数据结构-栈和队列

发布于：2025-08-20 ⋅ 阅读:(19) ⋅ 点赞:(0)

一、核心定义与原则

栈和队列均为线性数据结构，核心差异体现在 “数据操作顺序”，决定了二者的适用场景截然不同。

数据结构

核心定义

核心原则

操作端限制

栈（Stack）

仅允许在一端（栈顶）进行插入和删除的数据结构

LIFO（Last-In-First-Out，后进先出）

仅栈顶可操作（入栈、出栈），栈底固定

队列（Queue）

仅允许在一端（队尾）插入、另一端（队头）删除的数据结构

FIFO（First-In-First-Out，先进先出）

队尾入队、队头出队，两端分工操作

二、核心操作与时间复杂度

二者核心操作均围绕 “增、删、查、判空” 展开，基于数组 / 链表实现时，时间复杂度均为 O (1)（高效操作）。

操作类型

栈（Stack）

队列（Queue）

操作描述

时间复杂度

插入（增）

push(E e)

offer(E e)

向栈顶 / 队尾添加元素

O(1)

删除（删）

pop()

poll()

移除并返回栈顶 / 队头元素

O(1)

查看（查）

peek()

peek()

返回栈顶 / 队头元素（不移除）

O(1)

边界判断

isEmpty()

isEmpty()

判断结构是否为空

O(1)

边界判断

isFull()（仅固定容量）

isFull()（仅固定容量）

判断结构是否已满

O(1)

三、主流实现方式对比

栈和队列均支持数组实现和链表实现，不同实现方式的优劣与适用场景不同。

数据结构

实现方式

核心原理

优点

缺点

适用场景

栈

数组实现

用top指针指向栈顶索引，操作数组元素

访问速度快（索引直接定位），内存连续

容量固定，满栈需扩容（拷贝数据，效率低）

数据量已知、对速度要求高（如函数调用栈）

栈

链表实现

栈顶指向链表头节点，插入 / 删除仅操作头节点

容量动态扩展，无扩容问题

需额外存储指针 / 引用，内存不连续

数据量不确定、需灵活扩容（如编辑器撤销栈）

队列

数组实现（循环队列）

用front（队头）、rear（队尾）指针，数组循环复用

访问速度快，避免数组元素移动

需处理 “假满”（需预留 1 个空位或记录元素数）

数据量已知、高频读写（如任务队列）

队列

链表实现（链式队列）

队头指向链表头节点，队尾指向链表尾节点

容量动态扩展，无 “假满” 问题

需额外存储指针 / 引用，操作略慢

数据量不确定、需灵活扩容（如消息队列）

四、典型应用场景对比

二者的应用场景完全基于其核心原则（LIFO/FIFO），是解决特定问题的 “最优工具”。

数据结构

典型应用场景

场景原理（体现核心原则）

栈

1. 函数调用栈
2. 表达式求值（如3+4*(2-1)）
3. 括号匹配（如{[()]}验证）
4. 编辑器撤销操作

1. 函数调用入栈、执行完出栈（最后调用的函数最先执行完）
2. 运算符按优先级入栈，优先计算栈顶高优先级运算符
3. 左括号入栈，右括号与栈顶左括号匹配（最后入栈的左括号最先匹配）
4. 每步操作入栈，撤销时弹出最新操作

队列

1. 任务调度（如线程池任务队列）
2. 消息队列（如 MQ 中间件）
3. 浏览器 / APP 请求排队
4. 打印队列

1. 任务按提交顺序入队，线程按顺序处理（先提交的任务先执行）
2. 消息按发送顺序入队，消费者按顺序消费（先发送的消息先处理）
3. 多个请求按发起顺序排队，服务器按顺序响应
4. 打印任务按提交顺序入队，打印机按顺序打印

五、关键区别总结

对比维度

栈（Stack）

队列（Queue）

核心原则

LIFO（后进先出）

FIFO（先进先出）

操作端

仅 1 端（栈顶）：入栈、出栈均在栈顶

2 端分工：队尾入队、队头出队

指针 / 索引

仅需top指针（指向栈顶）

需front（队头）和rear（队尾）2 个指针

数组实现问题

满栈需扩容

易出现 “假满”（需循环队列优化）

核心关键词

“回溯”“撤销”“最近”

“排队”“顺序”“先来”

六、常见问题与注意事项

  1. 栈溢出 / 队列溢出：

    • 栈：数组实现满栈后push会溢出，需提前判断isFull()；链表实现无此问题，但需注意内存消耗。

    • 队列：数组实现（非循环）满队后offer会溢出；循环队列需通过 “(rear+1)%capacity == front” 判断满队。

  2. 空结构异常：
    对空栈执行pop()、对空队列执行poll()，会抛出异常（如 Java 的NoSuchElementException），需先通过isEmpty()判断。

  3. 队列的特殊变种：
    基于普通队列衍生出双端队列（Deque）（两端均可插入 / 删除）、优先级队列（PriorityQueue）（按优先级出队，不遵循 FIFO），可满足更复杂场景。

一 栈

一、代码执行流程

  1. 初始化阶段：创建Stack对象，此时栈的初始状态为：

    • 数组arr长度为 5（默认值均为 0）

    • 栈顶指针top = -1（表示栈为空）

  2. 入栈操作（push）：

    • stack.push(2)：top变为 0，arr[0] = 2

    • stack.push(5)：top变为 1，arr[1] = 5

    • stack.push(4)：top变为 2，arr[2] = 4

    • stack.push(1)：top变为 3，arr[3] = 1

    • stack.push(4)：top变为 4，arr[4] = 4（此时栈满）

  3. 出栈操作（pop）：

    • 第一次pop()：返回arr[4] = 4，top变为 3

    • 第二次pop()：返回arr[3] = 1，top变为 2

    • 第三次pop()：返回arr[2] = 4，top变为 1

    • 第四次pop()：返回arr[1] = 5，top变为 0

    • 第五次pop()：返回arr[0] = 2，top变为 - 1（此时栈空）

二、内存变化过程（栈内存与堆内存交互）

  1. 初始状态

    栈内存（main方法栈帧）：
- stack变量：引用地址（如0x001）

堆内存：
- Stack对象（地址0x001）：
  - arr数组：[0, 0, 0, 0, 0]（地址0x101）
  - top：-1

  2. 入栈完成后

    堆内存：
- Stack对象（地址0x001）：
  - arr数组：[2, 5, 4, 1, 4]（地址0x101）
  - top：4（指向数组索引4）

  3. 第一次 pop 后

    堆内存：
- Stack对象（地址0x001）：
  - arr数组：[2, 5, 4, 1, 4]（数组值未清空，仅指针移动）
  - top：3

  4. 第五次 pop 后

    堆内存：
- Stack对象（地址0x001）：
  - arr数组：[2, 5, 4, 1, 4]
  - top：-1（栈空状态）

三、核心原理总结

  1. 数据结构特性：栈遵循LIFO（后进先出） 原则，最后入栈的元素最先出栈

  2. 指针作用：top指针始终指向栈顶元素，通过改变指针位置实现入栈 / 出栈（无需真正删除数组元素）

  3. 边界判断：

    • 栈满条件：top == arr.length - 1

    • 栈空条件：top == -1

  4. 内存效率：基于数组实现的栈，操作时间复杂度为 O (1)，但容量固定（此例中最大容量为 5）

4
1
4
5
2

二 队列

一、Queue 类与 Test 类工作流程

1. 初始化阶段

  • Test类的main方法中创建Queue对象queue

  • Queue对象初始化时：

    • 成员变量arr为长度 5 的 int 数组（初始值均为 0）

    • front和rear初始值均为 - 1

2. 入队操作（add 方法）

执行queue.add(2)、queue.add(8)等 5 次入队操作：

  1. 每次调用add方法先检查队列是否满（isFull()判断rear == arr.length-1）

  2. 未满时rear自增 1，将值存入arr[rear]

  3. 5 次入队后：

    • rear变为 4（达到数组最大索引）

    • arr中存储[2,8,7,3,7]

    • 队列处于满状态

3. 出队操作（remove 方法）

执行 6 次queue.remove()操作：

  1. 前 5 次出队：

    • 检查队列是否空（isEmpty()判断rear == front）

    • 非空时front自增 1，返回arr[front]

    • 依次返回 2、8、7、3、7，front最终变为 4

  2. 第 6 次出队：

    • 此时front == rear（均为 4），isEmpty()返回 true

    • 抛出RuntimeException("空队列")

二、内存图流程（关键节点）

  1. 对象创建时

    queue引用 → Queue对象
               ├─ arr → [0,0,0,0,0]（长度5）
               ├─ front = -1
               └─ rear = -1

  2. 5 次入队后

    queue引用 → Queue对象
               ├─ arr → [2,8,7,3,7]
               ├─ front = -1
               └─ rear = 4

  3. 4 次出队后

    queue引用 → Queue对象
               ├─ arr → [2,8,7,3,7]
               ├─ front = 3
               └─ rear = 4

  4. 5 次出队后

    queue引用 → Queue对象
               ├─ arr → [2,8,7,3,7]
               ├─ front = 4
               └─ rear = 4 （此时队列空）

  5. 第 6 次出队时

    • 触发异常，程序终止

三、注意事项

  • 该队列实现为顺序队列，基于固定长度数组

  • 存在假溢出问题：当front和rear都到达数组末尾后，即使队列已空也无法继续入队

  • 入队满时仅打印提示，出队空时抛出异常，处理方式不同

  • 数组元素不会被真正删除，只是通过front指针移动标记出队

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布