网站导航
> 技术文档 > 数据结构中的栈与队列：原理、实现与应用_线性表、栈、队列、树、图等数据结构的原理知识csdn

数据结构中的栈与队列：原理、实现与应用_线性表、栈、队列、树、图等数据结构的原理知识csdn

网友: 技术文档 2025-07-30 13:49:17

前言：栈和队列是计算机科学中两种最基础的线性数据结构，它们的独特操作规则和广泛的应用场景使其成为每一位开发者必须掌握的核心知识。本文将通过生活案例、代码实现和实际应用场景，带您深入理解这两种数据结构的精髓。

1.栈（Stack）

基本定义

栈是一种受限的线性表，仅允许在同一端（栈顶）进行数据插入（push）和删除（pop）操作。其核心特性遵循LIFO(后进先出)（Last In First Out）原则，即后进入的元素优先被访问。

LIFO原则

  • 后进先出（Last In First Out）：最后入栈的元素总是最先出栈

  • 入栈（Push）：将新元素放入栈顶

  • 出栈（Pop）：移除并返回栈顶元素

核心机制

  • 单端操作：所有操作集中在栈顶完成

  • 动态指针：通过栈顶指针（top）实时跟踪最新元素位置

  • 操作限制：禁止直接访问中间元素，必须按序操作

  • 空间管理：顺序栈需预判容量，链式栈动态扩展但需额外指针空间

2.栈的实现

实现方式 优点 缺点 适用场景 动态数组 缓存友好，访问速度快 扩容时需要拷贝数据 通用场景 链表 无需预分配空间 每个元素需要额外指针空间 元素数量变化剧烈 静态数组 内存分配确定 容量固定，不够灵活 嵌入式系统/内存受限环境

本文将以动态数组为基础，手把手带你用C语言实现一个智能的“自动扩容栈”。

/* 栈元素类型定义（方便修改数据类型） */typedef int STDataType;/* 栈结构体定义 arr: 动态数组首地址 top: 栈顶指针（当前元素数量） capacity: 数组总容量 */typedef struct Stack { STDataType* arr; int top; int capacity; } ST;/* 功能：初始化栈结构 参数：ps - 指向栈的指针 关键点：初始状态数组为空，容量为0 */void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0;}/* 功能：压入元素到栈顶 参数：ps - 栈指针，x - 要入栈的元素 关键点：自动扩容策略（4→8→16...） 示例：初始容量0时首次push会扩容到4 */void STPush(ST* ps, STDataType x) { assert(ps); // 容量检查与扩容 if (ps->capacity == ps->top) { int newcapacity = ps->capacity ? 2*ps->capacity : 4; STDataType* temp = realloc(ps->arr, newcapacity*sizeof(STDataType)); if (!temp) { perror(\"malloc\"); exit(1); } ps->arr = temp; ps->capacity = newcapacity; } ps->arr[ps->top++] = x; // 先存数据再移动指针}/* 功能：判断栈是否为空 参数：ps - 栈指针 返回：true表示空栈，false非空 示例：初始化后返回true，push后返回false */bool STEmpty(ST* ps) { assert(ps); return ps->top == 0;}/* 功能：弹出栈顶元素 参数：ps - 栈指针 关键点：实际只移动指针，不删除数据 注意：空栈弹出会导致断言失败 */void STPop(ST* ps) { assert(ps && !STEmpty(ps)); ps->top--; // 逻辑删除}/* 功能：获取栈元素数量 参数：ps - 栈指针 返回：当前元素个数 示例：push三次后返回3 */int STSize(ST* ps) { assert(ps); return ps->top; // top直接表示数量}/* 功能：查看栈顶元素（不弹出） 参数：ps - 栈指针 返回：栈顶元素值 关键点：top-1才是最后存入的位置 示例：栈内[10,20]时返回20 */STDataType STTop(ST* ps) { assert(ps && !STEmpty(ps)); return ps->arr[ps->top-1];}/* 功能：销毁栈并释放内存 参数：ps - 栈指针 关键点：必须调用防止内存泄漏 注意：调用后栈不可再使用 */void STDestroy(ST* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0;}

测试用例 

int main(){ST st; // 声明栈变量（未初始化状态）STInit(&st); // 初始化栈 → arr=NULL, capacity=0, top=0STPush(&st, 1); // 触发扩容（0→4）→ arr[0]=1, top=1printf(\"%d\\n\", STSize(&st)); // 输出1（当前元素数量）STPush(&st, 2); // arr[1]=2, top=2printf(\"%d\\n\", STSize(&st)); // 输出2STPush(&st, 3); // arr[2]=3, top=3printf(\"%d\\n\", STSize(&st)); // 输出3STPush(&st, 4); // arr[3]=4, top=4（栈满）printf(\"%d\\n\", STSize(&st)); // 输出4while (!STEmpty(&st)) //打印栈中所有元素{ printf(\"%d \", STTop(&st)); // 从栈顶开始输出：4 3 2 1STPop(&st);  // 每次循环top减1}printf(\"\\n%d\", STSize(&st)); // 输出0（此时栈空）STDestroy(&st); // 必须调用！释放动态内存 return 0;}

3.队列（Queue）

基本定义

队列是另一种受限线性表，遵循FIFO（First In First Out）原则。元素从队尾（rear）插入（enqueue），从队首（front）移除，保持严格的先进先出顺序。

核心机制

  • 双指针系统：通过 front 和 rear 指针分别管理两端

  • 循环优化：使用模运算实现环形缓冲区解决\"假溢出\"问题

  • 等待特性：元素按到达顺序被处理，具有公平性特征

  • 容量管理：动态队列可扩展，但需考虑内存碎片问题

4.队列的实现

实现方式 优点 缺点 适用场景 普通数组队列 实现简单 出队效率低（需要搬移元素） 教学演示 循环数组队列 高效利用内存 需处理队空/队满边界条件 固定容量生产消费场景 链表队列 动态扩容灵活 内存碎片化，缓存不友好 频繁扩容/元素大小不一 动态数组队列 平衡性能与灵活性 扩容时产生瞬时延迟 通用场景

在本文中，会着重介绍下面三种队列，普通数组队列的使用并不常见，我们在这里并不过多介绍，大家可以自己尝试着实现。首先，我们实现链式队列。循环数组队列和动态数组队列我们作为后面习题补充会涉及到。

注意：链式队列的实现与单链表的实现大差不差，前面单链表的实现非常重要，能够完成单链表的实现代码，实现链式队列代码就不成问题。

typedef int QDataType; // 队列元素类型别名，方便修改存储类型// 队列节点结构（链式存储）typedef struct QueueNode { int val;  // 存储数据 struct QueueNode* next; // 指向下一个节点} QNode;// 队列管理结构typedef struct Queue { QNode* phead; // 队头指针（删除端） QNode* ptail; // 队尾指针（插入端） int size; // 当前元素数量} Queue;// 功能：初始化队列结构// 参数：pq - 指向队列的指针// 关键点：将指针置空，size清零void QueueInit(Queue* pq) { assert(pq); // 防御性编程，确保指针有效 pq->phead = pq->ptail = NULL; pq->size = 0; // 初始为空队列}// 功能：创建新节点// 参数：x - 要存储的数据// 返回：新节点指针// 关键点：内存分配与初始化QNode* Createnode(QDataType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { // 内存不足处理 perror(\"malloc\");  // 打印错误信息 exit(1);  // 直接终止程序 } newnode->val = x;  // 存储数据 newnode->next = NULL;  // 初始化指针 return newnode;}// 功能：在队尾插入新元素// 参数：pq - 队列指针，x - 要插入的数据// 关键点：维护头尾指针关系void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = Createnode(x); // 创建新节点 if (pq->phead == NULL) { // 空队列情况 pq->phead = pq->ptail = newnode; } else { // 非空队列 pq->ptail->next = newnode; // 链接新节点 pq->ptail = newnode; // 更新尾指针 } pq->size++; // 元素计数增加}// 功能：判断队列是否为空// 参数：pq - 队列指针// 返回：true为空，false非空// 关键点：只需检查头指针bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; // 头指针为空即队列空}// 功能：删除队头元素// 参数：pq - 队列指针// 关键点：处理最后一个节点的特殊情况void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); // 确保队列非空 QNode* del = pq->phead; // 保存待删除节点 pq->phead = pq->phead->next;// 头指针后移 // 处理删除最后一个元素的情况 if (pq->phead == NULL) { pq->ptail = NULL; // 尾指针也必须置空 } free(del); // 释放节点内存 pq->size--; // 元素计数减少}// 功能：查看队头元素（不删除）// 参数：pq - 队列指针// 返回：队头元素值// 注意：队列为空时触发断言QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); // 防御空队列访问 return pq->phead->val; // 直接返回头节点值}// 功能：查看队尾元素（不删除）// 参数：pq - 队列指针// 返回：队尾元素值QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); // 防御空队列访问 return pq->ptail->val; // 直接返回尾节点值}// 功能：获取当前元素数量// 参数：pq - 队列指针// 返回：队列元素个数// 优势：O(1)时间复杂度int QueueSize(Queue* pq) { assert(pq); return pq->size; // 直接返回计数器值}// 功能：释放队列所有内存// 参数：pq - 队列指针// 关键点：必须遍历释放所有节点void QueueDestroy(Queue* pq) { assert(pq); QNode* curr = pq->phead; while (curr) { QNode* del = curr; // 保存当前节点 curr = curr->next; // 移动到下一个节点 free(del);  // 释放当前节点 } pq->phead = pq->ptail = NULL; // 重置指针 pq->size = 0;  // 重置计数器}

测试用例

int main() { Queue q; QueueInit(&q); // 必须初始化 QueuePush(&q, 10); QueuePush(&q, 20); printf(\"队头：%d\\n\", QueueFront(&q)); // 输出10 QueuePop(&q); // 删除10 printf(\"当前大小：%d\\n\", QueueSize(&q)); // 输出1 QueueDestroy(&q); // 必须销毁 return 0;}

 5.栈与队列算法题

5.1 力扣：有效的括号

 1. 核心思想

  • 栈的LIFO特性：利用栈后进先出的特性，确保最近打开的括号必须最先闭合

  • 匹配原则：遍历字符串时，遇到左括号入栈，遇到右括号必须与栈顶左括号类型匹配

2. 执行流程

  1. 初始化栈：创建空栈用于存储待匹配的左括号

  2. 遍历字符：逐个处理输入字符串的每个字符

    • 左括号处理：(/[/{ → 压入栈顶

    • 右括号处理：

      • 检查栈空 → 栈空直接返回false

      • 栈非空 → 检查栈顶是否匹配 → 匹配则弹出，不匹配返回false

  3. 最终校验：遍历完成后检查栈是否为空（所有左括号均已匹配）

//代码中所用函数都是上文栈的实现中的函数bool isValid(char* s) { ST st; STInit(&st); while(*s != \'\\0\') { if(*s == \'(\' || *s == \'[\' || *s == \'{\') { STPush(&st,*s); } else { if(STEmpty(&st)) return false; STDataType ch1 = STTop(&st); if((ch1 == \'(\' && *s == \')\') || (ch1 == \'[\' && *s == \']\') || (ch1 == \'{\' && *s == \'}\')) STPop(&st); else { STDestroy(&st); return false; } } s++; } if(!STEmpty(&st)) return false; STDestroy(&st); return true;}

5.2力扣：用队列实现栈 

// 代码中所用函数都是上文队列的实现中的函数// 使用两个队列实现栈的结构定义typedef struct { Queue q1; Queue q2;} MyStack;// 创建栈实例并初始化两个队列MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst;}// 入栈操作：将元素压入非空队列（若都为空则选择q1）void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) QueuePush(&obj->q1, x); else QueuePush(&obj->q2, x);}// 出栈操作：将非空队列的前n-1个元素转移到空队列，弹出最后一个元素int myStackPop(MyStack* obj) { Queue* emptyQue = &obj->q1; Queue* nonEmptyQue = &obj->q2; // 确定空队列和非空队列 if(QueueEmpty(nonEmptyQue)) { emptyQue = &obj->q2; nonEmptyQue = &obj->q1; } // 将非空队列的前n-1个元素转移到空队列 while(QueueSize(nonEmptyQue) > 1) { QDataType data = QueueFront(nonEmptyQue); QueuePop(nonEmptyQue); QueuePush(emptyQue, data); } // 弹出并返回最后一个元素 QDataType ret = QueueFront(nonEmptyQue); QueuePop(nonEmptyQue); return ret;}// 获取栈顶元素：直接返回非空队列的队尾元素int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) return QueueBack(&obj->q1); else return QueueBack(&obj->q2);}// 判断栈是否为空：当两个队列都为空时栈为空bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}// 释放栈内存：销毁两个队列并释放栈结构void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); obj = NULL;}

 5.3力扣：用栈实现队列

 

// 代码中所用函数都是上文栈的实现中的函数// 使用两个栈实现队列的结构定义typedef struct { ST Pushst; // 用于入队操作的栈 ST Popst; // 用于出队操作的栈} MyQueue;// 创建队列实例并初始化两个栈MyQueue* myQueueCreate() { MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue)); STInit(&pst->Pushst); STInit(&pst->Popst); return pst;}// 入队操作：直接压入Push栈void myQueuePush(MyQueue* obj, int x) { STPush(&obj->Pushst, x);}// 出队操作：若Pop栈为空，则将Push栈元素全部倒入Pop栈，再弹出Pop栈顶元素int myQueuePop(MyQueue* obj) { if(STEmpty(&obj->Popst)) { // 将Push栈的元素逆序倒入Pop栈 while(!STEmpty(&obj->Pushst)) { STDataType data = STTop(&obj->Pushst); STPop(&obj->Pushst); STPush(&obj->Popst, data); } } STDataType ret = STTop(&obj->Popst); STPop(&obj->Popst); return ret;}// 获取队首元素：逻辑同出队，但不弹出元素int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->Popst)) { while(!STEmpty(&obj->Pushst)) { STDataType data = STTop(&obj->Pushst); STPop(&obj->Pushst); STPush(&obj->Popst, data); } } return STTop(&obj->Popst);}// 判断队列是否为空：当两个栈都为空时队列为空bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->Popst) && STEmpty(&obj->Pushst);}// 释放队列内存：销毁两个栈并释放队列结构void myQueueFree(MyQueue* obj) { STDestroy(&obj->Popst); STDestroy(&obj->Pushst); free(obj); obj = NULL;}

 5.4力扣：设计循环队列

// 使用数组实现的环形队列结构typedef struct { int* arr; // 存储队列元素的数组 int front; // 队头指针：指向队列第一个有效元素 int rear; // 队尾指针：指向队列最后一个元素的下一个位置 int capacity; // 队列的最大容量（实际存储元素个数为capacity）} MyCircularQueue;// 创建环形队列实例，k为队列容量MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // 分配k+1大小的数组，浪费一个空间用于区分队列满和空的状态 obj->arr = (int*)malloc(sizeof(int) * (k + 1)); obj->front = obj->rear = 0; // 初始化队头队尾指针 obj->capacity = k; // 设置队列容量 return obj;}// 判断队列是否为空bool myCircularQueueIsEmpty(MyCircularQueue* obj) { // 当队头和队尾指针指向同一位置时，队列为空 return obj->rear == obj->front;}// 判断队列是否已满bool myCircularQueueIsFull(MyCircularQueue* obj) { // 当队尾指针的下一个位置是队头指针时，队列已满 // 使用取模运算实现环形效果 return (obj->rear + 1) % (obj->capacity + 1) == obj->front;}// 入队操作bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) return false; // 队列已满，入队失败 obj->arr[obj->rear] = value; // 将元素放入队尾位置 obj->rear = (obj->rear + 1) % (obj->capacity + 1); // 更新队尾指针，循环前进 return true;}// 出队操作bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return false; // 队列为空，出队失败 obj->front = (obj->front + 1) % (obj->capacity + 1); // 更新队头指针，循环前进 return true;}// 获取队头元素int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; // 队列为空，返回-1表示无效值 return obj->arr[obj->front]; // 返回队头指针指向的元素}// 获取队尾元素int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) return -1; // 队列为空，返回-1表示无效值 // 计算队尾元素的实际位置（队尾指针前一个位置） int prev = (obj->rear - 1 + (obj->capacity + 1)) % (obj->capacity + 1); return obj->arr[prev];}// 释放队列内存void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); // 释放存储元素的数组 free(obj); // 释放队列结构体 obj = NULL; // 防止野指针}

  1. 数组大小：

    • 实际分配大小为 capacity + 1，浪费一个空间用于区分队列满和队列空的状态
    • 队列满条件：(rear + 1) % (capacity + 1) == front
    • 队列空条件：rear == front

  2. 指针移动：

    • 队头指针front：指向队列的第一个有效元素
    • 队尾指针rear：指向队列最后一个元素的下一个位置
    • 使用% (capacity + 1)实现环形效果

  3. 边界处理：

    • 入队时直接在rear位置赋值，然后rear指针后移
    • 出队时直接将front指针后移，无需真正删除元素
    • 获取队尾元素时需要计算rear的前一个位置，处理rear为 0 的情况

5.5设计动态循环列表

#include #include typedef struct { int* data; // 存储队列元素的动态数组 int front; // 队头指针，指向队列第一个元素 int rear; // 队尾指针，指向队列最后一个元素的下一个位置 int capacity; // 当前队列容量 int size; // 当前队列元素个数} DynamicQueue;// 创建动态队列，初始容量为initialCapacityDynamicQueue* createQueue(int initialCapacity) { DynamicQueue* queue = (DynamicQueue*)malloc(sizeof(DynamicQueue)); assert(queue != NULL); queue->data = (int*)malloc(sizeof(int) * initialCapacity); assert(queue->data != NULL); queue->front = 0; queue->rear = 0; queue->size = 0; queue->capacity = initialCapacity; return queue;}// 判断队列是否为空bool isEmpty(DynamicQueue* queue) { return queue->size == 0;}// 判断队列是否已满（实际不会满，会自动扩容）bool isFull(DynamicQueue* queue) { return queue->size == queue->capacity;}// 扩容队列，新容量为原容量的2倍void resizeQueue(DynamicQueue* queue) { int newCapacity = queue->capacity * 2; int* newData = (int*)malloc(sizeof(int) * newCapacity); assert(newData != NULL); // 复制原队列元素到新数组 for (int i = 0; i size; i++) { newData[i] = queue->data[(queue->front + i) % queue->capacity]; } free(queue->data); queue->data = newData; queue->front = 0; queue->rear = queue->size; queue->capacity = newCapacity;}// 入队操作void enqueue(DynamicQueue* queue, int value) { if (isFull(queue)) { resizeQueue(queue); } queue->data[queue->rear] = value; queue->rear = (queue->rear + 1) % queue->capacity; queue->size++;}// 出队操作，返回队头元素int dequeue(DynamicQueue* queue) { assert(!isEmpty(queue)); int value = queue->data[queue->front]; queue->front = (queue->front + 1) % queue->capacity; queue->size--; return value;}// 获取队头元素int getFront(DynamicQueue* queue) { assert(!isEmpty(queue)); return queue->data[queue->front];}// 获取队列大小int getSize(DynamicQueue* queue) { return queue->size;}// 释放队列内存void freeQueue(DynamicQueue* queue) { free(queue->data); free(queue);}

 

网络标签：

相关问题