数据结构算法题:栈与队列的使用(一)
目录
- 用队列实现栈
- 题目
- 解题思路
- 代码实现
- 创建栈的结构体
- 栈的初始化
- 入栈
- 出栈
- 获取栈顶数据
- 判断栈是否为空
- 销毁栈
用队列实现栈
题目
题目描述:
示例:
解题思路
题目要求使用两个队列实现栈的入栈、出栈、获取栈顶元素、检查栈是否为空栈的基本操作。
既然要用到队列,我们首先得有能够实现队列基本操作的代码,这里直接复制之前已经写好的队列代码。
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
int size;
}Queue;
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 newnode
if (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;
}
//取队尾数据
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;
}
现在有了队列的代码,继续分析如何通过队列实现栈的操作。
队列是先进先出,栈的话是先进后出。
他说要使用两个队列,我们就先创建两个队列:
这两个队列就是我们的栈,当我们入栈时,就是将数据放入队列内。
第一种情况:这里假设栈里面没有数据,我们放入哪个队列都可以。
第二种情况:这里假设栈里面有数据,我们就需要放入不为空的队列内。
如上面这种情况,我们就需要放入Q1内,这样当我们取栈顶数据时,才可以正确出栈。
综合一下就是入栈的数据放入不为空的队列内。
出栈的操作:假设我们入栈放入的是Q1
根据栈先进后出的特性,我们取栈顶取的是3,有什么方法可以取出来?
显然我们可以将Q1内的数据出队列存入到Q2,但是不是全部转移,在队列结构体里面我们定义了有效数据个数size,我们只要转移size-1个数据,剩下的就是栈顶的数据。
根据上面这个例子,我们转移2个数据,当转移完后,我们就剩下了3,而3刚好就是我们需要的数据,在出栈后我们释放栈顶及释放队列头节点空间即可。
入栈出栈了解完了,再了解一下取栈顶数据。
数据是放在队列里面的,队列是有头指针phead和尾指针ptail的,我们找到不为空的队列,直接返回队列的尾节点数据即可。
这里注意我们的队列无论在什么时候,两个队列是肯定有一个为空的。
在这些操作例,能改变队列是否为空的操作就只有入栈跟出栈,但是入栈时我们放的是不为空的队列,出栈我们在取出数据后会删除栈顶的数据,这样无论如何我们都会保持一个队列为空队列。
因为不能通过视频的方式讲解,会显得比较凌乱,可以在之上通过画图来帮助自己理解。
代码实现
这里队列的操作函数在上面已经提供了,这些代码在前面讲解队列时全部讲解过了,有不了解的可以去回顾一下哈。
创建栈的结构体
typedef struct {
Queue q1;//队列1
Queue q2;//队列2
} MyStack;
栈的初始化
栈是由两个队列实现的,那初始化就是初始化两个队列。
MyStack* myStackCreate() {
MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&ps->q1);
QueueInit(&ps->q2);
return ps;
}
入栈
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))//判断是否为空队列
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
出栈
int myStackPop(MyStack* obj) {
//定义两个变量分别指向空队列和不为空队列
Queue* empq=&obj->q1;
Queue* noneq=&obj->q2;
if(!QueueEmpty(&obj->q1))//这里判断Q1是否为空,不为空就要替换一下
{
empq=&obj->q2;
noneq=&obj->q1;
}
while(QueueSize(noneq)>1)//转移数据到空队列
{
int pop=QueueFront(noneq);
QueuePush(empq,pop);
QueuePop(noneq);
}
//出队列
int pop =QueueFront(noneq);
QueuePop(noneq);
return pop;
}
获取栈顶数据
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);//销毁队列1
QueueDestroy(&obj->q2);//销毁队列2
free(obj);
obj=NULL;
}
感谢观看,有错请在评论区指正,谢谢。
最后赏赐小编一个三连吧各位看官老爷们。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/349752.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!