数据结构之数组实现队列和循环队列

我会带着你远行 2022-02-23 13:25 313阅读 0赞

## 队列 ##

**描述**  
队列的定义：先进先出（First In First Out）；队列是一种特殊的线性表，只允许在表的头部（front处）进行删除操作，在表的尾部（tail处）进行插入操作的线性数据结构，这种结构就叫做队列。进行插入操作的一端称为队尾，进行删除操作的一端称为队尾。  
队列的类型：链式队列，即用链表实现的队列。静态队列：即用数组实现的队列。在这里，我们采用用数组实现的静态队列。因为用链表实现的队列，是一种动态队列，操作更加容易，所以我们这里采用的是静态队列。  
**普通数组**  
普通就队列就是一个先进先出的数组，我们在一端进行插入元素，那么就在另一端进行删除元素。就像我们在排队打饭的时候，来一个人就在后面排队，当然是排在最前面的人先打饭，然后打完饭之后最前面的人就离开。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]  
**循环队列**  
循环队列是队列中的一个重点也是一个难点，我们需要在队列中不断的删除元素和添加元素，front代表了头部的位置，tail代表了尾部+1的位置。当头部前面还有位置的话，后面tail不在后面扩容，而是把延伸到front前面。如果按照正常的前边的数据被删除，一直在后边添加的话，那么就会导致很多空间被白白浪费掉。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 1]  
声明变量，编写构造函数，传入一个数组容量大小，和头部front和尾部tail，长度size

private E[] data;
        private int front, tail;
        private int size;  
        public LoopQueue(int capacity){
            data = (E[])new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        public LoopQueue(){
            this(10);
        }

入栈操作

@Override
        public void enqueue(E e){
    
            if((tail + 1) % data.length == front)
                resize(getCapacity() * 2);
    
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size ++;
        }

出栈操作，包含有前面讲到复杂度震荡的解决

@Override
        public E dequeue(){
    
            if(isEmpty())
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
    
            E ret = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size --;
            if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
                resize(getCapacity() / 2);
            return ret;
        }

扩容操作

private void resize(int newCapacity){
    
            E[] newData = (E[])new Object[newCapacity + 1];
            for(int i = 0 ; i < size ; i ++)
                newData[i] = data[(i + front) % data.length];
    
            data = newData;
            front = 0;
            tail = size;
        }

**总结**  
队列是一种先进先出的线性表。  
当front等于tail的时候数组为空。  
当(tail+1)%data.length==front 的时候表满，需要扩容  
浪费一个地址空间。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]: /images/20220223/3e78184fa2df4d1a8166757d8fe61986.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 1]: /images/20220223/5bb145fc1d2040c8b49f8ee907db756d.png