深入栈与队列的概念和底层结构实现（数组 vs 链表）

前言

——栈和队列是计算机科学中最基础、最常用的两种抽象数据类型。几乎每个程序员都能随口说出“栈是后进先出（LIFO），队列是先进先出（FIFO）”，但在实际工程中，选择数组还是链表作为底层容器，会显著影响性能、内存占用和代码复杂度。
本期将使用C语言实现栈和队列，其主要内容包括：
1.使用头文件声明、源文件定义的形式呈现源码
2.介绍栈与队列的概念，并使用数组实现栈，链表实现队列
3.提供图例和使用链表实现栈，数组实现队列的对比表格

栈专题

一、概念

——栈是一种操作受限的线性表，只允许在固定一端进行插入和删除数据操作，进行插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据遵循后进先出原则(LIFO:List In First Out)
栈的插入操作被称为：进栈，入栈，压栈，在栈顶插入
栈的删除操作被称为：出栈，在栈顶删除
生活中的实例：空羽毛球桶，第一个被放入的羽毛球最后一个被取出，最后一个被放入的羽毛球第一个被取出(在不暴力拆除桶底的情况下(￣▽￣)")
注：说了这么多，但总结来看数据结构栈的本质还是数组，只是操作受限
数据结构栈的物理结构和逻辑结构示例图：

二、代码实现

准备

前置知识：

• assert()函数介绍
  C语言标准库中的调试宏，用于在程序运行时检查条件是否成立。若条件为假（0），则输出错误信息（文件、行号、表达式）并调用 abort()终止程序，若条件为真（非0），则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等
• perror()函数介绍
  C 语言标准库函数，用于打印错误信息。调用格式：perror(“前缀字符串”)，输出格式为“前缀字符串：错误原因\n”，常用于系统调用或库函数失败后，快速定位错误原因
• exit()函数介绍
  C 语言标准库函数，用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统（0or EXIT_SUCCESS表示成功，-1or EXIT_FAILURE表示失败）
• 布尔值
  C语言并不自带布尔值作为内置数据类型，使用需引入标准库<stdbool.h>

头文件内容总览

注：代码部分如果直接复制不能成功运行，请将所有中文前的#替换为//

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintSTDataType;#栈typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;#初始化栈voidSTInit(ST*pst);#添加：入栈voidSTPush(ST*pst,STDataType x);#删除：出栈voidSTPop(ST*pst);#获取栈顶元素 STDataTypeSTTop(ST*pst);#判断是否为空 boolSTEmpty(ST*pst);#获取元素个数intSTSize(ST*pst);#销毁栈voidSTDestroy(ST*pst);

栈的属性有使用动态开辟的数组 arr，用于指向栈顶的指针 top 和用于存储数组当前容量的 capacity。栈从逻辑上操作受限，因此除基础的初始化和销毁外只能从栈顶入栈和出栈，不能在指定位置插入或删除元素，也只能获取当前栈顶的元素。除此之外还有两个判断栈信息的函数用于确定栈是否为空以及返回当前栈内的元素个数

初始化

voidSTInit(ST*pst){assert(pst);pst->arr=NULL;pst->top=0;pst->capacity=0;}

传入栈，并断言传入的指针不为 NULL
关于 top 的初始化有一个重要的点涉及到后续操作的逻辑控制，如果 top 指向栈顶，则需将 top 初始化为 -1，如果初始化为零会出现 top 为零时无法判断当前栈中是否还有元素的问题。如果 top 指向栈顶元素的下一个位置，就将其初始化为零，这种写法便于判满、入栈和返回元素个数

判断空间容量

voidSTCheckCapacity(ST*pst){if(pst->top==pst->capacity){intnewcapacity=(pst->capacity==0?4:pst->capacity*2);STDataType*tmp=(STDataType*)realloc(pst->arr,newcapacity*sizeof(STDataType));if(tmp==NULL){perror("realloc fail");exit(1);}pst->arr=tmp;pst->capacity=newcapacity;}}

当 top 等于 capacity 时需动态扩容，当第一次扩容时初始化容量为4，否则扩容为当前容量的二倍，扩容后需判断是否扩容成功，失败返回提示信息后退出程序，成功时再执行更新操作

添加：入栈

voidSTPush(ST*pst,STDataType x){assert(pst);STCheckCapacity(pst);#入栈 pst->arr[pst->top++]=x;}

传入栈与要添加的元素，断言传入指针不为 NULL，判断容量
与顺序表相同，在数组尾插数据并让 top++

删除：出栈

voidSTPop(ST*pst){assert(pst&&pst->top);#出栈 pst->top--;}

传入栈，断言传入指针不为 NULL 且栈中元素个数不为0
与顺序表相同，使 top-- 就能达到逻辑删除

获取栈顶元素

STDataTypeSTTop(ST*pst){assert(pst&&pst->top);#获取栈顶元素returnpst->arr[pst->top-1];}

传入栈，断言传入指针不为 NULL 且栈中元素个数不为0
top 指向栈顶的下一个位置，可以利用 top - 1 找到并返回栈顶元素

判断是否为空

boolSTEmpty(ST*pst){assert(pst);#判断是否为空returnpst->top==0;}

传入栈，断言传入指针不为 NULL
在数组中，能根据每个元素的下标位置确定在这个元素前还有几个元素，例如下标为3的元素，它的前面就刚好有3个值，所以，我们同样可以根据 top 是否指向栈底判断栈是否为空，为空返回 true，否则返回 false

获取元素个数

intSTSize(ST*pst){assert(pst);#获取元素个数returnpst->top;}

传入栈，断言传入指针不为 NULL
同上，top 指向栈顶元素的下一个位置，因此就为当前栈中的元素个数

销毁栈

voidSTDestroy(ST*pst){assert(pst);free(pst->arr);pst->arr=NULL;pst->top=pst->capacity=0;}

传入栈，断言传入指针不为 NULL
释放栈在堆区开辟的动态空间并将指针初始化，初始化 top 和容量

一份测试代码

voidTest_Stack(){ST s;#初始化测试STInit(&s);#入栈测试STPush(&s,4);STPush(&s,3);STPush(&s,2);STPush(&s,1);#出栈测试STPop(&s);STPop(&s);#获取栈顶元素测试printf("%d\n",STTop(&s));#判断是否为空测试printf("%d\n",STEmpty(&s));#获取元素个数测试printf("%d\n",STSize(&s));#销毁测试STDestroy(&s);}

总结

数组实现栈的优缺点：

队列专题

一、概念

——队列也是一种操作受限的线性表，只允许在固定一端进行插入数据操作，另一端进行删除数据操作，插入数据的一端称为队尾，删除数据的一端称为队头，队列中的数据遵循先进先出的原则(FIFO:First In First Out)
队列的插入操作被称为：入队，在队尾插入
队列的删除操作被称为：出队，在队头删除
生活中的实例：排队购买，先来的人先买到票后从队头离开，后来的人排在队尾等待，整个流程有序进行(没有人插队的情况)
数据结构队列的物理结构和逻辑结构示例图：

二、代码实现

头文件内容总览

注：代码部分如果直接复制不能成功运行，请将所有中文前的#替换为//

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintQDataType;#定义队列的节点结构typedefstructQueueNode{QDataType data;#存储值structQueueNode*next;#指向下一个节点的指针}QNode;#定义存储队列信息的结构typedefstructQueue{QNode*phead;#指向队头的指针 QNode*ptail;#指向队尾的指针intsize;#当前的元素个数}Queue;#初始化队列voidQueueInit(Queue*pq);#添加：入队voidQNodePush(Queue*pq,QDataType x);#删除：出队voidQNodePop(Queue*pq);#获取队头数据 QDataTypeQueueFront(Queue*pq);#获取队尾数据 QDataTypeQueueBack(Queue*pq);#判断是否为空 boolQueueEmpty(Queue*pq);#获取元素个数intQSize(Queue*pq);#销毁队列voidQueueDestroy(Queue*pq);

从代码看，队列无疑多用了一个结构体用于实现完整结构，该结构的作用在于明确队头和队尾在物理存储结构中的位置，使我们无需考虑操作物理结构链表时执行的额外操作，只需将重点放在对队列的操作逻辑上。与此同时，我们注意到队列中有一个名为 QSize 的函数用于获取当前队列中的元素个数，我们知道，统计整条链表的元素个数需要完整遍历获得，单次操作的时间复杂度为O(N)，为高效可以在 Queue 结构体中额外维护一个变量 size 用于记录队列中的元素个数，使 QSize 函数的时间复杂度优化为O(1)

初始化

voidQueueInit(Queue*pq){assert(pq);pq->phead=pq->ptail=NULL;pq->size=0;}

传入队列，并断言传入的指针不为 NULL
当前队列中无节点，因此将队头指针和队尾指针都置空，并使 size 初始化为0

添加：入队

voidQNodePush(Queue*pq,QDataType x){QNode*newnode=(QNode*)malloc(sizeof(QNode));if(newnode==NULL){perror("malloc fail");return;}newnode->data=x;newnode->next=NULL;#入队if(pq->ptail==NULL){pq->phead=pq->ptail=newnode;}else{pq->ptail->next=newnode;pq->ptail=newnode;}pq->size++;}

传入队列与要添加的元素，断言传入指针不为 NULL，创建新节点
分为两种情况，当队列中无任何元素时，应该将队头指针与队尾指针同时指向入队节点，否则就使当前队尾元素的 next 指向入队节点后，修改队尾指针

删除：出队

voidQNodePop(Queue*pq){assert(pq&&pq->size);#出队 #队列元素为1时删除导致队尾指针为野指针 QNode*next=pq->phead->next;free(pq->phead);if(next==NULL)pq->phead=pq->ptail=next;elsepq->phead=next;pq->size--;}

传入队列，断言传入指针不为 NULL 且队列元素个数不为0
分为队列元素个数为1和不为1两种情况，为1时在销毁队头指针指向的节点后需同时修改头尾指针指向为 NULL，不为1时只修改队头指针指向

获取队头数据

QDataTypeQueueFront(Queue*pq){assert(pq&&pq->size);#获取队头数据returnpq->phead->data;}

传入队列，断言传入指针不为 NULL 且队列元素个数不为0
直接通过队头指针返回第一个元素

获取队尾数据

QDataTypeQueueBack(Queue*pq){assert(pq&&pq->size);#获取队尾数据returnpq->ptail->data;}

传入队列，断言传入指针不为 NULL 且队列元素个数不为0
通过队尾指针返回最后一个元素

判断是否为空

boolQueueEmpty(Queue*pq){assert(pq);#判断是否为空returnpq->size==0;}

传入队列，断言传入指针不为 NULL
通过维护的变量 size 判断，为空返回 true，非空返回 false

获取元素个数

intQSize(Queue*pq){assert(pq);#获取元素个数returnpq->size;}

传入队列，断言传入指针不为 NULL
pass

销毁队列

voidQueueDestroy(Queue*pq){assert(pq);QNode*cur=pq->phead;while(cur){QNode*next=cur->next;free(cur);cur=next;}pq->phead=pq->ptail=NULL;pq->size=0;}

传入队列，断言传入指针不为 NULL
与销毁链表的流程大致相同，注意需初始化头尾指针和 size 变量

一份测试代码

voidTest_Queue(){Queue q;#初始化测试QueueInit(&q);#入队测试QNodePush(&q,1);QNodePush(&q,2);QNodePush(&q,3);QNodePush(&q,4);#出队测试QNodePop(&q);QNodePop(&q);#获取队头数据测试printf("%d\n",QueueFront(&q));#获取队尾数据测试printf("%d\n",QueueBack(&q));#判断是否为空测试printf("%d\n",QueueEmpty(&q));#获取元素个数测试printf("%d\n",QSize(&q));#销毁队列测试QueueDestroy(&q);}

总结

链表实现队列的优缺点：

三、四种实现的全面对比

方向选择

我们换位思考，先看链表实现栈的场景：
如果用表头做栈底，表尾做栈顶，则每次返回栈顶数据都需遍历链表，操作的时间复杂度为O(N)。如果用表头做栈顶，表尾做栈底，则时间复杂度不变
再看数组实现队列的场景：
使用高下标位的方向作为队头，低下标位的方向作为队尾时，执行入队操作时需整体右移元素，时间复杂度为O(N)。使用高下标位的方向作为队尾，低下标位的方向作为队头时，执行出队操作时需整体左移元素，时间复杂度为O(N)。如果两种操作均不移动元素，在使用数组实现队列时会出现假溢出问题，导致浪费空间越来越多
由此，关于栈顶、栈底、队头、队尾方向的选择问题便有了大致的概念

对比表格

为了更清晰地看到 数组 vs 链表 在栈和队列上的差异，下表从多个维度做了详细对比

——数组天生适合栈，因为栈的操作只在一端进行，数组的末尾操作O(1)且缓存命中率高，扩容成本均摊后微乎其微。链表天生适合队列，因为队列要在两端操作，链表的头删尾插均为O(1)且无需搬移元素，动态增长无容量限制。

整体总结

通过本文，你不仅掌握了栈和队列的核心概念与操作，更重要的是，我们从底层存储视角剖析了数组与链表这两种实现方式的内在权衡：
➤数组的优势在于缓存命中率高和随机访问，但扩容和搬移元素是它的代价。因此数组适合操作集中于末尾(比如栈)的场景，而在队列中需要额外设计来避免搬移元素(循环队列)。
➤链表的优势在于动态伸缩和无需搬移元素，但代价是指针占用额外空间和缓存命中率低。链表适合两端操作频繁的队列，而在实现栈中并非最优解。

四、练习

推荐以下LeetCode题目
20. 有效的括号 & 链接：link.
225. 用队列实现栈 & 链接：link.
232. 用栈实现队列 & 链接：link.

⚛️EL PSY CONGROO，十分感谢你的阅读

本期不确定：
推荐的练习题是否充足，是否“高效”