Days 22栈与队列

一、前言

程序 = 数据结构 + 算法，栈和队列是开发中最基础、高频使用的受限线性表。 数组 / 普通链表可以在任意位置增删元素，而栈、队列严格限制操作位置：

• 栈：后进先出 LIFO，仅栈顶插入、删除
• 队列：先进先出 FIFO，队尾入队、队头出队

本文基于 Linux+C 语言实现，包含顺序栈、链式栈、循环队列、链式队列全套代码，配套内存图解、易错点分析，适合期末复习、面试基础复习。

二、栈（Stack）核心理论

2.1 栈核心规则

1. 操作端只有栈顶，栈底固定；
2. 入栈 (Push)：数据放到栈顶；出栈 (Pop)：只取出栈顶元素；
3. 判空：无有效元素；判满（仅顺序栈存在）：数组空间用完；
4. 两种实现：顺序栈（连续数组）、链栈（动态节点，无容量上限）

2.2 顺序栈（数组实现）

1. 结构体设计

c

运行

typedef int DataType; typedef struct{ DataType *pData; // 动态数组，存放栈数据 int tLen; // 栈最大容量 int Top; // 栈针：指向下一个待写入位置，Top=0代表空栈 }Stack_t;

内存图解：pData是堆区连续内存，Top 记录当前栈元素个数；

• 空栈：Top == 0
• 满栈：Top == tLen

2. 完整 seqstack.h 头文件

c

运行

#ifndef __SEQSTACK_H__ #define __SEQSTACK_H__ typedef int DataType; typedef struct{ DataType *pData; int tLen; int Top; }Stack_t; // 创建栈，指定最大容量 extern Stack_t *CreateSeqStack(int Len); // 判断栈空 extern int IsEmptySeqStack(Stack_t *pTmpStack); // 判断栈满 extern int IsFullSeqStack(Stack_t *pTmpStack); // 入栈 extern int PushSeqStack(Stack_t *pTmpStack, DataType TmpData); // 出栈，返回栈顶值 extern DataType PopSeqStack(Stack_t *pTmpStack); // 销毁栈（二级指针避免野指针） extern int DestroySeqStack(Stack_t **ppTmpStack); #endif

3. seqstack.c 功能实现

c

运行

#include "seqstack.h" #include <stdio.h> #include <stdlib.h> // 创建顺序栈 Stack_t *CreateSeqStack(int Len) { Stack_t *pTmpStack = (Stack_t *)malloc(sizeof(Stack_t)); if (NULL == pTmpStack) { perror("栈结构体申请失败"); return NULL; } pTmpStack->tLen = Len; pTmpStack->Top = 0; pTmpStack->pData = (DataType *)malloc(sizeof(DataType) * Len); if (NULL == pTmpStack->pData) { perror("数组空间申请失败"); free(pTmpStack); return NULL; } return pTmpStack; } // 判断栈空 int IsEmptySeqStack(Stack_t *pTmpStack) { return pTmpStack->Top == 0; } // 判断栈满 int IsFullSeqStack(Stack_t *pTmpStack) { return pTmpStack->Top == pTmpStack->tLen; } // 入栈 int PushSeqStack(Stack_t *pTmpStack, DataType TmpData) { if (IsFullSeqStack(pTmpStack)) { printf("栈已满，无法入栈\n"); return -1; } pTmpStack->pData[pTmpStack->Top] = TmpData; pTmpStack->Top++; return 0; } // 出栈：先存数据再释放/移动栈针，禁止free后取值 DataType PopSeqStack(Stack_t *pTmpStack) { if (IsEmptySeqStack(pTmpStack)) { printf("栈为空，无法出栈\n"); return 0; } pTmpStack->Top--; return pTmpStack->pData[pTmpStack->Top]; } // 销毁栈 int DestroySeqStack(Stack_t **ppTmpStack) { if (NULL == ppTmpStack || NULL == *ppTmpStack) return -1; free((*ppTmpStack)->pData); free(*ppTmpStack); *ppTmpStack = NULL; return 0; }

4. main.c 测试代码

c

运行

#include "seqstack.h" #include <stdio.h> int main(void) { Stack_t *pseq = CreateSeqStack(10); // 入栈1~5 for(int i=1;i<=5;i++) PushSeqStack(pseq, i); // 出栈打印：后进先出 5 4 3 2 1 while(!IsEmptySeqStack(pseq)) printf("%d ", PopSeqStack(pseq)); DestroySeqStack(&pseq); return 0; }

5. 顺序栈优缺点

✅ 优点：随机访问栈顶、内存连续、读写速度快； ❌ 缺点：容量固定，扩容麻烦，空间不足会栈满；闲置数组会内存浪费。

2.3 链式栈（链表实现，无容量限制）

1. 节点结构（带哨兵头节点）

c

运行

typedef int DataType; typedef struct Node{ DataType data; struct Node *pNext; }Node_t;

设计思路：头插法，头节点pNext直接指向栈顶，入栈出栈仅操作头节点后第一个节点，时间复杂度 O (1)。

• 空栈：pHead->pNext == NULL
• 无需判满，堆内存足够可无限入栈

2. 链栈核心实现关键（易错点）

出栈逻辑必须遵循：

1. 保存栈顶节点指针
2. 提前取出节点 data
3. 断开头节点与栈顶连接
4. free 释放节点

禁止先 free 再读取 data，释放后内存失效，程序段错误！

完整链栈 Push/Pop 示例：

c

运行

// 入栈 int PushLinkStack(Node_t *pHead, DataType val) { Node_t *pNew = (Node_t*)malloc(sizeof(Node_t)); if(!pNew) return -1; pNew->data = val; pNew->pNext = pHead->pNext; pHead->pNext = pNew; return 0; } // 出栈 DataType PopLinkStack(Node_t *pHead) { if(pHead->pNext == NULL) { printf("链栈空\n"); return 0; } Node_t *pDel = pHead->pNext; DataType res = pDel->data; // 先存数据！ pHead->pNext = pDel->pNext; free(pDel); return res; }

链栈优缺点

✅ 无容量上限、按需分配内存，无空间浪费； ❌ 每个节点附带指针，额外消耗内存，无法随机访问。

三、队列（Queue）核心理论

3.1 队列规则

先进先出 FIFO：只能队尾插入（入队 Enter）、队头删除（出队 Quit） 两种实现：循环顺序队列（解决普通顺序队列假溢出）、链式队列

3.2 循环顺序队列

普通数组队列会出现假溢出：队头元素出队后，前面空间闲置但无法入队；循环队列通过取模(rear+1)%maxlen实现环形复用。 判空：front == rear判满：(rear+1)%maxlen == front（牺牲一格空间区分空 / 满）

3.3 链式队列

双指针设计：头指针 front（出队）、尾指针 rear（入队），入队操作尾指针，出队操作头指针，无假溢出、无容量限制。

四、栈和队列对比总结

表格

五、高频面试 / 期末易错点

1. 顺序栈出栈：不能 free 后取值，必须先保存 data；
2. 链栈统一头插法，栈顶是头节点后继；
3. 循环队列判满条件(rear+1)%len == front，不可直接rear==front；
4. 销毁容器使用二级指针，将外部指针置 NULL，杜绝野指针；
5. 栈：函数调用栈、表达式求值、括号匹配；队列：消息队列、任务调度、广度优先搜索 (BFS)。

六、Linux 编译运行命令

以顺序栈为例：

bash

# 编译 gcc main.c seqstack.c -o stack -g # 运行 ./stack # gdb调试段错误 gdb ./stack # valgrind检测内存泄露 valgrind --tool=memcheck ./stack

七、结尾

栈和队列是二叉树、图、排序算法的基础容器，建议手动完整敲一遍两套栈 + 两套队列代码，吃透内存分配、指针操作、边界判空判满逻辑，后续学习复杂数据结构会事半功倍。