栈与队列 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; }循环队列的三种判满策略对比：
| 策略类型 | 实现方式 | 优点 | 缺点 |
|---|---|---|---|
| 牺牲一个单元 | (rear+1)%MAXSIZE == front | 实现简单 | 浪费一个存储单元 |
| 增加标志位 | front==rear && flag==1 | 不浪费空间 | 需要维护标志位 |
| 记录元素个数 | count==MAXSIZE | 逻辑清晰 | 需要额外存储空间 |
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. 典型应用场景与实战案例
栈的经典应用：表达式求值
// 中缀表达式转后缀表达式 vector<string> infixToPostfix(const string& expr) { vector<string> output; stack<char> opStack; unordered_map<char, 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; }在实际项目开发中，栈和队列的选择需要综合考虑数据规模、访问模式、性能要求等因素。顺序结构适合数据量固定或可预估的场景，而链式结构更适合频繁动态变化的场景。理解这些底层实现原理，对于设计高效算法和优化系统性能至关重要。
