【数据结构】栈与队列：数据结构中的双生子
栈与队列：数据结构中的双生子
✨前言：在数据结构的学习中，栈(Stack) 与 队列(Queue) 是两种基础而强大的存在。它们看似简单，却在各种算法和系统设计中扮演着核心角色。理解它们的特性和实现原理，是每位程序员成长的必经之路。今天我将带大家深入学习栈和队列。
📖专栏：【数据结构】
目录
一、栈（Stack）：后进先出的数据世界
1.1 栈的核心概念
栈是一种特殊的线性表，遵循LIFO（Last In First Out）原则，即最后入栈的元素最先出栈。它只允许在固定的一端（称为栈顶）进行插入（压栈）和删除（出栈）操作，另一端称为栈底。
- 压栈（Push）：向栈顶添加元素
- 出栈（Pop）：从栈顶移除元素
1.2 栈的实现方式
栈可以通过数组或链表实现，数组实现通常更优，因为：
- 数组在尾部插入/删除的时间复杂度为O(1)
内存连续，缓存命中率高
对于栈顶指针一般指向指向栈顶元素的下一个位置解释：
一般来说，栈顶指针可以指向栈顶元素，那这样的话栈为空的情况，top就只能指向-1了，看起来很别扭，所以为了方便起见，直接让栈顶指针指向指向栈顶元素的下一个位置就行。
1. 栈结构定义和初始化
#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefint STDataType;// 栈存储的数据类型// 栈结构体typedefstructStack{ STDataType* a;// 动态数组存储栈元素int top;// 栈顶指针(指向栈顶元素的下一个位置)int capacity;// 当前分配的存储容量} Stack;#defineINIT_SIZE4// 初始容量大小// 初始化栈voidStackInit(Stack* ps){assert(ps !=NULL);// 安全检查 ps->a =NULL;// 初始时数组为空 ps->top =0;// 栈顶指针初始为0 ps->capacity =0;// 初始容量为0}2. 容量检查函数（内部使用）
// 检查并扩容栈（内部函数）staticvoidCheckCapacity(Stack* ps){assert(ps !=NULL);// 当栈满时需要扩容if(ps->capacity == ps->top){// 计算新容量：初始为INIT_SIZE，否则双倍扩容int newCapacity =(ps->capacity ==0)? INIT_SIZE : ps->capacity *2;// 重新分配内存 STDataType* tmp =(STDataType*)realloc(ps->a, newCapacity *sizeof(STDataType));if(tmp ==NULL){perror("栈扩容失败");exit(EXIT_FAILURE);} ps->a = tmp; ps->capacity = newCapacity;printf("栈已扩容至%d\n", newCapacity);// 调试信息}}3. 入栈操作
// 元素入栈voidStackPush(Stack* ps, STDataType data){assert(ps !=NULL);// 安全检查// 检查是否需要扩容CheckCapacity(ps);// 将元素放入栈顶位置 ps->a[ps->top]= data; ps->top++;// 栈顶指针上移printf("元素%d入栈成功\n", data);// 调试信息}4. 出栈操作
// 元素出栈voidStackPop(Stack* ps){// 安全检查：栈不能为空assert(ps !=NULL&&!StackEmpty(ps));printf("元素%d出栈\n",StackTop(ps));// 调试信息 ps->top--;// 栈顶指针下移}5. 获取栈顶元素
// 获取栈顶元素 STDataType StackTop(Stack* ps){// 安全检查：栈不能为空assert(ps !=NULL&&!StackEmpty(ps));return ps->a[ps->top -1];// 返回栈顶元素}6. 获取栈大小
// 获取栈中元素数量intStackSize(Stack* ps){assert(ps !=NULL);return ps->top;// 栈顶指针就是元素数量}7. 判断栈是否为空
// 检查栈是否为空 bool StackEmpty(Stack* ps){assert(ps !=NULL);return ps->top ==0;// 栈顶为0表示空栈}8. 销毁栈
// 销毁栈voidStackDestroy(Stack* ps){assert(ps !=NULL);free(ps->a);// 释放动态数组 ps->a =NULL;// 避免野指针 ps->top =0;// 重置栈顶指针 ps->capacity =0;// 重置容量printf("栈已销毁\n");// 调试信息}二、队列（Queue）：先进先出的公平机制
2.1 队列的核心概念
队列是另一种特殊的线性表，遵循FIFO（First In First Out）原则，即最先入队的元素最先出队。插入操作在队尾进行，删除操作在队头进行。
- 入队（Enqueue）：向队尾添加元素
- 出队（Dequeue）：从队头移除元素
2.2 队列的实现方式
队列通常使用链表实现更优，因为：
- 数组实现时，头部删除需要移动元素（O(n)）
- 链表在头部删除和尾部插入都是O(1)
1. 队列结构定义
#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefint QDataType;// 队列元素类型// 队列节点结构typedefstructQueueNode{ QDataType data;// 数据域structQueueNode* next;// 指向下一个节点} QNode;// 队列结构typedefstructQueue{ QNode* phead;// 队头指针 QNode* ptail;// 队尾指针int size;// 队列元素个数} Queue;2. 队列初始化
// 初始化队列 voidQueueInit(Queue* q){assert(q);// 确保队列指针有效 q->phead = q->ptail =NULL;// 初始时头尾指针都为空 q->size =0;// 初始大小为0}3. 入队操作
// 队尾入队列 voidQueuePush(Queue* q, QDataType data){assert(q);// 确保队列指针有效// 创建新节点 QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");exit(1);} newnode->data = data;// 设置节点数据 newnode->next =NULL;// 新节点next置空// 队列为空时的特殊处理if(q->phead ==NULL){ q->phead = q->ptail = newnode;}else{ q->ptail->next = newnode;// 原尾节点指向新节点 q->ptail = newnode;// 更新尾指针} q->size++;// 队列大小增加}4. 出队操作
// 队头出队列 voidQueuePop(Queue* q){assert(q && q->phead !=NULL);// 确保队列不为空 QNode* pop = q->phead;// 保存要删除的节点 q->phead = q->phead->next;// 头指针后移free(pop);// 释放原头节点 pop =NULL;// 避免野指针// 如果出队后队列为空，更新尾指针if(q->phead ==NULL){ q->ptail =NULL;} q->size--;// 队列大小减少}5. 获取队头元素
// 获取队列头部元素 QDataType QueueFront(Queue* q){assert(q && q->phead);// 确保队列不为空return q->phead->data;// 返回头节点数据}6. 获取队尾元素
// 获取队列队尾元素 QDataType QueueBack(Queue* q){assert(q && q->ptail);// 确保队列不为空return q->ptail->data;// 返回尾节点数据}7. 获取队列大小
// 获取队列中有效元素个数 intQueueSize(Queue* q){assert(q);// 确保队列指针有效return q->size;// 直接返回size成员}8. 检查队列是否为空
// 检测队列是否为空 bool QueueEmpty(Queue* q){assert(q);// 确保队列指针有效return q->size ==0;// size为0表示空队列}9. 销毁队列
// 销毁队列 voidQueueDestroy(Queue* q){assert(q);// 确保队列指针有效 QNode* pcur = q->phead;// 从头节点开始 QNode* next =NULL;// 保存下一个节点// 遍历释放所有节点while(pcur){ next = pcur->next;// 保存下一个节点free(pcur);// 释放当前节点 pcur = next;// 移动到下一个节点}// 重置队列状态 q->phead = q->ptail =NULL; q->size =0;}三、总结
栈和队列虽然操作规则截然不同，但它们都是线性数据结构的基础构件。栈的LIFO特性使其成为处理递归和回溯的理想选择，而队列的FIFO特性则完美匹配需要公平处理的场景。理解它们的核心概念和实现细节，能够帮助我们更好地设计算法和解决实际问题。这两种看似简单的数据结构，共同构建了计算机科学中无数复杂系统的基石。
如果本文对您有启发：
✅ 点赞 -让更多人看到这篇硬核技术解析 ！
✅ 收藏 -实战代码随时复现
✅ 关注 -获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨
