《重生之霸道总裁爱上学数据结构的我（三）》之没人比我更懂栈和队列

Ne0inhk

— 12 min read
《重生之霸道总裁爱上学数据结构的我（三）》之没人比我更懂栈和队列

个人主页-爱因斯晨

文章专栏-霸道总裁爱上学数据结构的我

在这里插入图片描述

一、前言

我们在前两篇文章中讲到顺序表和链表其都是线性结构，我们今天讲的栈和队列也是特殊的线性表。顺序表和链表没有所谓的进出限制，但是我们今天要讲的栈就不一样，他有特殊的进栈和出栈顺序，只允许在一端进行插入和删除。也就是说后进先出，先进后出。但是队列呢，只允许从前面插入，后面出。也就是他俩是特殊的线性结构，所以在基本操作上和前文的线性表和链表有一定相似之处。

二、栈

在这里插入图片描述

只允许在一端进行插入和删除操作的线性表

空栈，没有元素。

栈顶允许插入和删除，栈底不允许。

2.1顺序栈

就是用顺序方式存储的栈就是顺序栈。

在这里插入图片描述

顺序栈的定义

这里用top指针来标记栈顶位置，初始化时top = -1，表示栈是空的。就像刚买的空盘子架，还没放任何盘子。

#defineMAXSIZE100//栈的最大容量#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstruct{//顺序栈的结构体int data[100];//栈的数组int top;//栈顶指针}SqStack;//顺序栈的类型定义

初始化

//初始化操作voidInitStack(SqStack *S){ S->top =-1;//将栈顶指针设为-1}//判断栈是否为空 bool StackEmpty(SqStack *S){if(S->top ==-1){return true;//栈为空}else{return false;//栈不为空}}

进栈操作

进栈就像往盘子架上放新盘子，只能放在最上面：

//进栈操作 bool Push(SqStack *S,int x){if(S->top == MAXSIZE){return false;//栈满} S->top++;//栈顶指针加1 S->data[S->top]= x;//将x入栈return true;//入栈成功}

先检查栈是不是满了（top等于最大容量），没满的话就把top往上挪一位，再把数据放进去。

出栈操作

出栈则是从最上面拿走一个盘子：

//出栈操作 bool Pop(SqStack *S,int*x){if(S->top ==-1){return false;//栈为空}*x = S->data[S->top];//将栈顶元素出栈 S->top--;//栈顶指针减1return true;//出栈成功}

先检查栈是不是空的，不空的话就把栈顶元素取出来，再把top往下挪一位。

获取栈顶元素

有时候我们只想看看最上面的盘子是啥样，不想拿走它：

//获取栈顶元素 bool GetTop(SqStack *S,int*x){if(S->top ==-1){return false;//栈为空}*x = S->data[S->top];//将栈顶元素赋值给xreturn true;//获取成功}

这个操作和出栈的区别是，top指针不会移动，只是 “偷看” 一眼。

2.2共享栈

共享栈是个节省空间的小能手，它让两个栈共享同一块数组空间，栈底分别在数组的两端，向中间生长。就像两个霸道总裁共用一个衣帽间，一人占一边，谁也不打扰谁。

在这里插入图片描述

建立

//共享栈建立typedefstruct{//共享栈的结构体int data[100];//栈的数组int top;//栈顶指针int top1;//栈底指针}SharedStack;//共享栈的类型定义

初始化

初始化时，第一个栈的top在 - 1，第二个栈的top1在最大容量处：

//初始化voidInitSharedStack(SharedStack *S){ S->top =-1;//将栈顶指针设为-1 S->top1 = MAXSIZE;//将栈顶指针设为最大容量}

这样两个栈就可以向中间扩展，直到top + 1 == top1时，表示栈满。

2.3链栈

链栈就是用链表实现的栈，链表的头结点作为栈顶，这样进栈和出栈操作都能在 O (1) 时间内完成，比顺序栈更灵活（不用提前规定大小）。

建立

//链栈建立typedefstruct{int data[100];int top;//栈顶指针structLinkNode*next;//指向下一个节点的指针}LinkStack;//链栈的类型定义

这里栈顶指针就是链表的头指针，进栈就是在头结点前插入新节点，出栈就是删除头结点。

三、队列

在这里插入图片描述

队列和栈正好相反，它是 “先进先出”（FIFO，First In First Out）的，就像排队买奶茶 —— 先到的人先拿到奶茶。只能在队尾插入（入队），在队头删除（出队）。

顺序队列用数组实现，但有个小问题：如果单纯地让front指向队头，rear指向队尾，随着入队和出队操作，front和rear都会往后移动，可能导致数组前面的空间浪费。

定义

初始化时，front和rear都指向 0：

//队列定义typedefstruct{int data[100];//队列的数组int front;//队头指针int rear;//队尾指针}SqQueue;//链队列的类型定义

初始化队列

//初始化队列 void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; //将队头指针和队尾指针设为0 }

判断队列是否为空

//判断队列是否为空 bool QueueEmpty(SqQueue *Q){if(Q->front == Q->rear){return true;//队列为空}else{return false;//队列不为空}}

入队操作

//入队操作 bool EnQueue(SqQueue *Q,int x){if(Q->rear == MAXSIZE){return false;//队列满} Q->data[Q->rear]= x;//将x入队 Q->rear++;//队尾指针加1return true;//入队成功}

把数据放在rear指向的位置，再把rear往后挪一位。

出队操作

//出队操作 bool DeQueue(SqQueue *Q,int*x){if(Q->front == Q->rear){return false;//队列为空}*x = Q->data[Q->front];//将队头元素赋值给x Q->front++;//队头指针加1return true;//出队成功}

取出front指向的元素，再把front往后挪一位。

判断队列的满和空

法一：

上面的方法有个缺陷：rear到达数组末尾时，即使前面有空位，也会被判为队满。解决这个问题有几种方法：

//判断队列是否为空 bool GetHead(SqQueue Q,int*x){if(Q.rear==Q.front)//队列为空return false;*x=Q.data[Q.front];//将队头元素赋值给xreturn true;}

法二：定义长度问题

增加一个size变量记录队列长度，队满条件是size == MaxSize，队空条件是size == 0。

#defineMaxSize10typedefstruct{int data[10];int front,rear;int size;//队列当前长度}SqQueue;//插入成功：size++ 删除成功size--//初始化时：rear=front=0,size=0//队满条件：size==MaxSize //队空条件：size==0

法三：

增加一个tag变量，记录最近操作是插入（1）还是删除（0）。队满条件是front == rear && tag == 1，队空条件是front == rear && tag == 0。

#defineMaxSize10typedefstruct{int data[10];int front,rear;int tag;//最近进行的是删除/插入 初始化时，rear=front=0;tag=0}SqQueue;

每次删除操作成功时，都令tag=0

每次插入操作成功时，都令tag=1

只有删除操作，才可能导致队空，只有插入操作，才可能导致队满

队满条件：frontrear&&tag1

队空条件：frontrear&&tag0

链式存储实现队列

链式队列用链表实现，队头指针指向头结点，队尾指针指向最后一个节点，这样入队和出队操作都很方便。

定义一个链式队列

//链队列的节点类型定义typedefstructLinkNode{int data;//数据域structLinkNode*next;//指向下一个节点的指针}LinkNode;//链队列的节点类型定义typedefstruct{ LinkNode *front ,*rear;//队头指针和队尾指针}LinkQueue;//链队列的类型定义

初始化（带头结点）

头结点不存数据，只是为了操作方便。

//初始化链队列voidInitoQueue(LinkQueue *Q){//初始时队头指针和队尾指针都指向头结点 Q->front = Q->rear =(LinkNode *)malloc(sizeof(LinkNode)); Q->front->next =NULL;//头结点的next指针设为NULL}//判断队列是否为空 bool QueueoEmpty(LinkQueue *Q){if(Q->front == Q->rear){return true;//队列为空}else{return false;//队列不为空}}

初始化队列不带头结点

//判断队列是否为空 bool QueueoEmpty(LinkQueue *Q) { if (Q->front == Q->rear) { return true; //队列为空 } else { return false; //队列不为空 } }

入队（带头结点）

入队就是在队尾添加新节点，然后把rear移到新节点。

//入队操作（带头结点） bool EnQueueo(LinkQueue *Q,int x){//创建一个新节点 LinkNode *s =(LinkNode *)malloc(sizeof(LinkNode));if(s ==NULL){return false;//内存分配失败} s->data = x;//将x赋值给新节点的数据域 s->next =NULL;//将新节点的next指针设为NULL Q->rear->next = s;//将原队尾节点的next指针指向新节点 Q->rear = s;//将队尾指针指向新节点return true;//入队成功}

入队（不带头结点）

//入队操作（不带头结点） bool EnQueueo(LinkQueue *Q,int x){//创建一个新节点 LinkNode *s =(LinkNode *)malloc(sizeof(LinkNode));if(s ==NULL){return false;//内存分配失败} s->data = x;//将x赋值给新节点的数据域 s->next =NULL;//将新节点的next指针设为NULL//若队列为空（首次入队），队头和队尾都指向新节点if(QueueoEmpty(Q)){ Q->front = s; Q->rear = s;}else{//队列非空时，队尾节点的next指向新节点，再移动队尾指针 Q->rear->next = s; Q->rear = s;}return true;//入队成功}

不带头结点的链式队列入队操作，核心区别在于需要处理 “首次入队” 的特殊情况：

  • 当队列是空的时候（front和rear都为NULL），新节点既是队头也是队尾，所以front和rear要同时指向这个新节点
  • 非空队列时，操作和带头结点类似：让当前队尾的next指向新节点，再把rear移到新节点上

出队（带头结点）

// 出队操作（带头结点） bool DeQueueo(LinkQueue *Q,int*x){// 队列为空时无法出队if(QueueoEmpty(Q)){return false;} LinkNode *p = Q->front->next;// p指向队头元素节点*x = p->data;// 保存出队元素的值 Q->front->next = p->next;// 头结点跳过队头元素，指向其后继// 若出队的是最后一个元素，队尾指针需指向头结点（保持空队列状态）if(Q->rear == p){ Q->rear = Q->front;}free(p);// 释放出队节点的内存return true;}
  • 队头元素始终是 front->next 指向的节点（头结点不存储数据）
  • 出队时只需修改头结点的 next 指针，最后一个元素出队时需将 rear 重置为头结点

出队（不带头结点）

// 出队操作（不带头结点） bool DeQueueo(LinkQueue *Q,int*x){// 队列为空时无法出队if(QueueoEmpty(Q)){return false;} LinkNode *p = Q->front;// p指向队头元素节点（不带头结点时front直接指向队头）*x = p->data;// 保存出队元素的值// 若队列只有一个元素，出队后队头队尾均置空if(Q->front == Q->rear){ Q->front = Q->rear =NULL;}else{// 队列有多个元素时，队头指针后移 Q->front = Q->front->next;}free(p);// 释放出队节点的内存return true;}
  • 队头指针 front 直接指向队头元素（首个数据节点）
  • 出队时需直接移动 front 指针，最后一个元素出队后需将 front 和 rear 均置为 NULL

队列满的条件

顺序存储，预分配的空间耗尽时队满

链式存储，一般不会队满，除非内存不足

四、总结：

栈和队列都是特殊的线性表，只是对操作的位置做了限制：

  • 栈：只允许在栈顶操作，后进先出
  • 队列：只允许在队尾入队、队头出队，先进先出

它们的实现可以用数组（顺序存储）或链表（链式存储），各有优缺点：

  • 顺序存储：访问快，但大小固定（或需要扩容）
  • 链式存储：大小灵活，但访问需要遍历指针

就像霸道总裁的两种处事风格：栈是 “后来者居上”，队列是 “按规矩办事”，各有各的适用场景。掌握它们的逻辑和实现，对于理解更复杂的数据结构至关重要。

Read more

从零开始打造高性能数据结构——手把手教你实现环形缓冲

从零开始打造高性能数据结构——手把手教你实现环形缓冲

◆ 博主名称： 小此方-ZEEKLOG博客 大家好，欢迎来到小此方的博客。 ⭐️个人专栏：《C语言》_小此方的博客-ZEEKLOG博客 算法_小此方的博客-ZEEKLOG博客  ⭐️踏破千山志未空，拨开云雾见晴虹。 人生何必叹萧瑟，心在凌霄第一峰。 目录 一，普通队列的劣势 1. 空间浪费严重（“假溢出”问题） 2. 需要频繁移动元素（若避免浪费） 3. 扩容成本高 4. 无法解决“假溢出”导致的提前扩容 二，环形缓冲结构分析  1. “循环”取模实现指针回绕  2.“循环”，轮流入座而不是排长队 三，实现环形缓冲 1，MyCircularQueue(k): 构造器   1，结构体搭建   2，初始化 3，为什么选择k+1块空间而不是k块空间？

By Ne0inhk
C++ 容器适配器与核心数据结构精解：栈、队列、deque 底层实现与实战应用----《Hello C++ Wrold!》(17)--(C/C++)

C++ 容器适配器与核心数据结构精解：栈、队列、deque 底层实现与实战应用----《Hello C++ Wrold!》(17)--(C/C++)

文章目录 * 前言 * stack * 其中常用的接口 * stack的模拟实现 * queue * 其中常见的接口 * queue的模拟实现 * deque * 常见接口 * 容器适配器 * priority_queue * 常用接口 * priority_queue模拟实现 * 反向迭代器的模拟实现 * 仿函数(又叫函数对象) * 作业部分 * 逆波兰表达式 * 引申 前言 在 C++ 标准库的庞大体系中，数据结构是支撑高效编程的基石，而容器适配器、序列容器以及相关的算法逻辑，则是其中最具实用价值的核心内容。无论是日常开发还是算法刷题，栈（stack）、队列（queue）、优先级队列（priority_queue）这些 “常客” 的身影几乎无处不在，它们看似简单的接口背后，藏着对数据存取规则的精妙设计 —— 栈的 “先进后出” 适配递归调用、括号匹配等场景，队列的 “先进先出” 适配层序遍历、

By Ne0inhk
【LeetCode经典题解】二叉树层序遍历：从思路拆解到代码实现，手把手教你搞定！

【LeetCode经典题解】二叉树层序遍历：从思路拆解到代码实现，手把手教你搞定！

🎁个人主页：User_芊芊君子 🎉欢迎大家点赞👍评论📝收藏⭐文章 🔍系列专栏：Java.数据结构 【前言】 二叉树的层序遍历是面试高频考点之一，它要求“逐层、从左到右”访问树的所有节点，最终返回每层节点值组成的二维列表。本文将通过一段代码，图文并茂的方式拆解其实现思路与核心逻辑。 文章目录: * 一、二叉树层序遍历 * 二、思路分析 * 1.初始化“容器” * 2.空树处理： * 3.辅助：队列 * 4.循环逻辑处理 * 4.1 外层循环 * 4.2 内层循环 * 三、代码展示 * 四、总结 一、二叉树层序遍历 二叉树层序遍历遵循“从上到下，从左到右”的原则访问树的所有节点，

By Ne0inhk
【算法通关指南：算法基础篇】 二维前缀和专题： 1. 【模板】二维度前缀和，2.激光炸弹

【算法通关指南：算法基础篇】 二维前缀和专题： 1. 【模板】二维度前缀和，2.激光炸弹

《算法通关指南：算法基础篇 ---- 二维前缀和 — 1. 【模板】二维度前缀和，2.激光炸弹》 🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南 》 ✨ 永远相信美好的事情即将发生 文章目录 * 《算法通关指南：算法基础篇 ---- 二维前缀和 — 1. 【模板】二维度前缀和，2.激光炸弹》 * 前言 * 一、二维前缀和 * 1.1 核心问题 * 1.1.1 创建前缀和矩阵 * 2.2.2 查询以(x1 , y1)为左上角,(x2 , y2)为右下角的子矩阵的和 * 二、

By Ne0inhk