黑豆的博客

# 队列简介

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

用我们实际生活的场景来举例的话：就比如我们在车站排队买票，前面的乘客买完票后依次从队首离开，后面的需要买票的乘客依次从队尾排队进入买票。

# 队列的基本实现

对于队列来说我们主要实现以下方法：

方法名 含义
void enqueue(E) 入队（向队列中添加元素）
E dequeue() 出队（从队列中取出元素）
E getFront() 查看队首元素
E getSize() 查看队列中一共有多少元素
boolean isEmpty() 队列是否为空

这里我们使用之前实现的数组类来实现队列这种数据结构，由于调用的都是之前数组类中的方法这里不再赘述，直接给出具体实现：

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

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();
    }
    @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("Queue:");
        res.append("front [");

        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 int getCapacity() {
        return array.getCapacity();
    }
}

测试我们实现的方法：

public class Main {
    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);
            }
        }
    }
}

# 复杂度分析

方法名 时间复杂度 备注
void enqueue(E e) O(1) 均摊时间复杂度
E dequeue() O(n)
int getSize() O(1)
boolean isEmpty() O(1)
E getFront() O(1)

出队操作的时间复杂度是O(n)级别的，这是因为上述队列我们是通过数组实现的，当我们出队的时候也就是 把数组中的第一个元素拿出的时候，数组中其余的元素都要向前挪一位，所以出队的时间复杂度是O(n)的。

# 循环队列

上面我们通过数组实现的队列在出队的时候时间复杂度是O(n)级别的，有没有办法让队列出对的时候时间复杂度也是O(1)呢？

前面我们已经说过，导致出队时间复杂度是O(n)级别的原因是因为把数组中的第一个元素拿出后，数组中其余的元素都要向前挪一位。那我们可不可以不让其他元素往前移呢？

我们可以使用一个变量来记录下队首记为front队尾记为tail，当队首元素出队时只需要让front向前移动一位指向新的队首即可。

当front==tail时表明队列是空的，当有一个元素入队，只需要tail往后挪一位即可，依次类推。当队首元素出队时，只需要front向后挪动即可，依次类推，这时出队的时间复杂度就变成了O(1)。当将tail移动到队尾的时候此时再有元素入队，由于队首有空出的位置，可以将tail移动到队首的位置进行元素添加，直到(tail+1)%capacity == front的时候表示对列满了，此时需要扩容(注：capacity表示数组的长度)。

入队操作

public void enqueue(E e) {
    // 判断队列是否满了，满了的话进行扩容
    if ((tail + 1) % data.length == front)
        resize(getCapacity() * 2);
    // 向队尾添加元素
    data[tail] = e;
    // 将tail向后移一位，因为是循环队列需要对data.length取余，构成循环
    tail = (tail + 1) % data.length;
    size++;
}

扩容操作

private void resize(int newCapacity) {
    // newCapacity + 1 有意识的浪费一个空间
    E[] newData = (E[]) new Object[newCapacity + 1];

    for (int i = 0; i < size; i++)
        // newData[i]对应的应该是data[i+front]，对data.length取余是为了让队列循环起来
        newData[i] = data[(i + front) % data.length];

    data = newData;
    front = 0;
    tail = size;
}

如图简单举例说下扩容操作，当i的取值是[0, 1]时newData[i]对应的是data[i+front]位置的元素，当 i= 2时newData[i]的取值对应的是data[(i+front) % 4]的值，由于data是一个循环队列newData[i]对应的值应该是data[(i+front) % 4]位置的值。

出队操作

public E dequeue() {
    if (isEmpty())
        throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

    // 获取队首元素
    E ret = data[front];
    // 将队首位置的元素置空，便于垃圾回收
    data[front] = null;
    
    // 移动front，因为是循环队列，所以需要对data.length取余
    front = (front + 1) % data.length;
  
    size--;

    // 如果队列中的元素出队了容积的四分之一，这时队列应该进行缩容，注意：缩容的值不能是零
    if (size == getCapacity() / 4 && getCapacity() / 2 != 0)
        resize(getCapacity() / 2);

    return ret;
}

完整代码：

public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front, tail, size;

    public LoopQueue(int capacity) {
        // capacity + 1是为了有意识的浪费一个空间，防止队列满时tail == front
        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 boolean isEmpty() {
        return front == tail;
    }

    @Override
    public int getSize() {
        return size;
    }

    @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;
    }

    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        return data[front];
    }

    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 String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d, capacity = %d\n", size, getCapacity()));
        res.append("front [");
        // 循环队列中第一个元素在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> queue = new LoopQueue<>();

        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);

            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

# 复杂度分析

方法名 时间复杂度 备注
void enqueue(E e) O(1) 均摊时间复杂度
E dequeue() O(1) 均摊时间复杂度
int getSize() O(1)
boolean isEmpty() O(1)
E getFront() O(1)

# 数组队列和循环队列的比较

上面我们费了半天劲终于实现了循环队列，那它比咱们之前实现队列的方法性能真的有提高吗？下面我们来编码测试下：

import java.util.Random;

public class Main {
    // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
    private static double testQueue(Queue<Integer> q, int opCount){

        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i = 0 ; i < opCount ; i ++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for(int i = 0 ; i < opCount ; i ++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");
    }
}

下图为运行上述测试代码结果截图：

可以看到使用循环队列从性能上确实得到了不少的提升。

使用size不浪费空间

浪费一个空间不使用size

# 双端队列

可以在队列的两端添加元素，也可以在队列的两端删除元素。

# 练习

前面我们所实现的栈和队列都是通过动态数组来实现的，假设没有动态数组这种数据结构，现在有一个封装好的栈数据结构，我们怎么使用栈这种数据结构实现队列呢？反过来，给了一个封装好的队列这种数据结构，我们怎么使用这种数据结构实现栈呢？

# 第一题

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-stack-using-queues 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 第二题

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-queue-using-stacks 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

← 链表 →