算法

013【入门】队列和栈-链表、数组实现

本博客介绍了队列和栈的基本概念及其链表和数组实现。队列遵循先进先出（FIFO）原则，而栈遵循后进先出（LIFO）原则。重点讲解了数组实现队列时环形队列的设计，以及栈和队列的常见操作。最后通过力扣622题展示了环形队列的实际应用和解法。

Posted by Hilda on March 25, 2025

概览

前置知识：链表

建议：比较初级，会的可以跳过，但是要注意环形队列用数组实现这个高频考点

1）队列的介绍

2）栈的介绍

3）队列的链表实现和数组实现

4）栈的数组实现

5）环形队列用数组实现

队列、栈、双端队列可以组成非常多重要的数据结构

将在【必备】课程里继续

本节涉及的力扣题目：622. 设计循环队列

队列的介绍

先到先出，尾巴进，头部出

【队列的实现：链表】

一开始进来的节点，头节点和尾节点都指向它，后续进来的节点，改变尾节点指向新节点。每次要出去一个节点，就让头节点指向的节点出去（C++需要析构），头节点指向下一个节点(next节点)。

【队列的实现：数组】：算法题目中，很多时候进来的数据的个数是已知的，即“入数N”已知，就可以用数组实现队列。

假设“入数”=5000，那么（如果是Java）N=5000, int[] arr = new int[N]

一开始，L = 0, R = 0，此时队列长度是0。

规定队列范围是[L,R)，如果L < R，则队列有数据；L = R，队列无数据

每次进一个新的数x，则放R位置，R++

每次弹出一个数，就弹出L位置的数，L++

代码实现队列-Java内部LinkedList

用Java内部LinkedList实现，public Queue<Integer> queue = new LinkedList<>();是双向链表，常数操作慢，但是其实单向链表就够了。

代码如下，几乎就是用原生的东西拼的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.LinkedList;
import java.util.Queue;

public class Queue1 {


    // java内部实现队列，用LinkedList(双向链表),但是其实单项链表就够了
    public static class Queue_LL {
        // LinkedList是双向链表，常数操作慢
        public Queue<Integer> queue = new LinkedList<>();
        //调用任何方法之前，先判断有没有数组
        public boolean isEmpty(){
            return queue.isEmpty();
        }
        // 向队列加一个数，加到尾巴

        public void offer(int num) {
            queue.offer(num);
        }
        // 从队列拿一个数，头节点拿数

        public int poll() {
            return queue.poll();
        }
        // 返回队列头元素，不弹出

        public int peek() {
            return queue.peek();
        }
        // 返回队列元素个数

        public int size() {
            return queue.size();
        }
    }
}

代码实现队列-常数时间更好

实际刷题时更常见的写法，常数时间好

如果可以确定加入操作的总次数不超过n，那么可以用

一般笔试、面试都会有一个明确数据量，所以这是最常用的方式

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Queue2 {

    // 实际刷题时更常见的写法，常数时间好
    // 如果可以确定加入操作的总次数不超过n，那么可以用
    // 一般笔试、面试都会有一个明确数据量，所以这是最常用的方式
    public static class Queue_arr {
        public int[] queue;
        public int l;
        public int r;

        // 加入次数的上限n是多少，一定要明确
        public Queue_arr(int n) {
            this.queue = new int[n];
            this.l = 0;
            this.r = 0;
        }

        public boolean isEmpty() {
            return l == r; //l = r 代表没数据  l < r代表有数据
        }
        public void offer(int num) {
            queue[r++] = num;
        }

        public int poll() {
            return queue[l++];
        }

        public int peek() {
            return queue[l];
        }

        public int tail() {
            return queue[r - 1];
        }

        public int size() {
            return r - l;
        }


    }
}

栈的介绍

先进后出

新加入一个数x，放size位置，size++

弹出时，弹出size-1位置，然后size--

代码实现栈-Java内部Stack

其实就是动态数组，常数时间并不好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.Stack;

public class Stack1 {

    public static class Stack_java {
        // 其实就是动态数组，常数时间并不好
        public Stack<Integer> stack = new Stack<>();

        // 调用任何方法之前，先调用这个判断栈里面有没有数据
        public boolean isEmpty() {
            return stack.isEmpty();
        }

        public void push(int num) {
            stack.push(num);
        }

        public int pop() {
            return stack.pop();
        }

        public int peek() {
            return stack.peek();
        }

        public int size() {
            return stack.size();
        }


    }
}

代码实现栈-常数时间更好

如果可以保证同时在栈里的元素个数不会超过n，那么可以用下面的方法

发生弹出操作之后，空间可以复用

一般笔试、面试都会有一个明确数据量，所以这是最常用的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Stack2 {

    // 实际刷题时更常见的写法，常数时间好
    // 如果可以保证同时在栈里的元素个数不会超过n，那么可以用
    // 也就是发生弹出操作之后，空间可以复用
    // 一般笔试、面试都会有一个明确数据量，所以这是最常用的方式

    public static class stack_2 {
        public int[] stack;
        public int size;
				// 同时在栈里的元素个数不会超过n
        public stack_2(int n) {
            stack = new int[n];
            size = 0;
        }
				// 调用任何方法之前，先调用这个方法来判断栈内是否有东西
        public boolean isEmpty() {
            return size == 0;
        }

        public void push(int num) {
            stack[size++] = num;
        }

        public int pop() {
            return stack[--size];
        }

        public int peek() {
            return stack[size - 1];
        }
        public int size() {
            return size;
        }
    }
}

环形队列

如果能确定同时在队列中的数据的个数的上限不超过limit，那么可以用环形队列

首先，头位置=0，尾位置=0，size=0

1)加入x，放尾，尾++，结束了的话尾回0

2)弹出时，拿头，头++，结束了的话头回0

注意：以上加入或者弹出要在size满足条件的情况下发生。

size<limit(limit是指创建的数组的大小)，可以加数

size大于0，可以弹出数据

力扣622. 设计循环队列

622. 设计循环队列

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

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

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

示例：

1
2
3
4
5
6
7
8
9
10

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

提示：

  • 所有的值都在 0 至 1000 的范围内；
  • 操作数将在 1 至 1000 的范围内；
  • 请不要使用内置的队列库。

解法

下面这个解法是我自己写的，左老师是写的tail一开始是0，我写的是-1

image-20250325113713877

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class MyCircularQueue {

    private int[] arr;
    private int head;  // 队首指针
    private int tail;  // 队尾指针
    private int size;  // 队列容量
    private int num;   // 当前元素个数



    public MyCircularQueue(){

    }

    public MyCircularQueue(int k) {
        arr = new int[k];
        size = k;
        head = 0;
        tail = -1;
        num = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        tail = (tail + 1) % size;
        arr[tail] = value;
        num++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % size;
        num--;
        return true;
    }

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

    // 获取队尾元素。如果队列为空，返回 -1
    public int Rear() {
        if (isEmpty()) return -1;
        return arr[tail];
    }

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

    public boolean isFull() {
        return size == num;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

中规中矩的实现。

设计思想：

  • 使用固定大小的数组实现循环队列，通过取模操作实现首尾指针的循环移动。
  • 用 head 指向队首，tail 指向队尾，num 跟踪当前元素个数。

初始化：

  • MyCircularQueue(int k) 创建容量为 k 的数组。
  • head = 0（队首初始位置），tail = -1（队尾初始为空），num = 0。

核心操作：

  • 入队 (enQueue)：
    • 检查队列是否满（isFull）。
    • tail 向前移动（(tail + 1) % size），将值存入 arr[tail]，num 增加。
  • 出队 (deQueue)：
    • 检查队列是否空（isEmpty）。
    • head 向前移动（(head + 1) % size），num 减少。
  • 获取队首 (Front)：
    • 返回 arr[head]，空队列返回 -1。
  • 获取队尾 (Rear)：
    • 返回 arr[tail]，空队列返回 -1。

辅助方法：

  • isEmpty()：检查 num == 0。
  • isFull()：检查 num == size。

特点：

  • 时间复杂度：所有操作均为 O(1)。
  • 空间复杂度：O(k)，由数组大小决定。
  • 通过 head 和 tail 的循环移动实现空间复用，避免浪费。

左神的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

public class MyCircularQueue {
    public int[] queue;

    public int l, r, size, limit;

    // 同时在队列里的数字个数，不要超过k
    public MyCircularQueue(int k) {
        queue = new int[k];
        l = r = size = 0;
        limit = k;
    }

    // 如果队列满了，什么也不做，返回false
    // 如果队列没满，加入value，返回true
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            queue[r] = value;
            // r++, 结束了，跳回0
            r = r == limit - 1 ? 0 : (r + 1);
            size++;
            return true;
        }
    }

    // 如果队列空了，什么也不做，返回false
    // 如果队列没空，弹出头部的数字，返回true
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        } else {
            // l++, 结束了，跳回0
            l = l == limit - 1 ? 0 : (l + 1);
            size--;
            return true;
        }
    }

    // 返回队列头部的数字（不弹出），如果没有数返回-1
    public int Front() {
        if (isEmpty()) {
            return -1;
        } else {
            return queue[l];
        }
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        } else {
            int last = r == 0 ? (limit - 1) : (r - 1);
            return queue[last];
        }
    }

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

    public boolean isFull() {
        return size == limit;
    }

}
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 机器学习-吴恩达 力扣 Java基础 numpy ollama工具 pandas
    FRIENDS