数据结构——栈与队列：原理、实现与经典应用

上一篇讲了线性表（顺序表和链表），这一篇讲线性表的两种特殊形式——栈（Stack）和队列（Queue）。它们在 408 考研和面试中出现频率极高。

一、栈——后进先出

1. 什么是栈

栈（Stack）是限定只能在一端进行插入和删除操作的线性表。

允许操作的一端 → 栈顶（Top） 不允许操作的一端 → 栈底（Bottom） 插入 → 入栈（Push） 删除 → 出栈（Pop） ← 出栈 ┌───┐ │ 5 │ ← 栈顶 ├───┤ │ 4 │ ├───┤ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ ← 栈底 └───┘ push(6) → 放到栈顶

特点：后进先出（LIFO, Last In First Out）

生活中的例子：

• 一叠盘子——你只能从上面拿（后放上去的先用）
• 浏览器的后退——最后访问的页面最先回退
• 函数调用——最里层的函数最先返回

2. 顺序栈（数组实现）

publicclassArrayStack<E>{privatestaticfinalintDEFAULT_CAPACITY=10;privateE[]data;privateinttop;// 栈顶指针（指向当前栈顶元素位置）publicArrayStack(){data=(E[])newObject[DEFAULT_CAPACITY];top=-1;// 初始为空栈}// 入栈publicvoidpush(Eelement){if(top==data.length-1){grow();// 扩容}data[++top]=element;}// 出栈publicEpop(){if(isEmpty())thrownewEmptyStackException();Eelement=data[top];data[top--]=null;// 清空引用，帮助 GCreturnelement;}// 查看栈顶（不删除）publicEpeek(){if(isEmpty())thrownewEmptyStackException();returndata[top];}publicbooleanisEmpty(){returntop==-1;}publicintsize(){returntop+1;}}

时间复杂度：push/pop/peek 都是O(1)。

3. 链栈（链表实现）

publicclassLinkedStack<E>{privateNode<E>top;// 栈顶（链表头）privateintsize;privatestaticclassNode<E>{Edata;Node<E>next;Node(Edata){this.data=data;}}publicvoidpush(Eelement){Node<E>newNode=newNode<>(element);newNode.next=top;// 新节点指向旧栈顶top=newNode;// 新节点成为栈顶size++;}publicEpop(){if(isEmpty())thrownewEmptyStackException();Edata=top.data;top=top.next;// 栈顶下移size--;returndata;}publicEpeek(){if(isEmpty())thrownewEmptyStackException();returntop.data;}publicbooleanisEmpty(){returntop==null;}}

注意：链栈的 push/pop 都是在链表头部操作，不需要遍历，时间复杂度O(1)。

二、队列——先进先出

1. 什么是队列

队列（Queue）是限定在一端插入、另一端删除的线性表。

插入（队尾）→ ┌───┬───┬───┬───┬───┐ → 删除（队头） │ 1 │ 2 │ 3 │ 4 │ 5 │ └───┴───┴───┴───┴───┘ front ↑ ↑ rear

特点：先进先出（FIFO, First In First Out）

生活中的例子：

• 排队买奶茶——先来的先买到
• 打印机任务队列——先提交的先打印
• 消息队列——生产者发送，消费者按顺序处理

2. 顺序队列的问题

// 直接使用数组实现队列的问题：// 出队时 front 后移，导致数组前面的空间被浪费初始： front=0,rear=0[][][][][]A入队：[A][][][][]B入队：[A][B][][][]A出队： front=1[][B][][][]← 下标0的空间浪费了

解决方案：循环队列

3. 循环队列

┌──────────────────────┐ │ rear │ │ ↓ │ │ ┌──┬──┬──┬──┬──┐ │ │ │ │ │E │F │G │ │ │ ├──┼──┼──┼──┼──┤ │ │ │D │ │ │ │ │ │ │ └──┴──┴──┴──┴──┘ │ │ ↑ │ │ front │ └──────────────────────┘

publicclassCircularQueue<E>{privateE[]data;privateintfront;// 队头指针privateintrear;// 队尾指针（指向下一个插入位置）privateintsize;privateintcapacity;publicCircularQueue(intcapacity){this.capacity=capacity;data=(E[])newObject[capacity];front=0;rear=0;size=0;}// 入队publicbooleanenqueue(Eelement){if(isFull())returnfalse;data[rear]=element;rear=(rear+1)%capacity;// 循环size++;returntrue;}// 出队publicEdequeue(){if(isEmpty())returnnull;Eelement=data[front];data[front]=null;front=(front+1)%capacity;// 循环size--;returnelement;}publicbooleanisEmpty(){returnsize==0;}publicbooleanisFull(){returnsize==capacity;}}

关键：rear = (rear + 1) % capacity实现循环——到达数组末尾后回到开头。

4. 链式队列

publicclassLinkedQueue<E>{privateNode<E>front;// 队头（出队）privateNode<E>rear;// 队尾（入队）privateintsize;publicvoidenqueue(Eelement){Node<E>newNode=newNode<>(element);if(isEmpty()){front=rear=newNode;}else{rear.next=newNode;rear=newNode;}size++;}publicEdequeue(){if(isEmpty())returnnull;Edata=front.data;front=front.next;if(front==null)rear=null;// 队列变空size--;returndata;}}

三、栈和队列的对比

四、408 考研经典考题

题1：括号匹配

publicbooleanisValid(Strings){Stack<Character>stack=newStack<>();for(charc:s.toCharArray()){if(c=='('||c=='['||c=='{'){stack.push(c);// 左括号入栈}else{if(stack.isEmpty())returnfalse;chartop=stack.pop();if(c==')'&&top!='(')returnfalse;if(c==']'&&top!='[')returnfalse;if(c=='}'&&top!='{')returnfalse;}}returnstack.isEmpty();// 所有左括号都匹配完}

题2：用两个栈实现队列

classMyQueue{privateStack<Integer>inStack;// 入队栈privateStack<Integer>outStack;// 出队栈publicMyQueue(){inStack=newStack<>();outStack=newStack<>();}publicvoidpush(intx){inStack.push(x);// 直接压入入队栈}publicintpop(){if(outStack.isEmpty()){// 把入队栈的元素全部倒入出队栈while(!inStack.isEmpty()){outStack.push(inStack.pop());}}returnoutStack.pop();}}

原理：入队时放入 inStack，出队时从 outStack 取。outStack 空了就把 inStack 全部倒过来——倒一次后元素的顺序就变成了队列顺序。

题3：循环队列判空判满

两种判断方式： 方法1：size 字段（推荐，简单明了） isEmpty() → size == 0 isFull() → size == capacity 方法2：牺牲一个存储单元 空 → rear == front 满 → (rear + 1) % capacity == front

题4：用队列实现栈（了解即可）

classMyStack{privateQueue<Integer>queue;publicvoidpush(intx){queue.offer(x);// 把前面的元素移到后面，让新元素在队头for(inti=0;i<queue.size()-1;i++){queue.offer(queue.poll());}}publicintpop(){returnqueue.poll();}}

五、实际开发中的应用

栈的应用： JVM 虚拟机栈 → 方法调用和返回 表达式求值 → 中缀转后缀 撤销操作 → Ctrl+Z 队列的应用： 线程池任务队列 → 等待执行的任务 消息队列 MQ → 异步解耦 树的层序遍历 → BFS

六、Java 中的栈和队列

// 栈（Java 官方推荐用 Deque 代替 Stack）Deque<String>stack=newArrayDeque<>();stack.push("A");// 入栈stack.pop();// 出栈stack.peek();// 查看栈顶// 队列Queue<String>queue=newLinkedList<>();queue.offer("A");// 入队queue.poll();// 出队queue.peek();// 查看队头// 双端队列（两端都可操作）Deque<String>deque=newArrayDeque<>();deque.addFirst("A");deque.addLast("B");deque.removeFirst();deque.removeLast();

总结：栈和队列其实就是限制了操作位置的线性表。栈只在一端操作（LIFO），队列在两端操作（FIFO）。代码实现时注意循环队列的取模运算和判空判满条件。

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫 实战干货，不让你白来。