天津网站建设找哪家,企业查询系统官网,网站开发交什么税,怎么制作灯笼目录
1.用队列实现栈oj题
对比
一、初始化
二、出栈
三、入栈
四、取队头元素#xff1a;
2.用栈实现队列
一、定义
二、入队列
三、出队列
四、队头
五、判空 前言#xff1a;如果想了解什么是栈和队列请参考上一篇文章进来一起把【数据结构】的【栈与队列】狠…目录
1.用队列实现栈oj题
对比
一、初始化
二、出栈
三、入栈
四、取队头元素
2.用栈实现队列
一、定义
二、入队列
三、出队列
四、队头
五、判空 前言如果想了解什么是栈和队列请参考上一篇文章进来一起把【数据结构】的【栈与队列】狠狠玩弄痛快到大汗淋漓-CSDN博客 本篇不进行详细讲解栈和队列的定义 1.用队列实现栈oj题
. - 力扣LeetCode
在这个题目中用两个队列实现栈以队列的方法和知识点实现栈
对比
我们先来一个函数对比一下
这是用普通方法来实现的栈的初始化
void STInit(ST* ps)
{assert(ps);ps-arr NULL;ps-capacity ps-top 0;
}这是用队列方法实现的初始化
MyStack* MyStackCreat()
{MyStack* plt (MyStack*)malloc(sizeof(MyStack));QueueInit(plt-q1);QueueInit(plt-q2);return plt;}
差异很明显队列实现的方式明显要复杂很多哈哈哈这就是oj题锻炼的是你的思维
写代码之前我们用图解先来解析
一、初始化 首先我们要知道的是我们用队列实现栈要定义和初始化的是什么用队列实现栈实则是用队列的属性实现栈的属性所以我们在这里要定义队列 但是为什么要定义两个队列 题目上说了要用两个队列实现 所以我们定义队列用结构体实现两个不同的队列。 代码
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
typedef struct
{QueueNode q1;QueueNode q2;}MyStack;
MyStack* MyStackCreat()
{MyStack* plt (MyStack*)malloc(sizeof(MyStack));QueueInit(plt-q1);QueueInit(plt-q2);return plt;} 二、出栈
1.我们先将所有需要的数据入队列这里要注意的是入队列的时候是队尾入队头出也就是FIFO先进先出 2.入完队列之后 我们开始模拟出栈思路栈的属性是先进后出队列的属性是先进先出那么问题就来了怎么用先进先出的两个数列实现先进后出。这个就是核心思路。
对于q1队列来说此时q2队列是空的
既然是栈的属性先进的后出所以就是q1的队尾先出所以要找到q1的队尾。 那么你会说这不简单嘛用指针不就完了
但是哈这里要强调用队列的属性来实现栈的属性使用的自然是队列的接口。而不是用库函数。
队列的基本操作有什么哪
入队列出队列队列判别空取队头取队尾队列有效个数销毁
所以第一个思路就来了。 将队尾前的元素直接移动到空队列q2这样就q1队列剩下的元素就是队尾元素。 之后如果再想出栈再将q2的队尾前的元素移动到空队列q1队尾元素出栈。
什么时候不能出栈了呢直到两个队列都为空的时候 这样我们就用两个队列实现了先进后出后进先出的栈的属性
void MystackPop(MyStack* pst)
{QueueNode* nonequ pst-q1;QueueNode* emtyqu pst-q2;if (!QueueEmpty(pst-q2)){emtyqu pst-q1;}else{emtyqu pst-q2;}while (QueueSize(nonequ) 1){int front QueueFront(nonequ);QueuePush(emtyqu, front);QueuePop(nonequ);}int pop QueueFront(nonequ);QueuePop(nonequ);return pop;
} 三、入栈
入栈操作相比于出栈先简单很多入队列和入栈的属性其实是相同的直接入就行了。所以体现在队列上就是先进的先入栈所以就是队头入栈。 void MyStackpush(MyStack* pst,int x)
{if (!QueueEmpty(pst-q1)){QueuePush(pst-q1, x);}else{QueuePush(pst-q2, x);}} 四、取队头元素
取队头元素听起来很复杂其实就是在栈里就是最后一个进入的在队列里就是队尾 直接返回队列的队尾元素即可
int MystackTop(MyStack* pst)
{if (!QueueEmpty(pst-q1)){return QueueBack(pst-q1);}else{return QueueBack(pst-q2);}
}
2.用栈实现队列
232. 用栈实现队列 - 力扣LeetCode 对于用栈实现队列其实扒开底层逻辑就好也不难理解要实现pushpoptopempty几种接口其实就是入栈出栈返回栈顶判断是否为空。至于怎么具体实现接下来就是详细解释
一、定义
这里要定义两个栈我们分别命名为pop和push队列
typedef struct
{ST pushST;ST popST;
}MyQU;MyQU* MyQueueCreat()
{MyQU* pst (MyQU*)malloc(sizeof(MyQU));STInit(pst-pushST);STInit(pst-popST);return pst;
}
二、入队列
两者逻辑差不多直接入队列即可 void MyqueuePush(MyQU* obj,int x)
{StackPush(obj-pushST, x);
} 三、出队列 其实出队列的逻辑跟出栈的逻辑是相反的跟上面的逻辑正好是倒过来的底层逻辑是怎么用两个先进后出的栈实现先进先出的队列但其实方法是大相径庭的。
判断pop是否为空为空的将push的数据全部出栈然后入栈给pop。不会空直接出栈相当于出队列
步骤一 过程二 过程三 int MyQueuePop(MyQU* obj)
{if (StackEmpty(obj-popST)){while (obj-pushST){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}int pop StackTop(obj-popST);StackPop(obj-popST);return pop;} 四、队头
队列中的队头限速是先进的那个元素在栈中是最后出栈的那个元素所以我们将栈的最后元素当作队头即可 五、判空 判断队列是空的时候相当于push和pop的栈都为空只有两个都为空的时候才是空。 要用到的队列和栈的接口源码
队列的接口源码
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
// ⼊队列队尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请新节点QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;//ptail newnodeif (pq-phead NULL){//队列为空pq-phead pq-ptail newnode;}else{//队列不为空pq-ptail-next newnode;pq-ptail pq-ptail-next;//newnode}pq-size;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}// 出队列队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点的情况避免ptail变成野指针if (pq-ptail pq-phead){free(pq-phead);pq-phead pq-ptail NULL;}else{//删除队头元素、QueueNode* next pq-phead-next;free(pq-phead);pq-phead next;}--pq-size;
}
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}//取队尾数据QU
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);/*int size 0;QueueNode* pcur pq-phead;while (pcur){size ;pcur pcur-next;}return size;*/return pq-size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
} 栈的接口
#define _CRT_SECURE_NO_WARNINGS 1
#includeStack.hvoid STInit(ST* ps)
{assert(ps);ps-arr NULL;ps-capacity ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);if (ps-arr)free(ps-arr);ps-arr NULL;ps-top ps-capacity 0;
}void StackPush(ST* ps, STDataType x)
{assert(ps);//1.判断空间是否足够if (ps-capacity ps-top){int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-arr, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);exit(1);}ps-arr tmp;ps-capacity newCapacity;}//空间足够ps-arr[ps-top] x;
}
bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps-top;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-arr[ps-top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
