栈与队列 C/C++ 代码实现对比：顺序栈、链队 5 种结构 20 个核心函数

栈与队列 C/C 代码实现对比顺序栈、链队 5 种结构 20 个核心函数1. 数据结构基础与核心概念在计算机科学中栈和队列是两种最基本且重要的线性数据结构。它们的核心区别在于数据元素的进出顺序栈遵循后进先出(LIFO)原则而队列遵循先进先出(FIFO)原则。这两种结构在操作系统、编译器、网络协议等底层系统中有着广泛应用。栈的核心特性只允许在表的一端栈顶进行插入和删除操作基本操作包括push压栈、pop弹栈、peek查看栈顶元素典型应用场景函数调用栈、表达式求值、括号匹配、递归实现队列的核心特性允许在表的一端队尾插入另一端队头删除基本操作包括enqueue入队、dequeue出队、front获取队头元素典型应用场景CPU任务调度、打印机队列、消息队列系统// 栈的抽象数据类型定义 typedef struct { ElemType *data; // 存储空间基址 int top; // 栈顶指针 int capacity; // 最大容量 } Stack; // 队列的抽象数据类型定义 typedef struct { ElemType *data; // 存储空间基址 int front; // 队头指针 int rear; // 队尾指针 int capacity; // 最大容量 } Queue;2. 顺序栈的实现与优化顺序栈采用数组作为底层存储结构具有内存连续、访问快速的优点。以下是完整实现#define INIT_SIZE 10 #define INCREMENT 5 // 顺序栈结构定义 typedef struct { int *base; // 栈底指针 int *top; // 栈顶指针 int size; // 当前分配的空间大小 } SqStack; // 初始化栈 Status InitStack(SqStack *S) { S-base (int*)malloc(INIT_SIZE * sizeof(int)); if (!S-base) return ERROR; S-top S-base; S-size INIT_SIZE; return OK; } // 入栈操作 Status Push(SqStack *S, int e) { if (S-top - S-base S-size) { // 栈满扩容 int *newbase (int*)realloc(S-base, (S-size INCREMENT) * sizeof(int)); if (!newbase) return ERROR; S-base newbase; S-top S-base S-size; S-size INCREMENT; } *S-top e; return OK; } // 出栈操作 Status Pop(SqStack *S, int *e) { if (S-top S-base) return ERROR; // 栈空 *e *(--S-top); return OK; } // 获取栈顶元素 Status GetTop(SqStack S, int *e) { if (S.top S.base) return ERROR; *e *(S.top - 1); return OK; } // 销毁栈 void DestroyStack(SqStack *S) { free(S-base); S-base S-top NULL; S-size 0; }顺序栈的优化技巧动态扩容当栈满时自动扩大存储空间如代码中的realloc共享栈两个栈共享同一存储空间分别从数组两端向中间生长内存预分配对于已知最大容量的场景可预先分配足够空间避免动态扩容开销// 共享栈的实现 typedef struct { ElemType data[MAXSIZE]; int top1; // 栈1栈顶指针 int top2; // 栈2栈顶指针 } SharedStack; void InitSharedStack(SharedStack *S) { S-top1 -1; S-top2 MAXSIZE; }3. 链式队列的完整实现链式队列使用链表作为存储结构避免了顺序存储的容量限制问题// 链队结点定义 typedef struct QNode { int data; struct QNode *next; } QNode; // 链队结构定义 typedef struct { QNode *front; // 队头指针 QNode *rear; // 队尾指针 int count; // 元素计数器 } LinkedQueue; // 初始化队列 void InitQueue(LinkedQueue *Q) { Q-front Q-rear (QNode*)malloc(sizeof(QNode)); if (!Q-front) exit(ERROR); Q-front-next NULL; Q-count 0; } // 入队操作 void EnQueue(LinkedQueue *Q, int e) { QNode *p (QNode*)malloc(sizeof(QNode)); if (!p) exit(ERROR); p-data e; p-next NULL; Q-rear-next p; Q-rear p; Q-count; } // 出队操作 int DeQueue(LinkedQueue *Q, int *e) { if (Q-front Q-rear) return ERROR; QNode *p Q-front-next; *e p-data; Q-front-next p-next; if (Q-rear p) Q-rear Q-front; // 最后一个元素出队 free(p); Q-count--; return OK; } // 获取队头元素 int GetHead(LinkedQueue Q, int *e) { if (Q.front Q.rear) return ERROR; *e Q.front-next-data; return OK; } // 销毁队列 void DestroyQueue(LinkedQueue *Q) { while (Q-front) { Q-rear Q-front-next; free(Q-front); Q-front Q-rear; } Q-count 0; }链队性能分析入队操作O(1)时间复杂度只需修改尾指针出队操作O(1)时间复杂度只需修改头指针空间利用率每个元素需要额外指针空间但无容量限制4. 循环队列的实现细节循环队列解决顺序队列假溢出问题通过取模运算实现逻辑上的循环#define MAXQSIZE 100 typedef struct { int *base; // 存储空间基址 int front; // 头指针 int rear; // 尾指针 int flag; // 队列空/满标志位 } CircularQueue; // 初始化循环队列 Status InitQueue(CircularQueue *Q) { Q-base (int*)malloc(MAXQSIZE * sizeof(int)); if (!Q-base) return ERROR; Q-front Q-rear 0; Q-flag 0; // 0表示空队列 return OK; } // 入队操作 Status EnQueue(CircularQueue *Q, int e) { if (Q-front Q-rear Q-flag 1) return ERROR; // 队满 Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXQSIZE; Q-flag (Q-rear Q-front) ? 1 : Q-flag; return OK; } // 出队操作 Status DeQueue(CircularQueue *Q, int *e) { if (Q-front Q-rear Q-flag 0) return ERROR; // 队空 *e Q-base[Q-front]; Q-front (Q-front 1) % MAXQSIZE; Q-flag 0; // 出队后队列至少有一个空位 return OK; } // 队列长度计算 int QueueLength(CircularQueue Q) { if (Q.front Q.rear) return Q.flag ? MAXQSIZE : 0; return (Q.rear - Q.front MAXQSIZE) % MAXQSIZE; }循环队列的三种判满策略对比策略类型实现方式优点缺点牺牲一个单元(rear1)%MAXSIZE front实现简单浪费一个存储单元增加标志位frontrear flag1不浪费空间需要维护标志位记录元素个数countMAXSIZE逻辑清晰需要额外存储空间5. 双端队列与特殊变种双端队列(Deque)允许在队列两端进行插入和删除操作具有更大的灵活性typedef struct { int *data; // 存储空间基址 int front; // 队头指针 int rear; // 队尾指针 int capacity; // 队列容量 } Deque; // 前端插入 Status PushFront(Deque *D, int e) { if ((D-rear 1) % D-capacity D-front) return ERROR; // 队满 D-front (D-front - 1 D-capacity) % D-capacity; D-data[D-front] e; return OK; } // 后端插入 Status PushBack(Deque *D, int e) { if ((D-rear 1) % D-capacity D-front) return ERROR; // 队满 D-data[D-rear] e; D-rear (D-rear 1) % D-capacity; return OK; } // 前端删除 Status PopFront(Deque *D, int *e) { if (D-front D-rear) return ERROR; // 队空 *e D-data[D-front]; D-front (D-front 1) % D-capacity; return OK; } // 后端删除 Status PopBack(Deque *D, int *e) { if (D-front D-rear) return ERROR; // 队空 D-rear (D-rear - 1 D-capacity) % D-capacity; *e D-data[D-rear]; return OK; }双端队列的四种特殊变种输入受限双端队列只能在一端插入但两端都可删除输出受限双端队列只能在一端删除但两端都可插入优先队列元素带有优先级高优先级先出通常用堆实现阻塞队列当队列空时获取操作会被阻塞队列满时插入操作会被阻塞6. 五种结构的综合对比通过表格对比五种实现方式的关键特性结构类型存储方式核心操作时间复杂度空间复杂度适用场景顺序栈数组O(1)O(n)已知最大容量或可预估的场景链栈链表O(1)O(n)频繁动态增长缩小的场景循环队列数组O(1)O(n)固定大小的缓冲区管理链队链表O(1)O(n)频繁入队出队的动态场景双端队列数组/链表O(1)O(n)需要两端操作的复杂场景内存布局对比顺序结构顺序栈、循环队列内存连续缓存友好需要预先分配固定空间插入删除可能引起数据移动链式结构链栈、链队内存不连续额外指针开销动态分配无固定大小限制插入删除只需修改指针7. 典型应用场景与实战案例栈的经典应用表达式求值// 中缀表达式转后缀表达式 vectorstring infixToPostfix(const string expr) { vectorstring output; stackchar opStack; unordered_mapchar, int precedence { {, 1}, {-, 1}, {*, 2}, {/, 2}, {^, 3} }; string num; for (char c : expr) { if (isdigit(c)) { num c; } else { if (!num.empty()) { output.push_back(num); num.clear(); } if (c () { opStack.push(c); } else if (c )) { while (!opStack.empty() opStack.top() ! () { output.push_back(string(1, opStack.top())); opStack.pop(); } opStack.pop(); // 弹出( } else if (precedence.count(c)) { while (!opStack.empty() opStack.top() ! ( precedence[opStack.top()] precedence[c]) { output.push_back(string(1, opStack.top())); opStack.pop(); } opStack.push(c); } } } if (!num.empty()) output.push_back(num); while (!opStack.empty()) { output.push_back(string(1, opStack.top())); opStack.pop(); } return output; }队列的经典应用二叉树的层次遍历typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; void LevelOrderTraversal(TreeNode *root) { if (!root) return; LinkedQueue Q; InitQueue(Q); EnQueue(Q, (int)root); while (Q.front ! Q.rear) { TreeNode *node; DeQueue(Q, (int*)node); printf(%d , node-val); if (node-left) EnQueue(Q, (int)node-left); if (node-right) EnQueue(Q, (int)node-right); } DestroyQueue(Q); }8. 考研真题分析与解题技巧常见考点总结栈的合法出栈序列判断如选择题给出入栈序列判断哪个出栈序列不可能循环队列的队空、队满条件及元素个数计算双端队列的输出序列合法性分析栈在递归中的应用及递归转非递归的实现特殊矩阵的压缩存储与下标计算解题技巧对于栈序列问题可以模拟入栈出栈过程循环队列长度公式(rear - front MAXSIZE) % MAXSIZE共享栈的栈满条件top1 1 top2递归算法改非递归时通常需要显式使用栈来保存中间状态// 递归阶乘函数 int Factorial(int n) { if (n 0) return 1; return n * Factorial(n - 1); } // 非递归实现使用栈 int Factorial_Iter(int n) { SqStack S; InitStack(S); int result 1; while (n 0) { Push(S, n); n--; } while (!StackEmpty(S)) { int x; Pop(S, x); result * x; } DestroyStack(S); return result; }在实际项目开发中栈和队列的选择需要综合考虑数据规模、访问模式、性能要求等因素。顺序结构适合数据量固定或可预估的场景而链式结构更适合频繁动态变化的场景。理解这些底层实现原理对于设计高效算法和优化系统性能至关重要。