C语言数据结构：栈和队列详解，从概念到代码实现一篇讲清楚
C语言数据结构：栈和队列详解，从概念到代码实现一篇讲清楚
往期回顾
《指针合集》《c语言基础》《数据结构》《机器学习导论》《前端基础》《操作系统》
目录
- 前言
- 一、栈和队列为什么重要？
- 二、什么是栈？
- 三、栈的核心操作
- 四、栈为什么适合用数组实现？
- 五、动态栈的结构设计
- 六、动态栈完整代码实现
- 七、什么是队列？
- 八、队列的核心操作
- 九、队列为什么更适合用链表实现？
- 十、链式队列的结构设计
- 十一、链式队列完整代码实现
- 十二、循环队列：数组如何高效实现队列？
- 十三、栈和队列的对比
- 十四、栈和队列的典型应用场景
- 十五、栈和队列常见易错点
- 全文总结
前言
在学习完顺序表和链表之后，我们会继续接触两种非常经典的线性数据结构：
栈
队列
它们看起来比顺序表、链表简单，因为它们的操作规则非常固定。
栈只允许在一端插入和删除。
队列只允许在一端插入，在另一端删除。
但也正因为规则固定，它们在很多场景里非常好用。
比如：
函数调用栈
浏览器前进后退
表达式求值
括号匹配
撤销和恢复
消息队列
任务调度
广度优先搜索
生产者消费者模型
如果说顺序表和链表是在研究“数据怎么存”，那么栈和队列更强调：
数据应该按照什么规则进出。
这一篇文章就系统梳理栈和队列的概念、结构、图解、C 语言实现以及常见应用。
一、栈和队列为什么重要？
栈和队列都属于线性结构。
所谓线性结构，就是数据之间存在前后关系。
比如：
a1 -> a2 -> a3 -> a4
但是栈和队列并不允许你随便在任意位置插入、删除。
它们都有自己的进出规则。
1. 栈强调“后进先出”
栈的规则是：
后进去的数据，先出来。
英文叫：
LIFO
Last In First Out
就像往桶里放盘子。
最后放上去的盘子，最先被拿走。
2. 队列强调“先进先出”
队列的规则是：
先进去的数据，先出来。
英文叫：
FIFO
First In First Out
就像排队买奶茶。
先排队的人，先被服务。
3. 它们解决的核心问题
栈和队列不是为了“存更多数据”，而是为了控制数据的访问顺序。
可以这样理解：
顺序表 / 链表：偏向底层存储结构
栈 / 队列：偏向操作规则和访问顺序
二、什么是栈？
栈是一种特殊的线性表。
它只允许在固定的一端进行插入和删除操作。
这一端叫：
栈顶
另一端叫：
栈底
栈中的数据遵循：
后进先出，这个也叫LIFO
栈的图解
入栈顺序：1 2 3 4
栈结构：
栈顶
↓
+-----+
| 4 |
+-----+
| 3 |
+-----+
| 2 |
+-----+
| 1 |
+-----+
↑
栈底
如果现在出栈，出来的是：
4
因为 4 是最后入栈的，也是最先出栈的。
比如你连续访问了几个页面：
页面 A -> 页面 B -> 页面 C
点击返回时，一般先回到页面 B。
因为页面 C 是最后访问的，它最先被返回出去。
这就是栈的思想。
三、栈的核心操作
栈的常见操作主要有下面几个。
| 操作 | 含义 |
|---|---|
StackInit |
初始化栈 |
StackPush |
入栈 / 压栈 |
StackPop |
出栈 |
StackTop |
获取栈顶元素 |
StackSize |
获取栈中元素个数 |
StackEmpty |
判断栈是否为空 |
StackDestroy |
销毁栈 |
1. 入栈 Push
入栈就是把数据放到栈顶。
原栈：
栈顶
↓
+---+
| 3 |
+---+
| 2 |
+---+
| 1 |
+---+
Push(4) 后：
栈顶
↓
+---+
| 4 |
+---+
| 3 |
+---+
| 2 |
+---+
| 1 |
+---+
2. 出栈 Pop
出栈就是删除栈顶元素。
原栈：
栈顶
↓
+---+
| 4 |
+---+
| 3 |
+---+
| 2 |
+---+
| 1 |
+---+
Pop() 后：
栈顶
↓
+---+
| 3 |
+---+
| 2 |
+---+
| 1 |
+---+
3. 获取栈顶元素 Top
获取栈顶元素只是查看，不删除。
Top() 返回 4
注意：
Top 不改变栈结构
Pop 才会真正删除栈顶元素
四、栈为什么适合用数组实现？
栈可以用两种方式实现：
数组
链表
但是在大多数基础实现中，数组实现栈更常见。
原因是：
栈只在栈顶插入和删除，而数组尾部插入删除的代价很低。
1. 用数组尾部作为栈顶
假设数组如下：
下标： 0 1 2 3 4
数据：10 20 30
我们可以让数组尾部作为栈顶：
栈底 栈顶
↓ ↓
+----+----+----+----+----+
| 10 | 20 | 30 | | |
+----+----+----+----+----+
0 1 2 3 4
top = 3
这里 top 表示下一个可以插入的位置。
也就是说：
有效数据范围：[0, top - 1]
栈顶元素下标：top - 1
2. 入栈就是尾插
a[top] = x;
top++;
3. 出栈就是 top–
top--;
不需要移动数据。
所以数组实现栈时，入栈和出栈都非常高效。
五、动态栈的结构设计
静态栈可以用定长数组实现：
#define N 10
typedef int STDataType;
typedef struct Stack
{
STDataType a[N];
int top;
} Stack;
但是静态栈的问题很明显：
空间给少了，不够用
空间给多了，浪费
容量固定，不能灵活增长
所以实际学习中更推荐实现动态栈。
动态栈结构
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
} Stack;
三个成员分别表示：
| 成员 | 含义 |
|---|---|
a |
指向动态数组 |
top |
栈顶位置，也表示有效元素个数 |
capacity |
当前容量 |
top 的两种常见设计
栈顶变量 top 常见有两种设计方式：
1. top 指向栈顶元素
2. top 指向栈顶元素的下一个位置
本文采用第二种：
top 指向栈顶元素的下一个位置
好处是：
top 天然表示元素个数
入栈：a[top++] = x
出栈：top--
栈顶元素：a[top - 1]
六、动态栈完整代码实现
下面给出一个比较标准的 C 语言动态栈实现。
1. Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
} Stack;
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, STDataType x);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
int StackEmpty(Stack* ps);
2. Stack.c
#include "Stack.h"
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
3. 测试代码
#include "Stack.h"
int main()
{
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestroy(&st);
return 0;
}
输出结果：
4 3 2 1
这正好体现了栈的特点：
后进先出
4. 栈操作复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
入栈 Push |
均摊 O(1) | 扩容时需要搬移数据 |
出栈 Pop |
O(1) | 只需要 top-- |
获取栈顶 Top |
O(1) | 直接访问 a[top - 1] |
判空 Empty |
O(1) | 判断 top == 0 |
获取大小 Size |
O(1) | 直接返回 top |
七、什么是队列？
队列也是一种特殊的线性表。
它只允许在一端插入数据，在另一端删除数据。
插入的一端叫：
队尾
删除的一端叫：
队头
队列遵循：
先进先出 FIFO
队列图解
出队方向 入队方向
← ←
+----+----+----+----+----+
| 10 | 20 | 30 | 40 | 50 |
+----+----+----+----+----+
↑ ↑
队头 队尾
如果现在出队，出来的是：
10
因为 10 最早进入队列。
如果现在入队 60，则插入到队尾：
+----+----+----+----+----+----+
| 10 | 20 | 30 | 40 | 50 | 60 |
+----+----+----+----+----+----+
八、队列的核心操作
队列常见操作如下：
| 操作 | 含义 |
|---|---|
QueueInit |
初始化队列 |
QueuePush |
入队 |
QueuePop |
出队 |
QueueFront |
获取队头元素 |
QueueBack |
获取队尾元素 |
QueueSize |
获取队列元素个数 |
QueueEmpty |
判断队列是否为空 |
QueueDestroy |
销毁队列 |
1. 入队 Push
入队就是在队尾插入数据。
原队列：
队头 队尾
↓ ↓
10 -> 20 -> 30 -> NULL
QueuePush(40) 后：
队头 队尾
↓ ↓
10 -> 20 -> 30 -> 40 -> NULL
2. 出队 Pop
出队就是删除队头数据。
原队列：
队头 队尾
↓ ↓
10 -> 20 -> 30 -> 40 -> NULL
QueuePop() 后：
队头 队尾
↓ ↓
20 -> 30 -> 40 -> NULL
3. 获取队头和队尾
QueueFront：返回队头元素
QueueBack：返回队尾元素
注意：
Front 和 Back 只是查看，不删除。
Pop 才会删除队头元素。
九、队列为什么更适合用链表实现？
队列可以用数组实现，也可以用链表实现。
但是如果直接用普通数组实现队列，会遇到一个问题：
出队发生在数组头部，删除头部元素后，后面的元素如果整体前移，效率会很低。
比如：
原数组：
+----+----+----+----+
| 10 | 20 | 30 | 40 |
+----+----+----+----+
出队删除 10 后，如果保持数据从下标 0 开始连续，就要把 20、30、40 都往前挪。
+----+----+----+----+
| 20 | 30 | 40 | |
+----+----+----+----+
这个移动成本是：
O(n)
链表实现队列的优势
链表队列只需要维护两个指针：
front：队头
rear：队尾
入队时尾插。
出队时头删。
如果维护了队尾指针，那么：
入队 O(1)
出队 O(1)
所以链式队列非常适合队列这种一头进、一头出的结构。
十、链式队列的结构设计
链式队列需要两类结构：
1. 队列节点
2. 队列管理结构
1. 队列节点
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
} QNode;
每个节点包含：
data：当前节点保存的数据
next：下一个节点地址
2. 队列管理结构
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;
} Queue;
这里比基础版本多维护了一个 size。
这样可以让 QueueSize 直接 O(1) 返回。
| 成员 | 含义 |
|---|---|
front |
指向队头节点 |
rear |
指向队尾节点 |
size |
队列中有效元素个数 |
链式队列图解
Queue
+--------+-------+------+
| front | rear | size |
+--------+-------+------+
| |
v v
+----+------+ +----+------+ +----+------+
| 10 | next | -> | 20 | next | -> | 30 | NULL |
+----+------+ +----+------+ +----+------+
队头 队尾
十一、链式队列完整代码实现
1. Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
} QNode;
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;
} Queue;
void QueueInit(Queue* q);
void QueueDestroy(Queue* q);
void QueuePush(Queue* q, QDataType x);
void QueuePop(Queue* q);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
int QueueEmpty(Queue* q);
2. Queue.c
#include "Queue.h"
void QueueInit(Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
void QueuePush(Queue* q, QDataType x)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (q->rear == NULL)
{
q->front = newnode;
q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;
}
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
QNode* del = q->front;
q->front = q->front->next;
free(del);
q->size--;
if (q->front == NULL)
{
q->rear = NULL;
}
}
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->rear->data;
}
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL;
}
3. 测试代码
#include "Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
return 0;
}
输出结果：
1 2 3 4
这正好体现了队列的特点：
先进先出
4. 队列操作复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
入队 QueuePush |
O(1) | 尾插，直接通过 rear 找到队尾 |
出队 QueuePop |
O(1) | 头删，直接移动 front |
获取队头 QueueFront |
O(1) | 直接访问 front->data |
获取队尾 QueueBack |
O(1) | 直接访问 rear->data |
判空 QueueEmpty |
O(1) | 判断 front == NULL |
获取大小 QueueSize |
O(1) | 因为额外维护了 size |
十二、循环队列：数组如何高效实现队列？
前面说普通数组实现队列时，如果每次出队都移动元素，效率很低。
那数组是不是不能实现队列？
不是。
只要使用：
循环队列
数组也可以高效实现队列。
1. 什么是循环队列？
循环队列可以理解成：
把数组首尾相接，看成一个环。
当 rear 走到数组末尾后，下一个位置可以回到下标 0。
2. 循环队列的核心公式
假设数组容量为 N。
下一个位置可以这样计算：
next = (index + 1) % N;
例如：
N = 5
index = 4
next = (4 + 1) % 5 = 0
这样就实现了从末尾回到开头。
3. 为什么循环队列要区分空和满？
如果只用 front == rear 判断队列状态，会出现一个问题：
空队列时：front == rear
满队列时：front 也可能 == rear
这样就无法区分空和满。
4. 常见解决方案一：浪费一个空间
最经典的做法是：
故意空出一个位置不用。
判断空：
front == rear
判断满：
(rear + 1) % N == front
有效元素个数：
(rear - front + N) % N
图解：
空队列：
front
↓
+----+----+----+----+----+
| | | | | |
+----+----+----+----+----+
↑
rear
满队列：
rear
↓
+----+----+----+----+----+
| | A | B | C | D |
+----+----+----+----+----+
↑
front
判断满：
(rear + 1) % N == front
5. 常见解决方案二：额外维护 size
也可以额外维护一个 size。
typedef struct CircularQueue
{
int* data;
int front;
int rear;
int size;
int capacity;
} CircularQueue;
这样：
size == 0 表示空
size == capacity 表示满
这种写法理解起来更直观，但需要额外维护 size。
6. 循环队列常见应用
循环队列常用于：
生产者消费者模型
缓冲区
消息队列
键盘输入缓冲
网络数据缓冲
操作系统任务调度
它适合这种场景：
数据不断进入
数据不断出去
存储空间可以重复利用
十三、栈和队列的对比
栈和队列都是受限制的线性表，但规则完全不同。
| 对比项 | 栈 | 队列 |
|---|---|---|
| 英文 | Stack | Queue |
| 规则 | 后进先出 | 先进先出 |
| 缩写 | LIFO | FIFO |
| 插入位置 | 栈顶 | 队尾 |
| 删除位置 | 栈顶 | 队头 |
| 常用实现 | 动态数组 | 链表 / 循环数组 |
| 典型操作 | Push / Pop / Top | Push / Pop / Front / Back |
十四、栈和队列的典型应用场景
1. 栈的应用
函数调用栈
函数调用天然符合栈结构。
比如：
main()
{
A();
}
A()
{
B();
}
B()
{
C();
}
调用过程：
main -> A -> B -> C
返回过程：
C -> B -> A -> main
最后调用的函数最先返回，这就是后进先出。
撤销操作
比如编辑器中连续输入：
A
B
C
按撤销时，一般先撤销 C。
因为 C 是最后一次操作。
这就是栈。
浏览器返回
访问页面顺序：
页面1 -> 页面2 -> 页面3
点击返回：
页面3 -> 页面2 -> 页面1
也符合栈的思想。
表达式处理
在表达式求值、中缀转后缀、括号结构分析中，栈非常常见。
比如：
(1 + 2) * 3
括号、运算符优先级等都可以借助栈处理。
2. 队列的应用
排队系统
最经典的队列场景就是排队。
先来的人先服务
后到的人后服务
打印任务队列
多个文件提交打印时，通常按照提交顺序处理。
任务1 -> 任务2 -> 任务3
先提交的先打印。
操作系统任务调度
操作系统中经常会维护各种任务队列。
例如：
就绪队列
阻塞队列
消息队列
广度优先搜索 BFS
图和树的广度优先搜索通常使用队列。
思想是：
先访问距离近的节点
再访问距离远的节点
这符合 FIFO。
生产者消费者模型
生产者不断生产数据，消费者不断取出数据。
中间常用队列作为缓冲区。
生产者 -> 队列缓冲区 -> 消费者
如果缓冲区用固定数组实现，就经常会用到循环队列。
十五、栈和队列常见易错点
1. 空栈不能 Pop 或 Top
错误：
StackPop(&st);
StackTop(&st);
如果栈为空，不能出栈，也不能取栈顶。
所以要加断言：
assert(!StackEmpty(ps));
2. 空队列不能 Pop、Front、Back
队列为空时，下面操作都不合法：
QueuePop(&q);
QueueFront(&q);
QueueBack(&q);
必须先判断非空。
3. 栈的 top 含义要统一
如果你设计：
top 指向栈顶元素
代码会是一种写法。
如果你设计：
top 指向栈顶元素的下一个位置
代码又是另一种写法。
本文采用的是：
top 指向栈顶元素的下一个位置
所以：
栈顶元素 = a[top - 1];
元素个数 = top;
写代码时一定要保持统一。
4. 队列出队后要处理 rear
链式队列中，如果删除的是最后一个节点，删除后：
front == NULL
此时必须同步让：
rear = NULL;
否则 rear 会变成野指针。
正确写法：
if (q->front == NULL)
{
q->rear = NULL;
}
5. malloc 后要检查返回值
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
动态内存申请失败时，如果不检查，后面直接解引用会出问题。
6. 销毁时要释放所有节点
链式队列中每个节点都是动态申请的。
销毁时必须一个个释放。
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
否则会造成内存泄漏。
7. 循环队列容易写错取模
循环队列中，指针往后走不能简单写：
rear++;
应该写：
rear = (rear + 1) % capacity;
这样才能从数组末尾回到开头。
全文总结
栈和队列都是非常经典的线性数据结构。
它们和顺序表、链表最大的区别是：
顺序表和链表更关注底层如何存储
栈和队列更关注数据如何进出
栈的核心
栈：只允许在栈顶插入和删除
规则：后进先出 LIFO
常用实现：动态数组
核心操作：Push、Pop、Top
队列的核心
队列：队尾插入，队头删除
规则：先进先出 FIFO
常用实现：链表或循环数组
核心操作：Push、Pop、Front、Back
循环队列的核心
循环队列本质是：
把数组当成环来使用
核心公式：
next = (index + 1) % capacity;
它解决了普通数组队列出队后空间不能高效复用的问题。
栈和队列看起来简单，但它们背后的思想非常重要。
栈适合处理：
需要回退、反向恢复、后进先出的场景
队列适合处理：
需要排队、公平调度、先进先出的场景
当你以后学习树、图、操作系统、编译原理、网络缓冲区时，会发现栈和队列几乎无处不在。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
15
0- 0
已为社区贡献6条内容
所有评论(0)