栈与队列学习笔记

一文彻底搞懂「栈和队列」——从零基础到面试常考（含详细 Java 代码）

适合人群：零基础 / 小白，刚接触数据结构与 Java
学完收获：能听懂概念、写出代码、看懂面试题，对“栈”和“队列”形成一套完整的知识体系。

目录速览

• 一、为什么要学栈和队列？
• 二、栈（Stack）——像“盘子堆”一样的结构
  • 1. 栈的生活类比
  • 2. 栈的基本概念和术语
  • 3. 栈的常见操作
• 三、用 Java 实现一个“顺序栈”（基于数组）
• 四、用 Java 的标准库来使用栈
• 五、队列（Queue）——像“排队买票”一样的结构
  • 1. 队列的生活类比
  • 2. 队列的基本概念和术语
  • 3. 队列的常见操作
• 六、用数组实现一个“顺序队列”（简单版）
• 七、进阶：循环队列（解决空间浪费问题）
• 八、用 Java 标准库来使用队列
• 九、栈和队列的典型应用场景
• 十、常见面试题（附思路+代码）
• 十一、栈 vs 队列：一张表帮你对比记忆
• 十二、给初学者的一些小建议

快速记忆小口诀：

• 栈：一头进出，后进先出（像盘子堆）
• 队列：一头进，一头出，先进先出（像排队）

一、为什么要学栈和队列？

• 栈（Stack）和队列（Queue）是最基础的两种数据结构
• 很多高级数据结构和算法都是在它们之上构建的
• 各大公司面试中，这两个是反复考、常考、必考的知识点

先记住一句话：

• 栈：后进先出（LIFO, Last In First Out）
• 队列：先进先出（FIFO, First In First Out）

我们先从生活中的例子理解，再看 Java 代码。

二、栈（Stack）——像“盘子堆”一样的结构

1. 栈的生活类比

想象一下食堂洗好的一摞盘子：

盘子示意图（上面是栈顶）： ┌───────┐ ← 栈顶 Top │ 盘子3 │ 后放进去，先拿出来 ├───────┤ │ 盘子2 │ ├───────┤ │ 盘子1 │ 最先放进去，最后才拿出来 └───────┘ ← 栈底 Bottom

• 新盘子只能放在最上面（压在上一个盘子上）
• 要拿盘子时，也只能从最上面拿

所以：

• 最后放上去的盘子，最先被拿走—— 这就是后进先出（LIFO）

2. 栈的基本概念和术语

• 压栈（push）：向栈顶放入一个元素
• 弹栈（pop）：从栈顶取出一个元素
• 栈顶（top）：当前可以操作的“最上面”的那个元素
• 栈底（bottom）：最早被压入、在最下面的元素
• 空栈：栈中没有任何元素

3. 栈的常见操作

一般包含以下几个方法（用伪代码描述）：

• push(x)：把元素x压入栈顶
• pop()：弹出栈顶元素，并返回
• peek() / top()：只看一眼栈顶元素，但不删除
• isEmpty()：栈是否为空
• size()：栈中有多少个元素

三、用 Java 实现一个“顺序栈”（基于数组）

我们先不用现成的java.util.Stack，自己实现一个栈，这样理解更深刻。

1. 核心设计思路

• 用一个数组data[]来存元素
• 用一个整型变量top来记录“当前栈顶的位置”

约定：

• 当栈为空时：top = -1
• 当有元素时：
  • 栈顶元素在data[top]
  • 每次push：先top++，然后赋值data[top] = x
  • 每次pop：取出data[top]，然后top--

2. 代码：基于数组实现的栈（含详细注释）

/** * 一个简单的顺序栈实现（基于数组） * 为了方便理解，我们只存 int 类型 */publicclassArrayStack{// 用数组存储栈中的元素privateint[]data;// top 代表“栈顶”下标，-1 代表空栈privateinttop;// 构造方法：指定栈的容量publicArrayStack(intcapacity){data=newint[capacity];// 初始化数组top=-1;// 一开始是空栈}/** * 入栈（压栈）操作 * @param value 要压入栈顶的元素 * @return 是否压入成功 */publicbooleanpush(intvalue){// 栈满的判断：top 已经到了数组最后一个下标if(top==data.length-1){System.out.println("栈满了，无法再压栈！");returnfalse;}// 先移动 top，再赋值top++;data[top]=value;returntrue;}/** * 出栈（弹栈）操作 * @return 栈顶元素；如果为空，则抛出异常或返回一个特殊值 */publicintpop(){if(isEmpty()){thrownewRuntimeException("栈为空，无法弹栈！");}// 先取值，再移动 topintvalue=data[top];top--;returnvalue;}/** * 查看栈顶元素（但不删除） */publicintpeek(){if(isEmpty()){thrownewRuntimeException("栈为空，没有栈顶元素！");}returndata[top];}/** * 栈是否为空 */publicbooleanisEmpty(){returntop==-1;}/** * 当前栈中元素个数 */publicintsize(){returntop+1;}/** * 打印当前栈中元素（从栈底到栈顶） */publicvoidprintStack(){if(isEmpty()){System.out.println("栈是空的");return;}System.out.print("栈中元素（从栈底到栈顶）：");for(inti=0;i<=top;i++){System.out.print(data[i]+" ");}System.out.println();}// 简单测试一下publicstaticvoidmain(String[]args){ArrayStackstack=newArrayStack(5);stack.push(10);stack.push(20);stack.push(30);stack.printStack();// 10 20 30System.out.println("当前栈顶元素："+stack.peek());// 30intpopped=stack.pop();System.out.println("弹出了元素："+popped);// 30stack.printStack();// 10 20System.out.println("当前栈大小："+stack.size());// 2}}

四、用 Java 的标准库来使用栈

在真实开发中，我们通常不会自己写栈，而是用 JDK 提供的容器。

1. 方式一：java.util.Stack

importjava.util.Stack;publicclassStackDemo{publicstaticvoidmain(String[]args){// 创建一个栈，元素类型为 IntegerStack<Integer>stack=newStack<>();// 压栈stack.push(1);stack.push(2);stack.push(3);System.out.println("栈顶元素："+stack.peek());// 3// 弹栈System.out.println("弹出："+stack.pop());// 3System.out.println("弹出："+stack.pop());// 2// 判断是否为空System.out.println("栈是否为空："+stack.isEmpty());// false}}

2. 方式二（面试常问）：用Deque代替Stack

Java 官方文档更推荐使用Deque（双端队列）来实现栈，因为Stack是比较老的类，基于Vector，有一些性能/设计上的历史包袱。

importjava.util.ArrayDeque;importjava.util.Deque;publicclassDequeAsStackDemo{publicstaticvoidmain(String[]args){// 用 Deque 来模拟栈Deque<Integer>stack=newArrayDeque<>();// 压栈：使用 pushstack.push(10);stack.push(20);stack.push(30);// 查看栈顶元素System.out.println("栈顶元素："+stack.peek());// 30// 弹栈System.out.println("弹出："+stack.pop());// 30System.out.println("弹出："+stack.pop());// 20System.out.println("是否为空："+stack.isEmpty());// false}}

面试小知识：
问：Java 中实现栈用什么？
答：可以用Stack，但更推荐使用Deque的实现类，比如ArrayDeque来实现栈结构。

五、队列（Queue）——像“排队买票”一样的结构

1. 队列的生活类比

最经典的例子：排队买奶茶。

• 最先排队的人，最先买到奶茶，然后离开队伍
• 新来的人，排到队伍的末尾

所以队列的规则是：

• 先来先服务：先进先出（FIFO, First In First Out）

2. 队列的基本概念和术语

• 入队（enqueue / offer）：从队尾插入一个元素
• 出队（dequeue / poll）：从队头取出一个元素
• 队头（front / head）：下一个要被取出的那个元素
• 队尾（rear / tail）：最后进入队列的那个元素
• 空队列：没有任何元素

3. 队列的常见操作

队列方向示意图： 入队方向 → [ 队头 ... 队列中间 ... 队尾 ] → 出队方向 front rear

• offer(x) / add(x)：入队
• poll() / remove()：出队
• peek() / element()：只看一下队头元素，不删除
• isEmpty()：是否为空
• size()：当前元素个数

六、用数组实现一个“顺序队列”（最简单版本）

为了更容易理解，我们先写一个最简单的数组队列版本，暂时不考虑“循环利用空间”的问题。

1. 核心思路

• 用一个数组data[]存元素
• 用两个指针（下标）
  • front：指向队头元素的位置
  • rear：指向队尾后面一个位置（也可以理解为“下一个可以插入的位置”）

简单版本约定：

• 初始时：front = 0,rear = 0，队列为空
• 每次入队：把元素放在data[rear]，然后rear++
• 每次出队：返回data[front]，然后front++
• 当front == rear：队列为空

缺点：当rear走到数组末尾时，即使前面有空间，也不能再插入（浪费空间）。
不过没关系，这个版本先帮你理解基本原理，后面我们再改进成循环队列。

2. 代码：简单数组队列实现

/** * 一个简单的顺序队列（基于数组，不循环利用空间） */publicclassSimpleArrayQueue{privateint[]data;privateintfront;// 指向队头元素privateintrear;// 指向队尾后面一个位置（下一次入队的位置）publicSimpleArrayQueue(intcapacity){data=newint[capacity];front=0;rear=0;}/** * 入队 */publicbooleanoffer(intvalue){if(rear==data.length){System.out.println("队列已满（简单实现，不可再入队）");returnfalse;}data[rear]=value;rear++;returntrue;}/** * 出队 */publicintpoll(){if(isEmpty()){thrownewRuntimeException("队列为空，无法出队！");}intvalue=data[front];front++;returnvalue;}/** * 查看队头元素 */publicintpeek(){if(isEmpty()){thrownewRuntimeException("队列为空，没有队头元素！");}returndata[front];}/** * 是否为空 */publicbooleanisEmpty(){returnfront==rear;}/** * 当前元素个数 */publicintsize(){returnrear-front;}publicvoidprintQueue(){if(isEmpty()){System.out.println("队列为空");return;}System.out.print("队列中的元素（从队头到队尾）：");for(inti=front;i<rear;i++){System.out.print(data[i]+" ");}System.out.println();}publicstaticvoidmain(String[]args){SimpleArrayQueuequeue=newSimpleArrayQueue(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.printQueue();// 1 2 3System.out.println("队头元素："+queue.peek());// 1System.out.println("出队："+queue.poll());// 1queue.printQueue();// 2 3}}

七、进阶：循环队列（解决空间浪费问题）

刚刚的简单队列有一个问题：前面空出来的位置用不了。
解决办法：把数组当成一个“环”来使用，这就是循环队列（circular queue）。

1. 循环队列的思想（模运算）

我们依然用front和rear两个指针，只是每次移动时都让下标绕圈：

• 入队时：rear = (rear + 1) % capacity
• 出队时：front = (front + 1) % capacity

为了区分“队满”和“队空”，常用办法是：

• 保留一个空位
• 约定：
  • 当(rear + 1) % capacity == front时，队列“满”
  • 当front == rear时，队列“空”

2. 代码：循环队列实现

/** * 循环队列实现（基于数组，保留一个空位来区分满和空） */publicclassCircularQueue{privateint[]data;privateintfront;// 队头下标privateintrear;// 队尾后一个位置publicCircularQueue(intcapacity){// 注意：实际可用的元素个数是 capacity - 1（因为要空出一个）data=newint[capacity];front=0;rear=0;}/** * 队列是否为空 */publicbooleanisEmpty(){returnfront==rear;}/** * 队列是否已满 * 条件：再往前走一步就撞上 front 了 */publicbooleanisFull(){return(rear+1)%data.length==front;}/** * 入队操作 */publicbooleanoffer(intvalue){if(isFull()){System.out.println("循环队列已满，无法入队！");returnfalse;}data[rear]=value;rear=(rear+1)%data.length;// 让 rear 向前走一步（绕圈）returntrue;}/** * 出队操作 */publicintpoll(){if(isEmpty()){thrownewRuntimeException("循环队列为空，无法出队！");}intvalue=data[front];front=(front+1)%data.length;// front 向前走一步returnvalue;}/** * 查看队头元素 */publicintpeek(){if(isEmpty()){thrownewRuntimeException("循环队列为空！");}returndata[front];}/** * 当前元素个数 */publicintsize(){// 环形队列的长度计算公式return(rear-front+data.length)%data.length;}publicvoidprintQueue(){if(isEmpty()){System.out.println("队列为空");return;}System.out.print("队列中的元素（从队头到队尾）：");inti=front;while(i!=rear){System.out.print(data[i]+" ");i=(i+1)%data.length;}System.out.println();}publicstaticvoidmain(String[]args){// 注意：数组长度为 5，最多只能存 4 个元素CircularQueuequeue=newCircularQueue(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.printQueue();// 1 2 3 4System.out.println("队列是否已满："+queue.isFull());// trueSystem.out.println("出队："+queue.poll());// 1System.out.println("出队："+queue.poll());// 2queue.printQueue();// 3 4queue.offer(5);queue.offer(6);queue.printQueue();// 3 4 5 6 （通过“绕圈”复用了空间）}}

八、用 Java 标准库来使用队列

Java 中常用的队列接口是java.util.Queue，最常见的实现类有：

• LinkedList：基于链表的队列
• ArrayDeque：基于数组的双端队列（既可以当队列，也可以当栈）

1. 使用LinkedList实现队列

importjava.util.LinkedList;importjava.util.Queue;publicclassLinkedListQueueDemo{publicstaticvoidmain(String[]args){// 使用 LinkedList 来实现 Queue 接口Queue<Integer>queue=newLinkedList<>();// 入队queue.offer(10);// 推荐使用 offer，队满时返回 false 不会抛异常queue.offer(20);queue.offer(30);System.out.println("队头元素："+queue.peek());// 10// 出队System.out.println("出队："+queue.poll());// 10System.out.println("出队："+queue.poll());// 20System.out.println("队列是否为空："+queue.isEmpty());// false}}

2. 使用ArrayDeque作为队列

importjava.util.ArrayDeque;importjava.util.Queue;publicclassArrayDequeQueueDemo{publicstaticvoidmain(String[]args){Queue<Integer>queue=newArrayDeque<>();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println("队头："+queue.peek());// 1System.out.println("出队："+queue.poll());// 1System.out.println("出队："+queue.poll());// 2}}

小提示：

• offer()/poll()/peek()：推荐在队列中使用，更安全，不容易抛异常
• add()/remove()/element()：在特殊情况下（队满、队空）会抛出异常

九、栈和队列在实际中的典型应用（帮助你更好理解）

1. 栈的典型应用

• 函数调用栈
  • 每调用一个方法，就压入栈
  • 方法执行完，就从栈中弹出
  • 这就是为什么有“栈溢出（StackOverflowError）”
• 撤销（Undo）功能
  • 比如文本编辑器的“撤销”：
    • 每次操作压栈
    • 撤销时从栈顶取出上一步操作
• 括号匹配（面试高频）
  • 如判断({[]})是否是合法括号序列
• 表达式求值
  • 中缀表达式转后缀表达式
  • 计算后缀表达式等

2. 队列的典型应用

• 操作系统的任务调度
  • 等待执行的任务，通常排队处理
• 消息队列（MQ）
  • Kafka、RabbitMQ 等系统本质上都在实现队列结构
• 广度优先搜索（BFS）
  • 图/树的层序遍历，用队列来实现
• 排队业务场景：
  • 银行排号、打印任务排队、网络请求处理等

十、常见面试题（附详解答案）

下面整理一些关于栈和队列的常见面试题，适合初级同学。

面试题 1：用栈实现队列

题目大意：
请用两个栈，实现一个队列，要求实现队列的两个基本操作：入队（push）和出队（pop）。

1. 思路讲解

队列是先进先出，栈是后进先出。
用两个栈倒来倒去，可以“反转顺序”，从而模拟队列：

• 准备两个栈：stackIn和stackOut
• 入队时：永远往stackIn里压栈
• 出队时：
  • 如果stackOut不为空：直接从stackOut弹栈
  • 如果stackOut为空：把stackIn中的所有元素依次弹出，压入stackOut
  • 然后再从stackOut弹出元素

这样：

• 进入顺序：1, 2, 3（入stackIn）
• 第一次出队时：
  • 把stackIn中的1, 2, 3依次弹出压入stackOut，顺序变成3, 2, 1
  • 然后从stackOut弹出栈顶1—— 就实现了“先来的先出队”

2. 代码实现（Java）

importjava.util.Stack;/** * 用两个栈实现一个队列 */publicclassMyQueueByTwoStacks{privateStack<Integer>stackIn;// 负责入队privateStack<Integer>stackOut;// 负责出队publicMyQueueByTwoStacks(){stackIn=newStack<>();stackOut=newStack<>();}/** * 入队操作 */publicvoidoffer(intvalue){stackIn.push(value);}/** * 出队操作 */publicintpoll(){if(isEmpty()){thrownewRuntimeException("队列为空，无法出队！");}// 如果 stackOut 为空，就把 stackIn 的元素全部倒过去if(stackOut.isEmpty()){while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}returnstackOut.pop();}/** * 查看队头元素 */publicintpeek(){if(isEmpty()){thrownewRuntimeException("队列为空！");}if(stackOut.isEmpty()){while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}returnstackOut.peek();}/** * 队列是否为空 */publicbooleanisEmpty(){returnstackIn.isEmpty()&&stackOut.isEmpty();}publicstaticvoidmain(String[]args){MyQueueByTwoStacksqueue=newMyQueueByTwoStacks();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.poll());// 1System.out.println(queue.poll());// 2queue.offer(4);System.out.println(queue.poll());// 3System.out.println(queue.poll());// 4}}

复杂度分析：

• 入队offer：平均时间复杂度为 (O(1))
• 出队poll：平均时间复杂度为 (O(1))（虽然有时会一次性搬很多元素，但摊还下来仍是常数级）

面试题 2：用队列实现栈

题目大意：
只使用队列的基本操作（入队、出队等），实现一个栈的功能（push、pop、top）。

1. 核心思路

栈是后进先出，我们用一个队列来模拟：

• 方法一：每次push时，保证新元素最后出队
• 常用做法：
  1. push(x)：先把x入队
  2. 然后把队列中前面的所有元素依次出队，再入队
  3. 这样，新来的x会被“旋转”到队头，之后pop时，总是先出x

2. 代码实现（Java）

importjava.util.LinkedList;importjava.util.Queue;/** * 用一个队列实现栈 */publicclassMyStackByQueue{privateQueue<Integer>queue;publicMyStackByQueue(){queue=newLinkedList<>();}/** * 压栈操作 */publicvoidpush(intx){// 1. 先把新元素入队queue.offer(x);// 2. 再把之前的元素“旋转”到新元素后面intsize=queue.size();// 除了刚入队的 x 之外，其它 size-1 个元素依次出队再入队for(inti=0;i<size-1;i++){intvalue=queue.poll();queue.offer(value);}}/** * 弹栈操作 */publicintpop(){if(isEmpty()){thrownewRuntimeException("栈为空，无法弹栈！");}// 因为我们在 push 的时候保证了“栈顶”总在队头returnqueue.poll();}/** * 查看栈顶元素 */publicinttop(){if(isEmpty()){thrownewRuntimeException("栈为空！");}returnqueue.peek();}/** * 栈是否为空 */publicbooleanisEmpty(){returnqueue.isEmpty();}publicstaticvoidmain(String[]args){MyStackByQueuestack=newMyStackByQueue();stack.push(1);stack.push(2);stack.push(3);System.out.println(stack.top());// 3System.out.println(stack.pop());// 3System.out.println(stack.pop());// 2System.out.println(stack.pop());// 1}}

复杂度分析：

• push：时间复杂度 (O(n))（每次要旋转前面的元素）
• pop、top：时间复杂度 (O(1))

面试题 3：用栈判断括号是否合法（经典高频题）

题目描述：
给定一个只包含()、[]、{}的字符串，判断括号是否成对、顺序是否正确。
例如：

• "()[]"合法
• "(]"不合法
• "([)]"不合法
• "{[]}"合法

1. 思路讲解

• 遍历字符串：
  • 遇到左括号：入栈
  • 遇到右括号：
    • 如果栈为空：不合法
    • 否则，弹出栈顶，看是否是对应的左括号
• 最后，栈必须为空，才算完全匹配

2. 代码实现（Java）

importjava.util.Stack;publicclassValidParentheses{publicstaticbooleanisValid(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();}publicstaticvoidmain(String[]args){System.out.println(isValid("()[]{}"));// trueSystem.out.println(isValid("([)]"));// falseSystem.out.println(isValid("{[]}"));// true}}

这道题几乎是“栈”的最经典应用题，力扣（LeetCode）上非常高频，建议熟练掌握。

十一、栈 vs 队列：一张表帮你对比记忆

十二、给初学者的一些小建议

• 多画图、多类比
  • 画出数组 + 指针（top / front / rear）的变化，印象更深
• 手动模拟一遍操作
  • 拿纸和笔模拟入栈、出栈，入队、出队
• 亲手敲一遍文中的代码
  • 不要只复制粘贴，自己打字可以加深记忆
• 尝试自己扩展
  • 把int改成泛型T，让栈 / 队列可以存任意类型
  • 给栈 / 队列加一个clear()方法