当前位置：首页 > news >正文

栈与队列：两种经典线性数据结构的深度解析

news 来源：原创 2025/9/11 9:59:44

一、栈：LIFO 特性的完美诠释

（一）核心概念与抽象模型

定义与特性
栈是一种严格遵循后进先出（LIFO）原则的线性数据结构，其操作被限制在栈顶（Top）进行。形象化理解：如同堆叠的餐盘，最后放置的餐盘最先被取用。
- 压栈（Push）：数据从栈顶插入，时间复杂度 O (1)
- 出栈（Pop）：数据从栈顶删除，时间复杂度 O (1)
- 典型场景：函数调用栈（保存调用上下文）、表达式求值（处理运算符优先级）、历史记录回退（如浏览器的 “后退” 功能）。
逻辑模型与物理结构
栈的逻辑结构是线性表，但物理实现有两种选择：
- 数组实现：利用动态数组，通过top指针记录栈顶位置（下标从 0 或 - 1 开始），适合频繁尾操作
- 链表实现：用单链表，头节点作为栈顶，插入 / 删除在头部进行，适合内存动态分配场景

（二）数组实现的工程细节（C 语言）

1. 结构体定义与初始化

typedef int STDataType;
typedef struct Stack {STDataType* data;     // 动态数组存储数据int top;              // 栈顶下标int capacity;         // 当前最大容量
} Stack;void StackInit(Stack* stack) {stack->data = (STDataType*)malloc(4 * sizeof(STDataType));if (stack->data == NULL) {        perror("malloc fali");return; // 内存分配失败处理}stack->top = 0;stack->capacity = 4;
}

2. 核心操作实现

压栈（含扩容逻辑）

void StackPush(Stack* stack, STDataType value) {// 检查是否需要扩容if (stack->top == stack->capacity - 1) {int newCapacity = stack->capacity * 2;STDataType* newData = (STDataType*)realloc(stack->data, newCapacity * sizeof(STDataType));if (newData == NULL) {perror("realloc fail");return; // 扩容失败处理}stack->data = newData;stack->capacity = newCapacity;}stack->data[stack->top++] = value;
}

出栈（需处理栈空异常）

void StackPop(Stack* stack) {if (StackEmpty(stack))return; // 空栈无法出栈stack->top--; // 直接调整指针，无需物理删除（懒删除）
}

获取栈顶元素

STDataType StackTop(Stack* stack) {if (StackEmpty(stack)) return; // 空栈访问异常return stack->data[stack->top];
}

3. 复杂度分析

压栈 / 出栈：均摊 O (1)（扩容时单次 O (n)，但均摊后为常数）
空间复杂度：O (n)（存储 n 个元素）

（三）典型应用：有效的括号

问题：判断字符串"()[]{}"是否括号匹配
算法步骤：

遍历字符串，遇左括号({[则压栈
遇右括号) ] }则检查栈顶是否为对应左括号：匹配则出栈，不匹配则直接返回 false
遍历结束后，栈空则合法，否则剩余左括号未匹配

代码关键点：用字典（或 switch）建立左右括号映射关系，处理边界情况（如字符串长度为奇数直接非法）。

二、队列：FIFO 特性的典型代表

（一）核心概念与抽象模型

定义与特性
队列是遵循先进先出（FIFO）原则的线性结构，插入操作在队尾（Rear），删除操作在队头（Front）。形象化理解：如同排队购票，先排队的人先接受服务。
- 入队（Enqueue）：数据从队尾插入，时间复杂度 O (1)
- 出队（Dequeue）：数据从队头删除，时间复杂度 O (1)
- 典型场景：操作系统进程调度（如就绪队列）、网络请求缓冲、BFS 算法（逐层访问图节点）。
逻辑模型与物理结构
- 链表实现：用双向链表或单链表，维护头指针（队头）和尾指针（队尾），适合频繁头尾操作
- 数组实现：普通数组实现需移动元素（头删除低效），故更适合循环队列实现

（二）链表实现的工程细节（C 语言）

1. 结构体定义与初始化

typedef int QDataType;
// 队列节点
typedef struct QueueNode {QDataType value;struct QueueNode* next;
} QueueNode;// 队列整体结构
typedef struct Queue {QueueNode* front; // 队头指针（指向第一个节点）QueueNode* rear;  // 队尾指针（指向最后一个节点）int size;         // 元素个数（优化：避免遍历计算长度）
} Queue;void QueueInit(Queue* queue) {queue->front = queue->rear = NULL;queue->size = 0;
}

2. 核心操作实现

入队（处理空队列场景）

void QueuePush(Queue* queue, QDataType value) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){peeror("malloc fail");return;}newNode->value = value;newNode->next = NULL;if (QueueEmpty(queue)) { // 空队列时头尾指针指向同一节点queue->front = queue->rear = newNode;} else { // 非空时尾指针的next指向新节点，尾指针后移queue->rear->next = newNode;queue->rear = newNode;}queue->size++;
}

出队（处理单节点队列）

void QueuePop(Queue* queue) {if (QueueEmpty(queue)) return;QueueNode* temp = queue->front;queue->front = queue->front->next; // 头指针后移free(temp); // 释放内存if (queue->front == NULL) { // 若删除后队列为空，尾指针置空queue->rear = NULL;}queue->size--;
}

获取队头 / 队尾元素

QDataType QueueFront(Queue* queue) {if (QueueEmpty(queue))return;return queue->front->value;
}
QDataType QueueBack(Queue* queue) {if (QueueEmpty(queue)) return;return queue->rear->value;
}

（三）特殊实现：设计循环队列

1. 设计目标

避免普通数组队列 “假溢出” 问题（队尾到达数组末尾但头部有空闲空间），通过环形结构复用空间。

2. 关键参数与状态判断

typedef struct {int* data;       // 存储数组int front;       // 队头下标（指向实际队头元素）int rear;        // 队尾下标（指向队尾元素的下一个空位）int capacity;    // 数组容量（含一个预留空位）
} MyCircularQueue;

队空条件：front == rear
队满条件：(rear + 1) % capacity == front
元素个数：(rear - front + capacity) % capacity

3. 核心操作实现（入队为例）

bool MyCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (MyCircularQueueIsFull(obj)) return false;obj->data[obj->rear] = value; // 先赋值obj->rear = (obj->rear + 1) % obj->capacity; // 再移动指针return true;
}

三、深度对比：栈 vs 队列的本质差异

维度	栈（Stack）	队列（Queue）
数据访问原则	后进先出（LIFO）	先进先出（FIFO）
操作限制	仅栈顶可插入 / 删除	队尾插入、队头删除
典型底层实现	数组（动态扩容，尾操作高效）	链表（头尾指针，头删除高效）
空间特性	栈顶指针移动，无需频繁内存分配	节点动态创建 / 销毁，可能有碎片
适用算法	深度优先搜索（DFS）、递归模拟	广度优先搜索（BFS）、层次遍历
内存管理	数组实现需处理扩容（均摊 O (1)）	链表实现需手动释放节点内存

四、进阶应用：数据结构的 “跨界” 实现

1. 用队列实现栈

核心思路：维护两个队列q1和q2，入栈时将元素加入非空队列，出栈时将非空队列的前 n-1 个元素转移到另一个队列，最后剩余元素即为栈顶。

入栈操作：push(x) → 加入非空队列（若均空则选q1）
出栈操作：pop() → 将非空队列的元素依次出队并入队到另一个队列，直到剩 1 个元素，弹出该元素

2. 用栈实现队列

核心思路：两个栈inStack和outStack，入队时压入inStack，出队时若outStack为空则将inStack全部元素倒序压入outStack（实现 FIFO）。

入队操作：push(x) → inStack.push(x)
出队操作：pop() → 若outStack空，先将inStack全部转移到outStack，再弹出outStack栈顶

五、工程实践中的注意事项

1. 边界条件处理

栈操作需检查栈空（避免越界访问）
队列操作需检查队空（避免空指针解引用）
循环队列需严格区分队空与队满条件（通过预留空位或计数器）

2. 内存管理最佳实践

数组实现的栈 / 队列：初始化时分配合理初始容量，扩容时使用realloc避免数据拷贝
链表实现的队列：出队时必须释放节点内存，销毁队列时需遍历释放所有节点
避免内存泄漏：建立 “初始化 - 使用 - 销毁” 的完整生命周期管理流程

3. 语言特性适配

C++：可直接使用 STL 的stack（底层 deque）和queue（底层 list/deque）
Python：collections.deque提供高效的头尾操作（替代原生 list 的pop(0)低效操作）
Java：java.util.Stack（过时，推荐用Deque实现），Queue接口有LinkedList等实现

六、总结：数据结构设计的本质

栈和队列的核心价值在于通过限制操作接口，实现特定的访问顺序。这种 “受限的数据访问” 思想是计算机科学的重要设计范式：

栈的 LIFO 特性适合处理 “嵌套”“回溯” 场景（如函数调用、语法分析）
队列的 FIFO 特性适合处理 “有序”“缓冲” 场景（如任务调度、数据流处理）

理解这两种结构，不仅要掌握 API 接口，更要深入底层实现（数组 vs 链表的选择、边界条件处理、内存管理），以及在算法设计中的灵活运用（如用栈模拟递归，用队列实现层序遍历）。它们是理解更复杂数据结构（如优先队列、双端队列）的基础，更是培养 “问题建模能力” 的重要切入点。

通过实际编码实现栈和队列的各个操作，处理各种边界情况，才能真正掌握其精髓 —— 这正是计算机科学 “从抽象到具体” 的工程思维体现。

附录

栈

//stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;		// 栈顶int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

//stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{ps->arr = NULL;ps->capacity = ps->top = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = data;}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
// 出栈 
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));--ps->top;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(!StackEmpty(ps));return ps->top;}
// 销毁栈 
void StackDestroy(Stack* ps)
{if (ps->arr != NULL)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}

队列

//Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

//Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
// 初始化队列 
void QueueInit(Queue* q)
{q->front = q->rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail1");exit(1);}newnode->data = data;newnode->next = NULL;if (q->front == NULL){q->front = q->rear = newnode;}else{q->rear->next = newnode;q->rear = newnode;}
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}
// 队头出队列 
void QueuePop(Queue* q)
{assert(!QueueEmpty(q));if (q->front == q->rear){free(q->front);q->front = q->rear = NULL;}else{QNode* tmp = q->front->next;free(q->front);q->front = tmp;}
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(!QueueEmpty(q));return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(!QueueEmpty(q));return q->rear->data;}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);int count = 0;QNode* tmp = q->front;while (tmp != NULL){count++;tmp = tmp->next;}return count;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* pcur = q->front;while (q->front){QNode* tmp = q->front->next;free(q->front);q->front = tmp;}q->front = q->rear = NULL;
}

一、栈：LIFO 特性的完美诠释

（一）核心概念与抽象模型

（二）数组实现的工程细节（C 语言）

1. 结构体定义与初始化

2. 核心操作实现

3. 复杂度分析

（三）典型应用：有效的括号

二、队列：FIFO 特性的典型代表

（一）核心概念与抽象模型

（二）链表实现的工程细节（C 语言）

1. 结构体定义与初始化

2. 核心操作实现

（三）特殊实现：设计循环队列

1. 设计目标

2. 关键参数与状态判断

3. 核心操作实现（入队为例）

三、深度对比：栈 vs 队列的本质差异

四、进阶应用：数据结构的 “跨界” 实现

1. 用队列实现栈

2. 用栈实现队列

五、工程实践中的注意事项

1. 边界条件处理

2. 内存管理最佳实践

3. 语言特性适配

六、总结：数据结构设计的本质

附录

栈

队列

相关文章：