``

前言

前面学习了单链表、双向链表，链表可以在任意位置插入删除，使用十分灵活。而栈和队列属于操作位置受限的特殊线性表，拥有固定的出入规则，是后端开发、操作系统中高频使用的数据结构。

一、普通表、栈、队列核心区别

1. 普通链表（线性表）
   可以在任意位置插入、任意位置删除，没有位置限制。

2. 栈（Stack）：先进后出，后进先出（LIFO）
   只能在同一端做插入和删除，这一端叫做栈顶；另一端叫栈底，不允许进行增删操作。

• 入栈（压栈 push）：往栈顶存放数据
• 出栈（弹栈 pop）：从栈顶取出数据

生活例子：弹夹，先压入的子弹最后才会打出来。

3. 队列（Queue）：先进先出，后进后出（FIFO）
   两端分开操作：一端只负责插入叫队尾，一端只负责删除叫队头。

• 入队：从队尾放入元素
• 出队：从队头取出元素

生活例子：排队，先来的人优先办理业务。

二、栈详解

1. 栈基础名词

• 栈顶：允许入栈、出栈的一端
• 栈底：封闭，不执行增删
• 栈针：标记下一个存放元素的位置
• 空栈：栈内没有元素
• 满栈：顺序栈容量耗尽，无法继续入栈

考试高频：空栈与满栈操作差异

• 空栈：栈针直接存数据，再移动栈针

• 满栈：先移动栈针，再存放数据

• 增栈：向内存高地址方向增长

• 减栈：向内存低地址方向增长，程序默认栈大多为减栈

2. 栈的两种实现

1. 顺序栈（数组实现）
   底层依托数组实现，容量固定，存在栈满溢出风险。

2. 链式栈（链表实现）
   底层依托单链表，没有容量上限；一般采用头插法入栈，头删法出栈，执行效率最高。

三、队列详解

1. 队列基础名词

• 队头：元素出队的一端
• 队尾：元素入队的一端

2. 队列两种实现

1. 顺序循环队列（数组）
   普通顺序队列会产生假溢出问题，循环队列将数组逻辑首尾相连；通常牺牲1个存储位置区分空队列与满队列。

2. 链式队列（链表）
   一般同时维护队头指针、队尾指针，方便两端操作。

链式队列接口声明

// 创建链式队列
Node_t *CreateLinkQueue(void);
// 判断队列是否为空
int IsEmptyLinkQueue(Node_t *pTmpQueue);
// 入队
int EnterLinkQueue(Node_t *pTmpQueue, DataType TmpData);
// 出队
DataType QuitLinkQueue(Node_t *pTmpQueue);
// 销毁队列
int DestroyLinkQueue(Node_t **ppTmpQueue);

注意：销毁队列传入二级指针，目的是将外部头指针置空，避免野指针。

四、双向链表回顾

双向链表每个节点包含三部分：数据域、前驱指针pPrev、后继指针pNext。

• 支持向前、向后双向遍历
• 插入、删除时，需要同时维护前驱、后继两组指针
• 缺点：增删操作指针逻辑多，容易写错
• 优点：获取上一个节点，不需要从头遍历

五、考点速记

1. 普通链表：任意位置完成增删；
2. 栈：先进后出，只操作栈顶；
3. 队列：先进先出，队尾入队、队头出队；
4. 顺序结构需要处理空、满边界；链式结构重点防止指针断链；
5. 链表、队列销毁函数优先使用二级指针。