AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构 | 栈和队列

2023-02-23 361
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 栈（Stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。队列（Queue）也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作，和栈一样，队列 的部分操作也会受到限制。

📘前言

栈（Stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。队列（Queue）也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作，和栈一样，队列 的部分操作也会受到限制。栈 的特点是 先进后出（FILO），队列 则是 先进先出（FIFO），本文将会通过顺序存储的方式模拟实现 栈，以及链式存储的方式模拟实现 队列，两种数据结构都比较简单，一起来看看吧！

d355619eb90d4f808304aa9107f86f54.jpg

📘正文

📖栈

首先介绍 栈 的实现，栈 非常适合通过 顺序表 来模拟实现，因为 顺序表 尾插、尾删的复杂度是O(1)，并且 栈 的插入、删除都是在 栈顶 完成的，因此我们可以去除 顺序表 的部分功能，这样就可以得到一个 栈

640ef9f9b7b54b9787606c77862f5e94.png

有人将栈形象的比作弹匣，装弹是在入栈，而将子弹射出则是在出栈，显然最先进入弹匣的子弹，将会在最后才被射出，准备的动图发不出来，可以自行百度查看


📃结构

既然可以通过 顺序表 实现 栈 ，那么 栈 的结构自然就和 顺序表 差不多了，都有一个 负责指向存储数据的指针 ，一个 下标(栈顶) 和 容量 ，因为 顺序表要求空间必须是连续的，因此后续需要进行动态内存开辟，而容量是不能少的

typedef int STDataType; //栈的元素类型
typedef struct StackInfo
{
  STDataType* data; //数据
  int top;  //栈顶
  int capacity; //容量
}Stack;

c5451721bac1424289d444b060f68e37.png

📃初始化

初始化需要把 指针 data 置空，栈顶值 top 和 容量值 capacity 归0

  • 当然这里的栈顶也可以置为-1，当我们取栈顶元素时，取的就是当前栈顶处的元素
  • 如果是归0，那么取的就是栈顶-1处的元素
  • 推荐归0，因为在后续操作中比较省事
voidStackDestroy(Stack*ps)    //栈的销毁{
assert(ps);
//只有为栈开辟空间了，才能正常销毁if (ps->data)
    {
free(ps->data);
ps->data=NULL;
ps->top=ps->capacity=0;
    }
}

📃销毁

销毁 栈 需要明白一点：是否可以销毁 ，因为可能会出现不插入元素的情况下，结束程序，此时如果继续执行销毁，就会发生空指针的解引用情况

voidStackDestroy(Stack*ps)    //栈的销毁{
assert(ps);
//只有为栈开辟空间了，才能正常销毁if (ps->data)
    {
free(ps->data);
ps->data=NULL;
ps->top=ps->capacity=0;
    }
}

c3a3234183be408a91fa0b094f9d0a78.png

📃入栈、出栈

顺序 栈 的 入栈、出栈 很简单，可以放一起介绍

  • 入栈
  • 确保有空间可以使用，因此需要借助扩容程序段
  • 直接将目标值插入到栈顶处
  • 最后栈顶+1，此时的栈顶代表着 栈 中的有效元素个数
voidStackPush(Stack*ps, STDataTypex) //入栈{
assert(ps);
//判断栈是否满if (ps->top==ps->capacity)
    {
intnewCapacity=ps->capacity==0?4 : ps->capacity*2; //二倍扩容STDataType*tmp= (STDataType*)realloc(ps->data, sizeof(STDataType) *newCapacity);
//如果扩容失败，需要报错并结束程序if (tmp==NULL)
        {
perror("realloc :: fail");
exit(-1);
        }
ps->data=tmp;
ps->capacity=newCapacity;
    }
//入栈，就是在栈顶处放入元素，然后栈顶+1ps->data[ps->top] =x;
ps->top++;
}

45f9656edd5a456cb4fcff555fb17a2a.png

出栈

  • 出栈需要确保 栈 内有元素可出
  • 如果 栈 为空，是不能执行出栈的
  • 出栈不需要将元素抹掉，直接栈顶-1，无法访问到此元素就行了
voidStackPop(Stack*ps)    //出栈{
assert(ps);
assert(ps->top>0);    //有元素才能出栈//出栈，直接栈顶-1ps->top--;
}

1dfcedb078a14c6aa414e2b0cdc6cbee.png

📃查看栈顶元素

前面说过，栈顶值 top-1 代表的就是当前栈顶元素，前提是有元素存在，因此这个函数就很简单了，直接先判断 栈 是否为空，如果不为空，返回 栈顶-1 处的元素值就行了

STDataTypeStackTop(Stack*ps)  //查看栈顶元素{
assert(ps);
assert(ps->top>0);    //有元素才能看//栈顶元素，在栈顶-1处，因为栈顶是从0开始的returnps->data[ps->top-1];
}

c7b26c30d6b24965897d12fcae33da96.png

📃查看栈内有效元素

所谓栈内有效元素，就是顺序 栈 的长度，也就是 栈顶值 top ，此时就体现出 栈顶值 从0开始的好处了，做什么都很方便，比如这里，直接返回 栈顶值 就行了

intStackSize(Stack*ps)    //查看栈的有效元素个数{
assert(ps);
//栈的大小就是当前栈的有效元素个数returnps->top;
}

0e9694ca6fb64f1db97990660f4c3cc8.png

📃判断栈是否为空

判断栈是否为空，太简单了，一行代码解决

  • 返回的是布尔值，需要引头文件 stdbool.h
  • 因为判断式返回值是布尔类型
  • 如果栈顶值为0，说明栈空，判断式为真，返回 true
  • 否则说明栈不空。判断式为假，返回 false
boolStackEmpty(Stack*ps)  //判断栈是否为空{
assert(ps);
//栈顶为0.说明栈空returnps->top==0;
}

顺序 栈 也就这点东西，我愿称之为顺序表青春版，所有源码放在gitee上了，可以跳转到源码区传送过去

下面是程序运行图(测试的时候手速太快了，所以有的地方可能看不太清楚)

这是一张动图，时长56秒

📖队列

队列 的特点是先进先出，主要功能是头部删除和尾部插入，因为队列比较特殊，如果采用 顺序表 的形式实现的话，容易出现 假溢出 问题（后续解决 循环队列 问题会用 顺序表 模拟实现），因此我们这里采取 链表 的形式模拟实现 队列


分析得出队列的 需求 如下


单链表就足够了，多加一个队尾指针，可以有效避免效率问题

哨兵位（可要可不要），因为待会实现时，是结构体嵌套结构体的形式

使用非循环的链表，没必要使用双向带头循环链表（小题大做）

结论


最简单的单链表就可以实现

因为有队头、队尾两个指针，因此需要使用结构体嵌套的方式

691ea473b7fb4897a1a92d6eaa02dc4f.png📃结构

单链表 最大的缺陷就是不好找尾，为此我们直接通过结构体嵌套定义的方式，定义 队头指针 front 、队尾指针 rear 和 队列长度 size，这样一来，所有涉及队列的操作，都是在以 O(1) 效率执行，灰常高效，就是比较难理解


帮助理解


假设队列中的节点是一个个链接的小球

存在一个大外壳装着这些小球

并且有两个警卫分别守着球头和球尾，还有一个秘书帮忙记录球数

当然它们的作用是为了更好的管理小球

显然，front 和 rear 就是两个警卫，而 size 是秘书

typedefintQListDataType;  //队列的数据类型//这是队列中，单个节点的信息typedefstructQListNode{
QListDataTypedata;
structQListNode*next;
}QNode;
//这是整个队列的信息，包含了队头和队尾两个指针typedefstructQueueNode{
QNode*front;   //队头指针QNode*rear;    //队尾指针size_tsize;    //队列长度}Queue;

709db3c18b624dbda0dc7e409da7bead.png

📃初始化

队列 的初始化很直接，把 队尾、队头指针 置空，长度 置0就行了

void QueueInit(Queue* pq) //队列的初始化
{
  assert(pq);
  //初始化状态：队头、队尾指针都指向空，队列大小为0
  pq->front = pq->rear = NULL;
  pq->size = 0;
}

📃销毁

队列 销毁原理，和 单链表 的销毁差不多，需要借助一个 临时指针 cur ，指向当前队头，然后 队头指针 front 移向下一个位置，销毁 临时指针 cur ，如此循环，直到 临时指针 cur 指向 NULL ，此时整个 队列 都会被销毁


队列 不需要像 栈 那样做特殊处理，因为当队空时，cur 一开始就为空，循环是进不去的

当然销毁后，两个指针都要置空，size 也要归零

voidQueueDestroy(Queue*pq)    //队列的销毁{
assert(pq);
//销毁思路：利用临时指针进行销毁QNode*cur=pq->front;
while (cur)
    {
QNode*tmp=cur->next;
free(cur);
cur=tmp;
    }
pq->front=pq->rear=NULL;
pq->size=0;
}

e1a065048b94465bb19c7cc1cbea8081.png

📃入队、出队

有了 队头、队尾 两个指针，入队、出队就很简单了，直接易如反掌

入队

  • 即单链表的尾插
  • 买一个新节点，存放目标值，将 队尾指针 与新节点链接起来
  • 注意：如果是第一次入队，直接赋值，而不是链接
  • 更新 队尾指针 ，队尾指针 变成了新节点
  • 队列长度 + 1
voidQueuePush(Queue*pq, QListDataTypex)  //入队{
assert(pq);
//先买一个节点QNode*newnode=buyNode(x);
//分情况：如果队头为空，说明队空，此时直接将新节点赋值给队头、队尾if (pq->front==NULL)
    {
pq->front=pq->rear=newnode;
pq->size++;
    }
else    {
//否则就是将新节点，链接到队尾，然后更新队尾pq->rear->next=newnode;   //链接pq->rear=newnode; //更新队尾pq->size++;
    }
}

4a7ea2ac03d5453dbbb3ae24aa628567.png出队

  • 即单链表的头删
  • 利用临时指针，存储当前 队头指针 的信息
  • 队头向后移动，即更新 队头指针
  • 释放临时指针
  • 队列长度 - 1
voidQueuePop(Queue*pq)    //出队{
assert(pq);
assert(!QueueEmpty(pq));    //如果队空，是不能出队的//出队思想：有元素才能出队，更新队头，销毁原队头QNode*cur=pq->front;
pq->front=pq->front->next;    //更新队头指针free(cur);
cur=NULL;
pq->size--;
}

8e3afa9282ec4f39a130990d6aa84ae7.png

📃查看队头、队尾元素

这两个都是甜品函数，直接一行代码解决

查看队头

  • 判断队列是否为空
  • 不为空才能查看，队头元素为 队头指针 的指向值
QListDataTypeQueueFront(Queue*pq) //查看队头元素{
assert(pq);
assert(!QueueEmpty(pq));
returnpq->front->data;
}

查看队尾

  • 同样需要判断队列是否为空
  • 不为空才能查看，队尾元素为 队尾指针 的指向值
QListDataTypeQueueRear(Queue*pq)  //查看队尾元素{
assert(pq);
assert(!QueueEmpty(pq));
returnpq->rear->data;
}

📃查看队内有效元素

队列中的有效元素数，就是之前一直默默工作的 队列长度 size，直接返回它的值就好了，没什么技巧


至于为何不通过遍历的方式确定有效元素数


时间成本太高，如果队列中有10w个元素，那么在调用此函数时，会很浪费时间

结构设计时 size 的加入，能很好的避免这个问题，因为 size 在改变时，总是伴随着入队或出队，默默记录，效率是很高

intQueueSize(Queue*pq)    //当前队列的有效元素数{
assert(pq);
returnpq->size;    //直接返回就行了}

📃判断队是否为空

此时判断队列是否为空，有多种方法

  • 通过 size 判断，为0，说明队列为空
  • 通过 队头指针 或 队尾指针 判断，为空说明队空

这里使用第二种方法，通过 队头指针 进行判断

当然，返回值是 布尔值 ，同样是利用了判断式的返回值

boolQueueEmpty(Queue*pq)  //判断当前队空情况{
assert(pq);
returnpq->front==NULL;
}

至此，队列 结束，结构体嵌套 也就是个纸老虎，实际还没有 二级指针 复杂，可以把 链队列 看作 单链表 的青春版

下面是程序运行图，同样是动图，可以耐心看完

image.gif


📖源码区

注意：为了避免文章过长，现采取 Gitee 仓库分享代码的形式，秉持开源精神，所有代码都可参考!

📃栈

这是属于栈的文件夹


📃队列

这是属于队列的文件夹


📘总结

栈和队列 是两种比较特殊的数据结构，在实际中往往很少单独去使用，都是用来配合实现其他数据结构，比如 二叉树 的 层序遍历 中会用到 队列 ，很多OJ试题也会爱考这两种数据结构，因此学好它们还是很重要的


如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！


如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正


c3a2fbd4cece4640b5ba77b478ae727a.jpg
文章标签：
前端开发
存储
关键词：
数据结构队列
数据结构栈队列
数据结构栈
数据结构栈和队列
北海。
目录
相关文章
大数据文摘
|
7月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
246 1
hahaha无
|
5月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
118 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
|
5月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
143 0
RossyYan
|
10月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
500 77
蓝易云
|
9月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
229 11
羑悻的小杀马特
|
9月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
165 14
RossyYan
|
10月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
411 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
10月前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
236 7
ephemerals__
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
1019 9
那年春天
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
287 59

热门文章

最新文章

  • 1
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    R语言的数据结构
  • 4
    《Java核心技术 卷Ⅱ　高级特性（原书第10版）》一2.6.2　缓冲区数据结构
  • 5
    铁路（栈）
  • 6
    【数据结构】二叉树全攻略，从实现到应用详解
  • 7
    全局变量和局部变量在堆和栈的区别
  • 8
    【数据结构】—C语言实现双向链表（超详细!）
  • 9
    【C语言】学习笔记10——其他数据结构
  • 10
    数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
  • 1
    232.用栈实现队列，225. 用队列实现栈
    143
  • 2
    栈区的非法访问导致的死循环(x64)
    118
  • 3
    Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
    295
  • 4
    Redis设计与实现——数据结构与对象
    317
  • 5
    快速排序-数据结构与算法
    541
  • 6
    16.1k star! 只需要DDL就能一键生成数据库关系图！开源神器ChartDB让你的数据结构"看得见"
    1609
  • 7
    java实现队列数据结构代码详解
    246
  • 8
    Java 中 .length 的使用方法：深入理解 Java 数据结构中的长度获取机制
    759
  • 9
    线性数据结构详解
    218
  • 10
    为什么要学习数据结构与算法
    190

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云弹性公网IP线路类型【BGP(多线)_精品】是什么意思？