C语言数据结构之栈与队列怎么相互实现
本篇内容介绍了“C语言数据结构之栈与队列怎么相互实现”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
一、用对列实现栈
题干要求：
细节分析：队列是先进先出； 要实现的栈是先进后出。
解题思路：假设：先用一个队列储存数据 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);
}“C语言数据结构之栈与队列怎么相互实现”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注蜗牛博客网站，小编将为大家输出更多高质量的实用文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
评论