左神算法学习笔记 - 013 - 队列和栈 - 链表和数组实现

Weijian Duan

2025-02-17

https://www.bilibili.com/video/BV18X4y177vA/?spm_id_from=333.1387.search.video_card.click

这节讲的是两种基础的数据结构——队列和栈——底层可以如何实现。

首先要理解队列和栈都是逻辑结构，具体怎么实现有很多种方式。具体来说：

队列是一种先进先出的结构，类似于生活中的排队
栈是一种后进先出的结构，一个形象的比喻是弹夹中后压入的子弹会先被打出去

下面来看具体如何实现它们。

队列的实现

用链表来实现队列

用单链表就可以轻松地实现队列的效果，只需要一个头指针和尾指针，就能够实现入队、出队、查看队首等操作。

Java 中的 LinkedList 从名字上就能看出是一个链表，它就是 Queue 接口的一个实现类。

因此我们可以简单封装就得到了自己的队列：

public static class Queue1 {

		// java中的双向链表LinkedList
		// 单向链表就足够了
		public Queue<Integer> queue = new LinkedList<>();

		// 调用任何方法之前，先调用这个方法来判断队列内是否有东西
		public boolean isEmpty() {
			return queue.isEmpty();
		}

		// 向队列中加入num，加到尾巴
		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();
		}

	}

但是使用语言自带的队列实现，常数时间并不好。

用数组实现队列

可以通过数组实现队列，来优化常数时间。

我们可以根据题目数据量来申请一个最大长度的数组（比如题目说明了入队的总数量不超过 xxx），然后通过两个下标变量 l 和 r 来模拟头尾。

public static class Queue2 {
        public int[] queue;
        public int l;
        public int r;
        
        public Queue2(int n) {
            queue = new int[n];
            l = r = 0;
        }
        
        public boolean isEmpty() {
            return l == r;
        }
        
        public void offer(int num) {
            queue[r++] = num;
        }
        
        public int poll() {
            return queue[l++];
        }
        
        public int head() {
            return queue[l];
        }
        
        public int tail() {
            return queue[r - 1];
        }
        
        public int size() {
            return r - 1;
        }
    }

理解的关键点是，l 和 r 确定的是 [l, r) 范围的一个队列。比如说，一开始 l = r = 0 的时候，[0, 0) 代表队列里没有元素。理解了这一点，size 是 r - l，尾元素是 queue[r - 1] 就可以理解了。

栈的实现

Java 自带的栈

栈一般是通过数组来实现的，似乎没有链表的事。比如 Java 自带的栈——Stack 类——底层就是通过动态数组实现的，但依然是常数时间不好。

public static class Stack1 {
        
        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();
        }
    }

值得注意的是栈相关操作的 API 名称：push, pop 和队列不同

自己用数组 + size 变量实现栈

时间复杂度更好的实现是通过一个明确数据量的数组和 size 变量来做的。对于数据量来说，只要栈里同时存在的元素不超过 n，设置那么大的数组就可以了。

public static class Stack2 {
        
        public int[] stack;
        public int size;
        
        public Stack2(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;
        }
    }

这个 size 变量，不仅代表的是栈的大小，也可以通过它得到栈顶元素（size - 1 位置）

环形队列题目

环形队列这道题目是基于「用数组实现队列」的基本做法的，想要优化的地方是，数组前面的部分因为出队，已经有空余的空间，因此可以用来「循环」存储新的值。

622. 设计循环队列

class MyCircularQueue {

    public int[] queue;
    public int l, r, limit, size;

    public MyCircularQueue(int k) {
        queue = new int[k];
        l = r = size = 0;
        limit = k;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            queue[r] = value;
            r = (r == limit - 1) ? 0 : r + 1;
            size++;
            return true;
        }
    }
    
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        } else {
            l = (l == limit - 1) ? 0 : l + 1;
            size--;
            return true;
        }
    }
    
    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;
    }
}

复用的关键就在于 l 和 r 遇到边界时候的「调转操作」
- 涉及到入队、出队操作
- 同时也涉及到查看队尾元素，因为 r 是队尾元素的下一个下标
同时还利用到了 size 和 limit 两个变量，方便判空和判满
注意在每一个读取操作的时候，都需要判空和判满