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

【数据结构】详细介绍栈和队列，解析栈和队列每一处细节

news 来源：原创 2024/9/21 4:36:11

目录

一. 栈

1. 栈的概念

2. 栈的实现

2.1 栈的结构

2.2 初始化栈

2.3 入栈

2.4 出栈

2.5 获取栈顶元素

2.6 获取栈中有效个数

2.7 判断栈是否为空

2.8 销毁栈 

二. 队列

1. 队列的概念

2. 队列的实现 

2.1 队列的结构

2.2 队列初始化 

2.3 销毁队列 

2.4 入队列(队尾) 

2.5 出队列(队头) 

2.6 获取队头数据 

2.7 获取队尾数据 

2.8 获取队列节点个数 

2.9 判断队列是否为空 

3. 循环队列

4. 编程题 设计循环队列 

三. 概念题

一. 栈

1. 栈的概念

1. 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

2. 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

3. 栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

4. 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

5. 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2. 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。

2.1 栈的结构

1. top表示栈顶数据的下一个位置。

typedef int StackDataType;
typedef struct Stack
{StackDataType* arr; //用数组作为存放栈数据的结构int top;			//栈顶数据的下一个位置int capacity;		//容量
}Stack;

2.2 初始化栈

1. 将结构数据初始化。

void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}

2.3 入栈

1. 判断扩容。

2. 数据插入栈顶。

void StackPush(Stack* ps, StackDataType data)
{assert(ps);//判断扩容if (ps->top == ps->capacity){int size = ps->capacity == 0 ? 4 : ps->capacity * 2;StackDataType* tmp = (StackDataType*)realloc(ps->arr, sizeof(StackDataType)*size);if (tmp == NULL){perror("realloc");return;}ps->arr = tmp;ps->capacity = size;}//入栈ps->arr[ps->top++] = data;
}

2.4 出栈

1. 栈不为空才能出栈。

void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}

2.5 获取栈顶元素

1. 判断空栈

StackDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

2.6 获取栈中有效个数

int StackSize(Stack* ps)
{assert(ps);return ps->top;
}

2.7 判断栈是否为空

1. 栈空返回真。

bool StackEmpty(Stack* ps)
{assert(ps);return !ps->top;
}

2.8 销毁栈 

1. 释放空间，初始数据。

void StackDestroy(Stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

 完整代码：Stack/Stack · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

二. 队列

1. 队列的概念

1. 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

2. 队列具有先进先出FIFO(First In First Out)的特点。

3. 入队列：进行插入操作，这一端称为队尾。

4. 出队列：进行删除操作，这一端称为队头。

2. 队列的实现 

队列也可以使用数组或链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1 队列的结构

1. 需要两个结构体，一个表示节点，一个表示队列整体。

2. 节点的结构包含存放的数据和指向下一个节点的指针。

3. 表示队列的结构包含队头指针和队尾指针还有节点的数量。

typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType data;     //数据struct QueueNode* next; //下一个节点地址
}QueueNode;typedef struct Queue
{QueueNode* prev; //队头指针QueueNode* tail; //队尾指针size_t size;     //节点个数
}Queue;

2.2 队列初始化 

1. 传入的队列指针不能为空。

2. 将队列结构体中队头队尾指针置空，节点数量置0。

void QueueInit(Queue* q)
{assert(q);q->prev = q->tail = NULL;q->size = 0;
}

2.3 销毁队列 

1. 传入的队列指针不能为空。

2. 从队头指针开始遍历释放节点直到空停下，并将队头队尾指针置空，节点数量置0。

void QueueDestroy(Queue* q)
{assert(q);while (q->prev){QueueNode* next = q->prev->next;free(q->prev);q->prev = next;}q->tail = NULL;q->size = 0;
}

2.4 入队列(队尾) 

1. 传入的队列指针不能为空。

2. 创建要入队列的节点

3. 当队列为空时，将队头队尾指针都指向新节点，节点数量加一。

4. 当队列不为空时，将新节点和最后一个节点连接，然后队尾指针指向新节点，节点数量加一。

void QueuePush(Queue* q, QueueDataType data)
{//1. 传入的队列指针不能为空。assert(q);//2. 创建要入队列的节点QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));if (new == NULL){perror("malloc");return;}new->data = data;new->next = NULL;//3. 当队列为空时，然后将队头队尾指针都指向新节点，节点数量加一。if (q->size == 0){q->prev = q->tail = new;q->size++;}//4. 当队列不为空时，将新节点和最后一个节点连接，然后队尾指针指向新节点，节点数量加一。else{q->tail->next = new;q->tail = new;q->size++;}
}

2.5 出队列(队头) 

1. 传入的队列指针不能为空。

2. 队列不能为空。

3. 释放第一个节点，队头指针指向第二个节点，节点数量减一。

4. 当队列删完之后没有节点了，这种情况需要特殊处理，防止队尾指针变成野指针。

void QueuePop(Queue* q)
{//1. 传入的队列指针不能为空。assert(q);//2. 队列不能为空。assert(q->size);//3. 释放第一个节点，队头指针指向第二个节点，节点数量减一。QueueNode* next = q->prev->next;free(q->prev);q->prev = next;q->size--;//4. 当队列删完之后没有节点了，这种情况需要特殊处理，防止队尾指针变成野指针。if (q->size == 0) q->tail = NULL;
}

2.6 获取队头数据 

1. 队列指针不能为空。

2. 队列不能为空。

3. 返回队头节点存放的数据。

QueueDataType QueueFront(Queue* q)
{//1. 队列指针不能为空。assert(q);//2. 队列不能为空。assert(q->size);//3. 返回队头节点存放的数据。return q->prev->data;
}

2.7 获取队尾数据 

1. 队列指针不能为空。

2. 队列不能为空。

3. 返回队尾节点存放的数据。

QueueDataType QueueBack(Queue* q)
{//1. 队列指针不能为空。assert(q);//2. 队列不能为空。assert(q->size);//3. 返回队尾节点存放的数据。return q->tail->data;
}

2.8 获取队列节点个数 

1. 队列指针不能为空。

2. 返回节点个数。

int QueueSize(Queue* q)
{//1. 队列指针不能为空。assert(q);//2. 返回节点个数。return q->size;
}

2.9 判断队列是否为空 

1. 队列指针不能为空。

2. 根据节点数量判断。空返回真。

bool QueueEmpty(Queue* q)
{//1. 队列指针不能为空。assert(q);//2. 根据节点数量判断。空返回真。return !q->size;
}

完整代码： Queue/Queue · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

3. 循环队列

1. rear的位置插入数据，然后rear++。

2. pop一次就是front往前移一位。

3. front == rear 表示空。

4. rear+1 == front 表示满，记得取模。

5. 这里使用数组实现，因为单链表不方便获取队尾数据。

4. 编程题 设计循环队列 

链接：. - 力扣（LeetCode）

typedef struct 
{int* arr;  //指向队列int front; //队头下标int rear;  //队尾下标int k;     
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->arr = (int*)malloc(sizeof(int)*(k+1));obj->front = obj->rear = 0;obj->k = k;return obj;    
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{//队头下标等于队尾下标时为空。return obj->front == obj->rear;    
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{//队尾下标加一等于队头下标时为满，超出数组范围需要取模。return (obj->rear+1) % (obj->k+1) == obj->front;    
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{//满了不能插入。if(myCircularQueueIsFull(obj)) return false;else{//在队尾放数据，然后队尾加一，记得取模。obj->arr[obj->rear] = value;obj->rear = (obj->rear+1) % (obj->k+1);return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{//空的不能删。if(myCircularQueueIsEmpty(obj)) return false;else{//删除数据队头下标直接加一即可，记得取模。obj->front = (obj->front+1) % (obj->k+1);return true;}    
}int myCircularQueueFront(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)) return -1;return obj->arr[obj->front];    
}int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)) return -1;//当rear等于0时需要特殊处理return obj->arr[(obj->rear-1+obj->k+1)%(obj->k+1)];  
}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->arr);   free(obj);
}

三. 概念题

一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

答：B

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

答：C

循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（ ）

A 1

B 2

C 99

D 0或者100

答：D

以下( )不是队列的基本运算？

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值 

答：B

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)

A (rear - front + N) % N + 1

B (rear - front + N) % N

C (rear - front) % (N + 1)

D (rear - front + N) % (N - 1) 

答：B

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 基础第3关：LangGPT结构化提示词编写实践
  • VS2022上面运行QT程序
  • docker-实战——consul集群
  • 如何将老照片修复模糊照片变清晰？照片修复方法
  • 宏定义———C语言
  • 数据结构之排序（下）
  • 【图像去雾系列】使用SSR/MSR/MSRCR/MSRCP/automatedMSRCR算法对单图像进行图像增强，达到去雾效果
  • 【C++二分查找 前缀和 】1292. 元素和小于等于阈值的正方形的最大边长
  • 主流AI绘画工具StableDiffusion最新模型sd3本地部署方法（附工作流）
  • 螺旋矩阵 II（LeetCode）
  • ros2_control_py 使用教程
  • Java二十三种设计模式-备忘录模式（19/23）
  • SPDY是何方神圣
  • \r和\n不同系统的区别
  • SpringBoot注解大总结
  • 实现windows 窗体的自己画，网上摘抄的，学习了
  • 【162天】黑马程序员27天视频学习笔记【Day02-上】
  • Brief introduction of how to 'Call, Apply and Bind'
  • python_bomb----数据类型总结
  • SAP云平台运行环境Cloud Foundry和Neo的区别
  • tensorflow学习笔记3——MNIST应用篇
  • vue-router的history模式发布配置
  • 构建工具 - 收藏集 - 掘金
  • 判断客户端类型，Android，iOS，PC
  • 使用common-codec进行md5加密
  • 手机app有了短信验证码还有没必要有图片验证码？
  • 数据可视化之 Sankey 桑基图的实现
  • ​iOS安全加固方法及实现
  • #设计模式#4.6 Flyweight（享元） 对象结构型模式
  • （3）选择元素——（17）练习（Exercises）
  • (31)对象的克隆
  • (55)MOS管专题---＞(10)MOS管的封装
  • (cljs/run-at (JSVM. :browser) 搭建刚好可用的开发环境!)
  • （DFS + 剪枝）【洛谷P1731】 [NOI1999] 生日蛋糕
  • （JSP）EL——优化登录界面，获取对象，获取数据
  • （附源码）spring boot球鞋文化交流论坛 毕业设计 141436
  • （六）vue-router+UI组件库
  • （论文阅读22/100）Learning a Deep Compact Image Representation for Visual Tracking
  • (一)基于IDEA的JAVA基础12
  • (原創) X61用戶，小心你的上蓋!! (NB) (ThinkPad) (X61)
  • (转)大型网站架构演变和知识体系
  • (转)四层和七层负载均衡的区别
  • (转载)hibernate缓存
  • .bat批处理（十）：从路径字符串中截取盘符、文件名、后缀名等信息
  • .form文件_一篇文章学会文件上传
  • .NET 8.0 中有哪些新的变化？
  • .NET Core 实现 Redis 批量查询指定格式的Key
  • .NET core 自定义过滤器 Filter 实现webapi RestFul 统一接口数据返回格式
  • .Net8 Blazor 尝鲜
  • .NetCore+vue3上传图片 Multipart body length limit 16384 exceeded.
  • .NET教程 - 字符串 编码 正则表达式（String Encoding Regular Express）
  • .net专家（高海东的专栏）
  • @31省区市高考时间表来了，祝考试成功
  • []使用 Tortoise SVN 创建 Externals 外部引用目录
  • [AI Embedchain] 开始使用 - 全栈