队列（Queue）

用户11820508

发布于 2026-01-12 14:35:37

一.队列

（1）概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）

（2）队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

import java.util.LinkedList;
import java.util.Queue;
public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);//入队列
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        Integer x = queue.peek();//队顶元素
        System.out.println("peek队顶元素" + x);
        Integer y = queue.poll();//出队列
        System.out.println("poll出队列元素" + y);
        Integer z = queue.size();//队中有效元素个数
        System.out.println("队内有效元素个数" + z);
        System.out.println("队内是否为空" + queue.isEmpty());
    }
}

（3）链表模拟实现队列

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。 队列的实现使用顺序结构还是链式结构好？ 顺序结构（数组）： 优点：

空间利用率高：在队列大小固定的情况下，顺序结构可以更有效地利用内存空间，因为数组中的元素是连续存储的。
访问速度快：由于数组中的元素是连续存储的，因此可以通过索引直接访问任何位置的元素，时间复杂度为O(1)。
缓存友好：顺序结构的数据在内存中通常是连续存放的，这有助于提高CPU缓存的命中率，从而加速数据访问。

缺点：

动态扩展困难：数组的长度是固定的
空间利用率受限：数组中元素较少时会存在空间浪费情况

链式结构（链表）： 优点：

动态扩展灵活
空间利用率高

缺点：

访问速度慢
缓存不友好

这里我们以双链表为例来实现队列，队列是遵循先进先出的，为了达到入队（尾插）和出队（头删）的时间复杂度为O(1)的效果，我们在定义head头节点的基础上，再定义一个last尾节点（若不定义尾节点就需要遍历链表，此时时间复杂度就是O(1)了）

public class MyQueue {
    static public class ListNode {
        //双向链表有三个属性：下一个节点的地址，前驱节点的地址，value值
        public int val;
        public ListNode pre;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode head;
        public ListNode last;

        public void offer(int val) {
            //入队列就是双链表的尾插法
            ListNode node = new ListNode(val);
            if (head == null) {
                //第一次插入
                head = last = node;
            }else {
                last.next = node;
                node.pre = last;
                last = last.next;
            }
        }

        public int poll() {
            //出队列就是头删
            if(head == null) {
                return -1;
            }
            int ret = head.val;
            if(head.next == null) {
                head = null;
                last = null;
            }else {
                head = head.next;
                head.pre = null;
            }
            return ret;
        }

        public int peek() {
            if(head == null) {
                return -1;
            }
            int ret = head.val;
            return ret;
        }
        
        public boolean isEmpty() {
            return head == null;
        }
    }
}

（4）数组设计循环队列

①链接

循环队列

https://leetcode.cn/problems/design-circular-queue/

②解析

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

简单来说循环队列就是将 “原本的存储方式由一条直线变为一个圆圈”

在我们进行出队（头删）操作时，当前下标对应的数据是空的，我们希望当数组满了的时候还可以循环利用前面为空的位置，也就是说当数组满的时候，我们还想进行添加操作，此时我们就可以添加到0，1，2位置

那我们如何判断是满还是空呢？

我们可以定义两个变量，first指向头，last指向尾，添加一个元素就last++，我们发现当fast == last是既可以表示空也可以表示满，很明显，这样解决不了问题；此时我们有三个方法来判断满的情况：

usedSize来计数数组中有几个元素，当usedSize = 数组长度时为满，相遇时为空（此时我们不需要定义last节点）空: us == 0满：us ==数组长度
boolean flg = false;以标记的方式处理满和空
浪费一个空间相遇就是空满: last的下一个是first

方法一解析：

空: us == 0满：us ==数组长度此时我们很容易就可以实现判空和判满这两个方法

首先我们定义三个成员变量，即头first，elem数组，usedSize

尾插一个元素enQueue(int value)：第一步先进行判满操作，当数组已经满员的情况下直接返回false 不满的话，我们要考虑当数组中后面已满前面为空时，怎样计算下一个需要插入的位置并确保该索引是循环的呢？也就是说再添加元素时，要添加到0下标的位置，即：(first + usedSize) % elem.length，添加到该下标即可，添加一个元素要usedSize++

头删一个元素deQueue()：第一步先进行判空操作，数组为空则直接返回false； first往后走一步并考虑循环，即(first + 1) % elem.length，删一个元素就usedSize--
获取队尾元素Rear(): 队尾下标索引并保证循环：(first + usedSize - 1) % elem.length

方法二解析：

我们通过浪费一个空间来队循环链表进行判空判满操作，因此在我们最初定义数组大小时就需要+1操作，即

elem = new int[k + 1];

尾插一个元素enQueue(int value)：第一步先进行判满操作，当数组已经满员的情况下直接返回false 进行尾插操作有两种情况：（第一次插入时直接插入last下标，之后将下标不断更新） ①数组内还有空间直接向last+1的下标进行尾插即可 ②last此时需要循环利用数组中的空间，数组是利用下标来进行访问的，因此我们需要形成一个表示下标索引的表达式，要求既能满足第一种情况的last+1，又能确保 last 索引在到达数组末尾后能够回绕到数组的开始。，即： last = (last + 1) % elem.length;
头删一个元素deQueue()：第一步先进行判空操作，数组为空则直接返回false；头删仅要求返回是否删除成功即可，所以我们只需要保证first索引在到达数组末尾后能够回绕到数组的开始，即： first = (first + 1) % elem.length;
获取队尾元素Rear(): 第一步先进行判空操作，数组为空则直接返回false；获取队尾元素就是返回last位置对应的下标即可，此时last有两种情况： ①last没有循环使用数组空间，下标为last-1的索引就是队尾元素 ②last循环使用了数组空间，且last位于下标为0的位置，此时要返回的下标索引应为elem.length - 1

③题解

方法一：usedSize实现

class MyCircularQueue {
    public int first;
    public int[] elem;
    public int usedSize;
    public MyCircularQueue(int k) {
        elem = new int[k];
        first = 0;
    }

    public boolean enQueue(int value) {
        //向循环队列插入一个元素。如果成功插入则返回真。
        //尾插
        if (isFull()) {
            return false;
        }
        int nextIndex = (first + usedSize) % elem.length; // 计算下一个插入位置  
        elem[nextIndex] = value;  
        usedSize++;  
        return true; 
    }

    public boolean deQueue() {
        //从循环队列中删除一个元素。如果成功删除则返回真。
        //头删
        if (isEmpty()) {
            return false;
        }
        first = (first + 1) % elem.length;//头删   first往后走一步
        usedSize--;
        return true;

    }

    public int Front() {
        //从队首获取元素。如果队列为空，返回 -1
        if(isEmpty()) {
            return -1;
        }
        return elem[first];
    }

    public int Rear() {
        //获取队尾元素。如果队列为空，返回 -1 。
        if (isEmpty()) {
            return -1;
        }
        int index = (first + usedSize - 1) % elem.length;
        return elem[index];
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }
}

方法二：浪费一块空间实现

class MyCircularQueue {
    private int first;
    private int last;
    private int[] elem;

    public MyCircularQueue(int k) {
        //k表示队列长度
        elem = new int[k + 1];
    }

    public boolean enQueue(int value) {
        //向循环队列插入一个元素。如果成功插入则返回真。
        if (isFull()) {
            return false;
        }
        elem[last] = value;//尾插
        last = (last + 1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        //从循环队列中删除一个元素。如果成功删除则返回真。
        if (isEmpty()) {
            return false;
        }
        first = (first + 1) % elem.length;//头删   first往后走一步
        return true;
    }

    public int Front() {
        //从队首获取元素。如果队列为空，返回 -1
        if(isEmpty()) {
            return -1;
        }
        return elem[first];
    }

    public int Rear() {
        //获取队尾元素。如果队列为空，返回 -1 。
        if (isEmpty()) {
            return -1;
        }
        int index = last == 0 ? elem.length - 1 : last - 1;
        return elem[index];
    }

    public boolean isEmpty() {
        //相遇就是空
        return first == last;
    }

    public boolean isFull() {
        //last的下一个是first
        return (last + 1) % elem.length == first;
    }
}

④ 计算数组下标循环的小技巧

1. 下标最后再往后(oﬀset 小于 array.length): index = (index + oﬀset) % array.length

2. 下标最前再往前(oﬀset 小于 array.length): index = (index + array.length - oﬀset) % array.length

⑤ 计算队列有效长度小技巧

现有一循环队列，其队头为front，队尾为rear(rear指向队尾数据的下一个位置)，循环队列长度为N,最多存储N-1个数据。其队内有效长度为(rear - front + N) % N 有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。

二.双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象。

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

三.面试题

1.队列实现栈

（1）链接

用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/

（2）解析

队列是遵循先进先出的原则，而栈是先进后出，因此我们需要使用两个栈来实现队列

push()方法：约定第一次入栈先放到q1中之后添加元素时,q1为空就添加到q2中，q2为空就添加到q1中
pop()方法：有两个空队列，我们约定入队的元素都在q1中，此时q2为空

因此我们只需要计算出不同情况下队中有效元素的个数即可，当q2为空时就将q1当中的元素移动到q2中，否则将q2的移动到q1中

（3）题解

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        //定义两个队列来实现栈
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if (empty()) {
            queue1.offer(x);//第一次入栈先放到q1中
            return;
        }
        if (queue1.isEmpty()) {
            queue2.offer(x);
        }else {
            queue1.offer(x);
        }
    }

    public int pop() {
        //思路：有两个空队列，我们约定入队的元素都在q1中，此时q2为空
        // 此时我们将q1中n-1个元素移动到q2中，q1中剩下的一个元素就是需要出栈的元素
        if(empty()) {
            return -1;
        }
        if(queue2.isEmpty()) {
            int size = queue1.size();
            for (int i = 0; i < size-1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else {
            int size = queue2.size();
            for (int i = 0; i < size-1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    public int top() {
        if(empty()) {
            return -1;
        }
        if(!queue1.isEmpty()) {
            int size = queue1.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret = queue1.poll();
                queue2.offer(ret);
            }
            return ret;
        }else {
            int size = queue2.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret = queue2.poll();
                queue1.offer(ret);
            }
            return ret;
        }
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

2.栈实现队列

（1）链接

栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/

（2）解析

pop(): 将一个栈中的元素全部拿到另一个栈中，依次将另一个栈的元素依次出栈即可若s2为空的话，就将s1中的所有元素直接添加到s2中（直到s1为空停止）即可，当我们需要出栈时只需要将s2中的元素按顺序出栈即可

（3）题解

class MyQueue {
    public ArrayDeque<Integer> s1;
    public ArrayDeque<Integer> s2;

    public MyQueue() {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        //思路：将一个栈中的元素全部拿到另一个栈中，依次将另一个栈的元素依次出栈即可
        if (empty()) {
            return -1;
        }
        if (s2.isEmpty()) {
            //将s1中的元素全部移到s2中
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if(empty()) {
            return -1;
        }
        if(s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-20，如有侵权请联系 cloudcommunity@tencent.com 删除

索引