数据结构之队列详解

蔚落 2022-03-06 02:56 253阅读 0赞

### 文章目录 ###

*  队列Queue
 *   *  队列的实现
     *  队列的时间复杂度
     *  手写一个循环队列：
     *  循环队列的时间复杂度

# 队列Queue #

*  队列也是一种线性结构
 *  相比数组，队列对应的操作是数组的子集
 *  只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
 *  队列是一种先进先出的数据结构
 *  First In First Out（FIFO）

## 队列的实现 ##

接口Queue：

/**
     * Created by binzhang on 2019/3/17.
     */
    public interface Queue<E> { 
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }

实现类ArrayQueue：

/**
     * Created by binzhang on 2019/3/17.
     */
    public class ArrayQueue<E> implements Queue<E> { 
    
        private Array<E> array;
    
        public ArrayQueue(int capacity){ 
            array = new Array<>(capacity);
        }
    
        public ArrayQueue(){ 
            array = new Array<>();
        }
    
        @Override
        public int getSize() { 
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() { 
            return array.isEmpty();
        }
    
        public int getCapacity(){ 
            return array.getCapacity();
        }
    
        @Override
        public void enqueue(E e) { 
            array.addLast(e);
        }
    
        @Override
        public E dequeue() { 
            return array.removeFirst();
        }
    
        @Override
        public E getFront() { 
            return array.getFirst();
        }
    
        @Override
        public String toString(){ 
            StringBuilder res = new StringBuilder();
            res.append(String.format("Queue: "));
            res.append('[');
            for (int i = 0 ; i < array.getSize() ; i ++){ 
                res.append(array.get(i));
                if(i != array.getSize() - 1)
                    res.append(", ");
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args) { 
            ArrayQueue<Integer> queue = new ArrayQueue<>();
            for (int i = 0 ; i < 10 ; i ++){ 
                queue.enqueue(i);
                System.out.println(queue);
                if (i % 3 == 2){ 
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

main方法运行结果：

Queue: [0] tail
    Queue: [0, 1] tail
    Queue: [0, 1, 2] tail
    Queue: [1, 2] tail
    Queue: [1, 2, 3] tail
    Queue: [1, 2, 3, 4] tail
    Queue: [1, 2, 3, 4, 5] tail
    Queue: [2, 3, 4, 5] tail
    Queue: [2, 3, 4, 5, 6] tail
    Queue: [2, 3, 4, 5, 6, 7] tail
    Queue: [2, 3, 4, 5, 6, 7, 8] tail
    Queue: [3, 4, 5, 6, 7, 8] tail
    Queue: [3, 4, 5, 6, 7, 8, 9] tail

## 队列的时间复杂度 ##

ArrayQueue

*  void enqueue(E) O(1)均摊
 *  E dequeue() O(n)
 *  E front() O(1)
 *  int getSize() O(1)
 *  boolean isEmpty() O(1)

可以看到数组出列的时间复杂度是O(n)的，所有的元素都要向前挪一位，性能相对是比较低的。  
循环队列可以解决这个问题。  
循环队列加入了`front`和`tail`两个属性。  
当`front==tail`时队列为空。  
每次入队的时候`tail`都会向后移动一个单位，当有出队操作时，`front`也会向后移动一个单位。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]

当数据插入到位置7后，tail会回到0位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]

那么tail是怎么回到0的呢，当我们插入的元素大于队列长度时采用取余的方式来计算  
`tail = (i + 1)/capacity`  
这里就是(7+1)/8（8为数组长度）就回到了我们索引为0的位置

注意我们之前定义了`front==tail`是队列为空的标志，索引当遇到下图情况即`tail+1==front`（更准确的说是`(tail + 1) % c == front`）的时候就表明我们的队列是满的了，可以进行扩容了，也就是说循环队列中总会是浪费一个空间的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]

## 手写一个循环队列： ##

/**
     * Created by binzhang on 2019/3/17.
     */
    public class LoopQueue<E> implements Queue<E> { 
    
        private E[] data;
        private int front, tail;
        private int size;
    
        public LoopQueue(int capacity){ 
            // 循环数组是有一个空间浪费的，所以要存储n个要定义空间大小为n+1
            data = (E[])new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        public LoopQueue(){ 
            this(10);
        }
    
        public int getCapacity(){ 
            return data.length - 1;
        }
    
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return front == tail;
        }
    
        @Override
        public void enqueue(E e) { 
            if ((tail + 1) % data.length == front)
                resize(getCapacity() * 2);
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size ++;
        }
    
        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;
        }
    
        @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;
        }
    
        @Override
        public E getFront() { 
            if (isEmpty())
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            return data[front];
        }
    
        @Override
        public String toString(){ 
            StringBuilder res = new StringBuilder();
            res.append(String.format("Queue: size = %d, capacity = %d\n", size, getCapacity()));
            res.append("front [");
            for (int i = front ; i != tail ; i = (i + 1) % data.length){ 
                res.append(data[i]);
                if((i + 1) % data.length != tail)
                    res.append(", ");
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args) { 
            LoopQueue<Integer> loopQueue = new LoopQueue<>();
            for (int i = 0 ; i < 10 ; i ++){ 
                loopQueue.enqueue(i);
                System.out.println(loopQueue);
                if (i % 3 == 2){ 
                    loopQueue.dequeue();
                    System.out.println(loopQueue);
                }
            }
    
        }
    }

输出：

Queue: size = 1, capacity = 10
    front [0] tail
    Queue: size = 2, capacity = 10
    front [0, 1] tail
    Queue: size = 3, capacity = 10
    front [0, 1, 2] tail
    Queue: size = 2, capacity = 5
    front [1, 2] tail
    Queue: size = 3, capacity = 5
    front [1, 2, 3] tail
    Queue: size = 4, capacity = 5
    front [1, 2, 3, 4] tail
    Queue: size = 5, capacity = 5
    front [1, 2, 3, 4, 5] tail
    Queue: size = 4, capacity = 5
    front [2, 3, 4, 5] tail
    Queue: size = 5, capacity = 5
    front [2, 3, 4, 5, 6] tail
    Queue: size = 6, capacity = 10
    front [2, 3, 4, 5, 6, 7] tail
    Queue: size = 7, capacity = 10
    front [2, 3, 4, 5, 6, 7, 8] tail
    Queue: size = 6, capacity = 10
    front [3, 4, 5, 6, 7, 8] tail
    Queue: size = 7, capacity = 10
    front [3, 4, 5, 6, 7, 8, 9] tail

> 循环队列出列的时间复杂度变为O(1)

## 循环队列的时间复杂度 ##

LoopQueue

*  void enqueue(E) O(1)均摊
 *  E dequeue() `O(1)` 均摊
 *  E front() O(1)
 *  int getSize() O(1)
 *  boolean isEmpty() O(1)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220306/2663013756a34b4cb4d9d44c67e87bca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]: /images/20220306/d16781b8d8774ef3b555a88ee96e5b52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]: /images/20220306/dd5022d64eb94b33bb7c977276e526b9.png