上一篇讲了线性表（顺序表和链表），这一篇讲线性表的两种特殊形式------栈（Stack）和队列（Queue）。它们在 408 考研和面试中出现频率极高。
一、栈------后进先出
1. 什么是栈
栈（Stack） 是限定只能在一端进行插入和删除操作的线性表。
复制代码
允许操作的一端 → 栈顶（Top）
不允许操作的一端 → 栈底（Bottom）
插入 → 入栈（Push）
删除 → 出栈（Pop）
← 出栈
┌───┐
│ 5 │ ← 栈顶
├───┤
│ 4 │
├───┤
│ 3 │
├───┤
│ 2 │
├───┤
│ 1 │ ← 栈底
└───┘
push(6) → 放到栈顶
特点：后进先出（LIFO, Last In First Out）
生活中的例子：
一叠盘子------你只能从上面拿（后放上去的先用）
浏览器的后退------最后访问的页面最先回退
函数调用------最里层的函数最先返回
2. 顺序栈（数组实现）
java
复制代码
public class ArrayStack
private static final int DEFAULT_CAPACITY = 10;
private E[] data;
private int top; // 栈顶指针（指向当前栈顶元素位置）
public ArrayStack() {
data = (E[]) new Object[DEFAULT_CAPACITY];
top = -1; // 初始为空栈
}
// 入栈
public void push(E element) {
if (top == data.length - 1) {
grow(); // 扩容
}
data[++top] = element;
}
// 出栈
public E pop() {
if (isEmpty()) throw new EmptyStackException();
E element = data[top];
data[top--] = null; // 清空引用，帮助 GC
return element;
}
// 查看栈顶（不删除）
public E peek() {
if (isEmpty()) throw new EmptyStackException();
return data[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
}
时间复杂度： push/pop/peek 都是 O(1)。
3. 链栈（链表实现）
java
复制代码
public class LinkedStack
private Node
private int size;
private static class Node
E data;
Node
Node(E data) { this.data = data; }
}
public void push(E element) {
Node
newNode.next = top; // 新节点指向旧栈顶
top = newNode; // 新节点成为栈顶
size++;
}
public E pop() {
if (isEmpty()) throw new EmptyStackException();
E data = top.data;
top = top.next; // 栈顶下移
size--;
return data;
}
public E peek() {
if (isEmpty()) throw new EmptyStackException();
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}
注意： 链栈的 push/pop 都是在链表头部操作，不需要遍历，时间复杂度 O(1)。
二、队列------先进先出
1. 什么是队列
队列（Queue） 是限定在一端插入、另一端删除的线性表。
复制代码
插入（队尾）→ ┌───┬───┬───┬───┬───┐ → 删除（队头）
│ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴───┴───┘
front ↑ ↑ rear
特点：先进先出（FIFO, First In First Out）
生活中的例子：
排队买奶茶------先来的先买到
打印机任务队列------先提交的先打印
消息队列------生产者发送，消费者按顺序处理
2. 顺序队列的问题
java
复制代码
// 直接使用数组实现队列的问题：
// 出队时 front 后移，导致数组前面的空间被浪费
初始： front=0, rear=0 [ ][ ][ ][ ][ ]
A入队： [A][ ][ ][ ][ ]
B入队： [A][B][ ][ ][ ]
A出队： front=1 [ ][B][ ][ ][ ] ← 下标0的空间浪费了
解决方案：循环队列
3. 循环队列
复制代码
┌──────────────────────┐
│ rear │
│ ↓ │
│ ┌──┬──┬──┬──┬──┐ │
│ │ │ │E │F │G │ │
│ ├──┼──┼──┼──┼──┤ │
│ │D │ │ │ │ │ │
│ └──┴──┴──┴──┴──┘ │
│ ↑ │
│ front │
└──────────────────────┘
java
复制代码
public class CircularQueue
private E[] data;
private int front; // 队头指针
private int rear; // 队尾指针（指向下一个插入位置）
private int size;
private int capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
data = (E[]) new Object[capacity];
front = 0;
rear = 0;
size = 0;
}
// 入队
public boolean enqueue(E element) {
if (isFull()) return false;
data[rear] = element;
rear = (rear + 1) % capacity; // 循环
size++;
return true;
}
// 出队
public E dequeue() {
if (isEmpty()) return null;
E element = data[front];
data[front] = null;
front = (front + 1) % capacity; // 循环
size--;
return element;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}
关键： rear = (rear + 1) % capacity 实现循环------到达数组末尾后回到开头。
4. 链式队列
java
复制代码
public class LinkedQueue
private Node
private Node
private int size;
public void enqueue(E element) {
Node
if (isEmpty()) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
size++;
}
public E dequeue() {
if (isEmpty()) return null;
E data = front.data;
front = front.next;
if (front == null) rear = null; // 队列变空
size--;
return data;
}
}
三、栈和队列的对比
对比
栈
队列
规则
后进先出（LIFO）
先进先出（FIFO）
插入/删除位置
同一端（栈顶）
两端（队尾/队头）
常用实现
数组（顺序栈）
循环数组（循环队列）
适用场景
递归转非递归、括号匹配
排队系统、BFS、消息队列
四、408 考研经典考题
题1：括号匹配
java
复制代码
public boolean isValid(String s) {
Stack
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c); // 左括号入栈
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return stack.isEmpty(); // 所有左括号都匹配完
}
题2：用两个栈实现队列
java
复制代码
class MyQueue {
private Stack
private Stack
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void push(int x) {
inStack.push(x); // 直接压入入队栈
}
public int pop() {
if (outStack.isEmpty()) {
// 把入队栈的元素全部倒入出队栈
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}
}
原理： 入队时放入 inStack，出队时从 outStack 取。outStack 空了就把 inStack 全部倒过来------倒一次后元素的顺序就变成了队列顺序。
题3：循环队列判空判满
复制代码
两种判断方式：
方法1：size 字段（推荐，简单明了）
isEmpty() → size == 0
isFull() → size == capacity
方法2：牺牲一个存储单元
空 → rear == front
满 → (rear + 1) % capacity == front
题4：用队列实现栈（了解即可）
java
复制代码
class MyStack {
private Queue
public void push(int x) {
queue.offer(x);
// 把前面的元素移到后面，让新元素在队头
for (int i = 0; i < queue.size() - 1; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
}
五、实际开发中的应用
复制代码
栈的应用：
JVM 虚拟机栈 → 方法调用和返回
表达式求值 → 中缀转后缀
撤销操作 → Ctrl+Z
队列的应用：
线程池任务队列 → 等待执行的任务
消息队列 MQ → 异步解耦
树的层序遍历 → BFS
六、Java 中的栈和队列
java
复制代码
// 栈（Java 官方推荐用 Deque 代替 Stack）
Deque
stack.push("A"); // 入栈
stack.pop(); // 出栈
stack.peek(); // 查看栈顶
// 队列
Queue
queue.offer("A"); // 入队
queue.poll(); // 出队
queue.peek(); // 查看队头
// 双端队列（两端都可操作）
Deque
deque.addFirst("A");
deque.addLast("B");
deque.removeFirst();
deque.removeLast();
总结： 栈和队列其实就是限制了操作位置的线性表。栈只在一端操作（LIFO），队列在两端操作（FIFO）。代码实现时注意循环队列的取模运算和判空判满条件。
💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫 实战干货，不让你白来。