当前位置:网站首页>I 用c l 栈与队列的相互实现
I 用c l 栈与队列的相互实现
2022-07-05 07:22:00 【MT_125】
目录
一、用对列实现栈
题干要求:
细节分析:队列是先进先出; 要实现的栈是先进后出。
解题思路:假设:先用一个队列储存数据 N 个,然后将前 N-1 个数据导入到另一个队列,
此时,原始队列中仅剩一个,是最后剩的数据,便可将其导出,这便是一次后进先出。
细节点 :每次导出数据时,都需要一个队列向另一个队列传入数据,因此输入队列和输出队列 需要轮换,要对其进行判定。
具体过程gif动态图如下:
代码实现:
1.初始化栈:先初始化两个队列
//栈的结构是由两个队列构成
typedef struct Nystack{
Quetail q1;
Quetail q2;
} MyStack;
//栈的初始化
MyStack* myStackCreate() {
MyStack* Newstack = (MyStack*)malloc(sizeof(MyStack));
Que_Init(&Newstack->q1);
Que_Init(&Newstack->q2);
return Newstack;
}
2. 插入数据
因为存储数据的队列不是固定的,因此在一个队列有数据的前提下,就继续向该队列插入数据,
空的队列负责在导出数据时进行轮转。(哪个不空向哪个插入)
//插入数据
void myStackPush(MyStack* obj, int x) {
//if((&obj->q1)->head == NULL) //法一:直接判断是否为空
if(Que_Empty(&obj->q1)) //法二:后续函数的复用
Que_push(&obj->q2,x);
else
Que_push(&obj->q1,x);
}
3.导出数据(实现先进后出)
第一步:将有数据的队列中除最后进的数据,依次导入到另一个空队列 ;
导入空队列,删除原队列,保留最后数据。
第二布:将原队列中最后一个数据导出 。
注:这里先假设了两个队列中,一个是原队列和一个是空队列,再进行判定,若与实际不符,则 交换 。
int myStackPop(MyStack* obj) {
int temp = 0;
//假设原队列和空队列
Quetail* existque = &obj->q1,*nullque = &obj->q2;
if((&obj->q1)->head == NULL) //判断与实际是否相符
{
existque = nullque;
nullque = &obj->q1;
}
for(;existque->head->Next;) //保留最后一个数据
{
Que_push(nullque,existque->head->data); //向空队列导入数据
Que_pop(existque); //删除原队列数据
}
temp = existque->head->data;
Que_pop(existque); //导出最后进的数据
return temp;
}
4.查找栈顶数据
找到不空的队列 >> 返回其队尾的数据
int myStackTop(MyStack* obj) {
if((&obj->q1)->head == NULL)
{
return (&obj->q2)->tail->data;
}
return (&obj->q1)->tail->data;
}
5.判断栈是否为空:
判断两个队列是否均为空
bool myStackEmpty(MyStack* obj) {
assert(obj);
//法一:直接判断
//if((&obj->q1)->head == NULL&& (&obj->q2)->head == NULL)
//法二:复用队列判空函数
if(Que_Empty(&(obj->q1))&&Que_Empty(&(obj->q2)))
return true;
return false;
}
6.销毁栈:
销毁两个队列
void myStackFree(MyStack* obj) {
Que_Destory(&obj->q1);
Que_Destory(&obj->q2);
free(obj);
}
二、用栈实现队列
题干要求:
细节分析:这次是用两个栈,实现先进先出 。
解题思路:首先,将两个栈分为入口栈和出口栈,
其次,数据正序入口栈,由于栈是先进后出,因此将数据再逆序进入出口栈,
然后,此时数据再出口栈中是逆序,所以,便可以正序从出口栈中依次排出 。
代码实现:
1.初始化双栈队列
typedef struct {
Stack T1;
Stack T2;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue *Q1;
Q1 = (MyQueue*)malloc(sizeof(MyQueue));
Stack_init(&(Q1->T1)); // T1 做入口栈
Stack_init(&(Q1->T2)); // T2 做出口栈
return Q1;
}
2.插入数据
void myQueuePush(MyQueue* obj, int x) {
Stack_push(&obj->T1,x); //这里将栈 T1 作为入口栈
}
3.删除数据(先进先出)
将入口栈数据记录 >> 删除入口栈数据 >> 导入出口栈 >> 从出口栈导出数据
int myQueuePop(MyQueue* obj) {
if(Stack_Empty(&obj->T2)) //判断是否为空
{
int k = 0;
for(;!Stack_Empty(&obj->T1);)
{
k = Stack_Top(&obj->T1); //记录入口站数据
Stack_pop(&obj->T1); //删除入口栈数据
Stack_push(&obj->T2,k); //导入出口栈
}
}
int temp = 0;
temp = Stack_Top(&obj->T2);
Stack_pop(&obj->T2); //从出口栈导出数据
return temp; //题干要求返回导出的值
}
4.查找队列头部数据
这里的头部数据是正序的头数据,因此要先将入口栈中的逆序数据导入出口栈,
变成正序,再返回出口栈的栈顶数据 。
int myQueuePeek(MyQueue* obj) {
if(Stack_Empty(&obj->T2)) //判断出口栈中是否有数据
{
int k = 0;
for(;!Stack_Empty(&obj->T1);) //向出口栈导入数据
{
k = Stack_Top(&obj->T1);
Stack_pop(&obj->T1);
Stack_push(&obj->T2,k);
}
}
return Stack_Top(&obj->T2); //返回出口栈栈顶数据
}
5.判断队列是否为空 及 销毁队列
//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
//判断两个栈是否均为空
return Stack_Empty(&obj->T1)&&Stack_Empty(&obj->T2);
}
//销毁释放队列
void myQueueFree(MyQueue* obj) {
Stack_pop(&obj->T1);
Stack_pop(&obj->T2);
free(obj);
}
感谢大家的支持!!!
边栏推荐
- When jupyter notebook is encountered, erroe appears in the name and is not output after running, but an empty line of code is added downward, and [] is empty
- Tshydro tool
- Matlab在线性代数中的应用(四):相似矩阵及二次型
- Machine learning Seaborn visualization
- Oracle code use
- PHY drive commissioning --- mdio/mdc interface Clause 22 and 45 (I)
- [untitled]
- The problem of configuring opencv in qt5.13.2 is solved in detail
- Altimeter data knowledge point 2
- HDU1232 畅通工程(并查集)
猜你喜欢
iNFTnews | 喝茶送虚拟股票?浅析奈雪的茶“发币”
Clickhouse database installation deployment and remote IP access
【Node】nvm 版本管理工具
Don't confuse the use difference between series / and / *
网易To B,柔外刚中
arcgis_ spatialjoin
并发编程 — 如何中断/停止一个运行中的线程?
U-boot initialization and workflow analysis
Using GEE plug-in in QGIS
The problem of configuring opencv in qt5.13.2 is solved in detail
随机推荐
Unity UGUI不同的UI面板或者UI之间如何进行坐标匹配和变换
Ros2 - function package (VI)
MySQL setting trigger problem
第 2 章:小试牛刀,实现一个简单的Bean容器
Altimeter data knowledge point 2
Executealways of unity is replacing executeineditmode
Netease to B, soft outside, hard in
并查集理论讲解和代码实现
What is sodium hydroxide?
玩转gRPC—深入概念与原理
Mipi interface, DVP interface and CSI interface of camera
Graduation thesis project local deployment practice
ORACLE CREATE SEQUENCE,ALTER SEQUENCE,DROP SEQUENCE
Intelligent target detection 59 -- detailed explanation of pytoch focal loss and its implementation in yolov4
Microservice registry Nacos introduction
Word import literature -mendeley
selenium 元素定位
Ugnx12.0 initialization crash, initialization error (-15)
Don't confuse the use difference between series / and / *
Jenkins reported an error. Illegal character: '\ufeff'. Class, interface or enum are required