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

【数据结构初阶】详解：实现循环队列、用栈实现队列、用队列实现栈

news 来源：原创 2024/9/20 13:40:23

文章目录

  • 一、循环队列
    • 1、题目简述
    • 2、方法讲解
      • 2.1、了解tail的指向
      • 2.2、了解空间是如何利用的
      • 2.3、如何判断队列是否为空（假溢出问题）？
      • 2.4、实现代码
  • 二、用栈实现队列
    • 1、题目简述
    • 2、方法讲解
      • 2.1、讲解
      • 2.2、实现代码
  • 三、用队列实现栈
    • 1、题目简述
    • 2、方法讲解
      • 2.1、讲解
      • 2.2、实现代码
  • 四、谢谢观看

一、循环队列

1、题目简述

与队列的区别：循环队列的空间大小是固定的，且队尾连接队头形成循环。
在这里插入图片描述
要实现的方法：
在这里插入图片描述

2、方法讲解

我们开始就说过，循环队列的数据储存的数量是固定的，为了方便讲解，我们这里设队列可储存4个数据。即 k=4。

2.1、了解tail的指向

我们将队列的数据存放在数组中，head为队头下标，tail为队尾的下一个元素的下标。
在这里插入图片描述

tail为队尾的下一个元素的下标 原因：
若指向队尾数据：
当对列为空时，head、tail均指向首，即head=tail=0
而当队列有一个元素时，tail指向队尾，则仍有head=tail=0
产生歧义，无法区分队列是否有元素。
故，tail必须指向队尾元素的下一个元素

2.2、了解空间是如何利用的

注：队列遵循先进先出的规则
下面来举例了解数据的循环入队列：
1、入三个数据1,2，3
在这里插入图片描述

2、出两次数据
在这里插入图片描述
3、入三个数据4，5，6
在这里插入图片描述
在有限空间内，保证先进先出，空间重复使用。
那么问题来了：如何判断队列是否为空？

2.3、如何判断队列是否为空（假溢出问题）？

假溢出：空、满时判断条件相同。
在这里插入图片描述
此时无法区分空、满。
为了解决假溢出问题，我们有两种方法

  • 方法一：通过size来计录数据
    空：size = 0
    满：size = k (k:队列可储存数据个数)

  • 方法二：多开一个空间
    k = 4 (最多push入4个数据)
    在这里插入图片描述
    push入4个数据 1，2，3，4
    在这里插入图片描述
    空一个空间出来，则满的时候 head不可能等于tail，假溢出问题就解决了。
    已经入了4个数据了，想要再入数据就要先出数据，把空间空出来。

pop 出三次
在这里插入图片描述
push 入 5,6，7
在这里插入图片描述
由上可得：

空： head == tail
满： （tail+1）% （k+1）== head

2.4、实现代码

1、初始化
在这里插入图片描述
2、获取队首元素
在这里插入图片描述
3、取尾
在这里插入图片描述
在取尾返回时，也可写为
在这里插入图片描述

//数组
typedef struct {int* a;//数组下标int head;int tail;//指向尾的下一个int k;
} MyCircularQueue;//初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开k+1个数组空间obj->a = (int*)malloc(sizeof(int) * (k + 1));obj->head = obj->tail = 0;obj->k = k;return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k + 1) == obj->head;
}
//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj))return false;obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k + 1);return true;
}
//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;obj->head++;obj->head %= obj->k + 1;return true;
}
//找头
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->head];
}
//取尾
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->tail==0? obj->a[obj->k] : obj->a[obj->tail-1];
}//释放
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

二、用栈实现队列

1、题目简述

在这里插入图片描述
注意：C语言不支持栈，我们需要先模拟栈。
模拟栈在这里就不赘述了，以下是C语言模拟的栈：

typedef int STDataType;
typedef struct Stack
{STDataType* a;//指针指向数组int top;int capacity;//数组大小
}ST;//初始化与销毁
void STInit(ST* pst)
{assert(pst);//指针不为空pst->a = NULL;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素pst->top = 0;pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));//扩容是否成功if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//入栈：给数组（栈）放入值之后，top++pst->a[pst->top] = x;//数组a中的元素为xpst->top++;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素}
void STPop(ST* pst)//出栈：删除数据
{assert(pst);assert(pst->top > 0);//栈不为空pst->top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);return pst->a[pst->top - 1];//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//所以栈顶元素是pst->top-1
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//top为0，即为空，返回1//不为空，返回0
}//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}

2、方法讲解

  • 栈：从栈顶入、从栈顶出。满足先进后出。

       一种入栈顺序，可有多种（边进边出）出栈顺序

  • 队列：从队尾入、从队头出。满足先进先出。

    一种入队顺序，只有一种出队顺序。

使用两个栈，一个只入数据，一个只出数据。要用栈来实现队列的顺序特点。

2.1、讲解

在这里插入图片描述
1、入数据1,2，3,4
在这里插入图片描述
2、出数据
如果popst内的数据为空，就将pushst内的数据导入popst中，此时从popst中按栈的顺序出数据时，所出顺序即为队列的出数据顺序。
在这里插入图片描述
入的数据与出的数据的顺序相同，符合队列先进先出的逻辑。

2.2、实现代码

typedef int STDataType;
typedef struct Stack
{STDataType* a;//指针指向数组int top;int capacity;//数组大小
}ST;//初始化与销毁
void STInit(ST* pst)
{assert(pst);//指针不为空pst->a = NULL;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素pst->top = 0;pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));//扩容是否成功if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//入栈：给数组（栈）放入值之后，top++pst->a[pst->top] = x;//数组a中的元素为xpst->top++;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素}
void STPop(ST* pst)//出栈：删除数据
{assert(pst);assert(pst->top > 0);//栈不为空pst->top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);return pst->a[pst->top - 1];//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//所以栈顶元素是pst->top-1
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//top为0，即为空，返回1//不为空，返回0
}//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}
//两个栈实现队列
typedef struct {ST pushst; //入数据ST popst;  //出数据
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}
//入队
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);
}
//出队
int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj); //队头STPop(&obj->popst);return front;
}
//找队头
int myQueuePeek(MyQueue* obj) {//如果popst为空，就倒数据，倒完的popst的顺序为先进先出if(STEmpty(&obj->popst)){//倒数据while(!STEmpty(&obj->pushst)){int top = STTop(&obj->pushst);STPush(&obj->popst,top);STPop(&obj->pushst);}}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);
}

三、用队列实现栈

1、题目简述

在这里插入图片描述
C语言模拟的队列：

typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//可避免使用二级指针和传多个参数
{int size;//size为每个节点的编号，每增加一个，size++QNode* phead;QNode* ptail;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = NULL;pq->ptail = NULL;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc error");return;}newnode->next = NULL;newnode->val = x;if (pq->phead == NULL)//原队列无节点{pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//只有一个if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}//多个节点else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//找头数据
QDataType QueueFront(Queue* pq)
{assert(pq);//assert(pq->phead);return pq->phead->val;
}//找尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//统计个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2、方法讲解

在这里插入图片描述

2.1、讲解

1、入栈 1,2，3,4
判断哪一个队列为空，入到为空的队列中
在这里插入图片描述
2、删除栈顶数据
将不为空的队列中的队尾数据之前的所有数据导入为空的队列中，而原队列中只剩下要删除的元素。
在这里插入图片描述

//删除栈顶元素
int myStackPop(MyStack* obj) {//将该队列队尾之前的元素（size-1）push到空的队列中//原队列中只剩下要删除的元素Queue* empty = &obj->q1;Queue* nonEmpty = &obj->q2;if (!QueueEmpty(&obj->q1)){empty = &obj->q2;nonEmpty = &obj->q1;}while (QueueSize(nonEmpty) > 1){QueuePush(empty, QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}

2.2、实现代码

//两个队列实现栈（后进先出）
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//可避免使用二级指针和传多个参数
{int size;//size为每个节点的编号，每增加一个，size++QNode* phead;QNode* ptail;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = NULL;pq->ptail = NULL;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc error");return;}newnode->next = NULL;newnode->val = x;if (pq->phead == NULL)//原队列无节点{pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//只有一个if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}//多个节点else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//找头数据
QDataType QueueFront(Queue* pq)
{assert(pq);//assert(pq->phead);return pq->phead->val;
}//找尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//统计个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}typedef struct {//匿名结构体Queue q1;Queue q2; //两个队列
} MyStack;//初始化
MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//malloc开辟的空间在出函数后不会销毁QueueInit(&obj->q1);QueueInit(&obj->q2);//优先级->高于&return obj;
}
//入栈
void myStackPush(MyStack* obj, int x) {//push到不为空的队列中if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}}
//删除栈顶元素
int myStackPop(MyStack* obj) {//将该队列队尾之前的元素（size-1）push到空的队列中//原队列中只剩下要删除的元素Queue* empty = &obj->q1;Queue* nonEmpty = &obj->q2;if (!QueueEmpty(&obj->q1)){empty = &obj->q2;nonEmpty = &obj->q1;}while (QueueSize(nonEmpty) > 1){QueuePush(empty, QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}
//找栈顶元素
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);
}

四、谢谢观看

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 通过内网穿透远程访问自己的项目
  • 【力扣】3128. 直角三角形 JAVA
  • matlab y=sin(x) - 2/π*(x)函数绘制
  • 1.1、centos stream 9安装Kubernetes v1.30集群 环境说明
  • CSS mask-image 实现边缘淡出过渡效果
  • Flink-CDC解析（第47天）
  • 【机器学习】机器学习与医疗健康在疾病预测中的融合应用与性能优化新探索
  • CANopen和CAN是什么关系
  • Resilience4j 数据库熔断-健康检查sql
  • C# Web控件与数据感应之 TreeView 类
  • 【数据结构算法经典题目刨析（c语言）】随机链表的复制（图文详解）
  • 【人工智能】Transformers之Pipeline（三）：文本转音频（text-to-audio/text-to-speech）
  • 仓颉语言 -- 宏
  • vue项目中，前端如何配置跨域请求
  • C语言 -- 动态内存管理
  • (ckeditor+ckfinder用法)Jquery,js获取ckeditor值
  • Android系统模拟器绘制实现概述
  • Angular js 常用指令ng-if、ng-class、ng-option、ng-value、ng-click是如何使用的？
  • CentOS学习笔记 - 12. Nginx搭建Centos7.5远程repo
  • Elasticsearch 参考指南（升级前重新索引）
  • javascript 总结（常用工具类的封装）
  • JavaScript/HTML5图表开发工具JavaScript Charts v3.19.6发布【附下载】
  • javascript数组去重/查找/插入/删除
  • JS创建对象模式及其对象原型链探究（一）：Object模式
  • Mithril.js 入门介绍
  • nodejs：开发并发布一个nodejs包
  • Nodejs和JavaWeb协助开发
  • Work@Alibaba 阿里巴巴的企业应用构建之路
  • 电商搜索引擎的架构设计和性能优化
  • 分享一份非常强势的Android面试题
  • 机器人定位导航技术 激光SLAM与视觉SLAM谁更胜一筹？
  • 基于Android乐音识别(2)
  • 聊聊flink的TableFactory
  • 使用SAX解析XML
  • 微信小程序填坑清单
  • 学习笔记TF060:图像语音结合，看图说话
  • HanLP分词命名实体提取详解
  • ### RabbitMQ五种工作模式：
  • #1015 : KMP算法
  • (2009.11版)《网络管理员考试 考前冲刺预测卷及考点解析》复习重点
  • (6) 深入探索Python-Pandas库的核心数据结构：DataFrame全面解析
  • （安全基本功）磁盘MBR，分区表，活动分区，引导扇区。。。详解与区别
  • （二）linux使用docker容器运行mysql
  • （二）pulsar安装在独立的docker中，python测试
  • （二十四）Flask之flask-session组件
  • （附源码）springboot“微印象”在线打印预约系统 毕业设计 061642
  • （论文阅读23/100）Hierarchical Convolutional Features for Visual Tracking
  • （十一）手动添加用户和文件的特殊权限
  • （数据结构）顺序表的定义
  • （学习日记）2024.01.09
  • （转）PlayerPrefs在Windows下存到哪里去了？
  • .net 8 发布了，试下微软最近强推的MAUI
  • .NET/C# 反射的的性能数据，以及高性能开发建议（反射获取 Attribute 和反射调用方法）
  • .NET/C# 获取一个正在运行的进程的命令行参数
  • .net开发引用程序集提示没有强名称的解决办法