0


《数据结构初阶》用队列实现栈&&用栈实现队列的细致解析

纵有千古、横有八方

一、⏱️本章重点

  1. 用两个队列实现栈
  2. 用两个栈实现队列
  3. 解题思路总结

二、⏱️队列实现栈

我们有两个队列:

入栈数据1、 2、 3

可以将数据入队列至队列一或者队列二。

如何出栈?

但出栈要先出1,怎么办?

第一步

将队列一出队n-1个至队列二。

** 第二步**:

pop队列一的最后一个元素。

** 接下来怎么入栈呢?**

将元素入队至不为空的队列。

怎么判断栈空?

队列一和队列二都为空的情况下,栈就是空的。

如何取栈顶元素?

取不为空的队列尾部元素。

总的来说就是,入栈时就将数据插入不为空的队列,出栈就将不为空的队列的前n-1个数据导入至另一个队列,然后pop最后一个元素。

代码实现:

首先我们要构造一个栈。

这个栈要包含两个队列

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;

在此之前我们要准备好队列的一般接口:

我这里的队列是用单链表来构建的,具体接口实现可以看我之前的文章。

typedef int QTypeData;
typedef struct QueueNode
{
    struct QueueNode* next;
    QTypeData val;
}QN;

void QueueInit(Queue* pq)//初始化队列
size_t QueueSize(Queue* pq)//求队列元素个数
int QueueBack(Queue* pq)//取队列尾部数据
void QueuePush(Queue* pq, QTypeData x)//将x入队
void QueuePop(Queue* pq)//出队
void QueueDestroy(Queue* pq)//结束队列

我们要用队列实现栈的接口:

💯第一个接口:创建并初始化栈

接口一:MyStack* myStackCreate()

这样做行吗?

MyStack* myStackCreate()
{

    MyStack ms;
    QueueInit(&ms.q1);
    QueueInit(&ms.q2);
    return ms;
}

很显然,返回局部变量的地址是不明智的,因为在函数返回时,ms开辟的空间会重新交给操作系统,再次访问就是非法操作。

因此我们需要将ms开辟在堆区。

参考代码:

💯第二个接口:入栈

接口二:void myStackPush(MyStack* obj, int x)

入栈简单:只要将数据插入到不为空的队列即可。

入栈之前我们需要判断队列满吗?

不需要,因为我的队列是用单链表实现的,可以无限链接下去。

如果两个队列都为空,该插入到哪个队列呢?

我们可以这样做,如果队列1为空,就插入到队列2,如果不为空,就插入到队列1.

参考代码:

💯第三个接口:出栈

接口三:int myStackPop(MyStack* obj) //出栈

再次回顾一下我们是如何出栈的。

首先我们有两个队列

初始状态它们都是空的

队列一:空

队列二:空

入栈1、2、3、4

执行后

队列一:空

队列二:1、2、3、4

出队列只能先出1,如何出4呢?

把1、2、3先出给队列一

执行后

队列一:1、2、3

队列二:4

然后将4用变量记录并出队,最后返回记录4的变量。

执行后

队列一:1、2、3

队列二:空。

出队三板斧

第一步:即将不为空的队列的前n-1个元素入至为空的队列。

第二步:将剩下的1个元素用变量记录,然后将最后一个元素出队。

第三步:返回用变量记录的元素。

需要注意的是:如果栈为空,那么就返回false。

参考代码:

💯第四个接口:取栈顶元素

接口四:int myStackTop(MyStack* obj) //取栈顶元素

取栈顶元素之前我们需要保证栈不为空

如果栈为空,返回false。

取栈顶元素,即取不为空的队列的队尾元素。

参考代码:

💯第五个接口:判断栈是否为空

接口五:bool myStackEmpty(MyStack* obj) //判断栈是否为空

如果两个队列都是空的那么该栈就是空的。

这里多提一下,栈的元素个数怎么求?

栈的元素个数就是那个不为空队列的元素个数。

参考代码:

💯第六个接口:销毁栈

接口六:void myStackFree(MyStack* obj) //结束栈

参考代码:

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

最后需要注意的是:调用栈为空的接口时,要先声明!!

三、⏱️栈实现队列

第一次入队

将数据1出队操作

将栈1的数据全导入栈2

然后栈2进行出栈操作

再次入队5、6、7

直接将5、6、7入栈至栈1

实际我们的对头和队尾是这样的

** 总的来说:**

用两个栈实现一个队列,就得把一个栈专门入队,另一个栈用作出队。这里实现的时候我们用栈1做入队栈,栈2做出队栈。

也就是说,只要将数据入队,直接放入栈1.

出队就直接出栈2的数据,如果栈2为空,这将栈1的数据全部导入栈2.

队列的结构体

typedef struct 
{
    ST st1;
    ST st2;
} MyQueue;

我们需要准备的栈

typedef int STDataType;
typedef struct Stack
{
    STDataType* data;
    int top;
    int capacity;
}ST;

这里我用的是动态数组实现的栈

需要提前准备栈的接口:

void STInit(ST* p)
void STDestroy(ST* p)
void STPush(ST* p,STDataType x)
void STPop(ST* p)
bool STEmpty(ST* p)
int STSize(ST* p)
STDataType STRear(ST* p)

💯第一个接口:创建并初始化队列

MyQueue* myQueueCreate() 

同样的,需要把队列开辟在堆区,同时对栈1和栈2进行初始化。

参考代码:

MyQueue* myQueueCreate() 
{
    MyQueue* mq=(MyQueue*)malloc(sizeof(MyQueue));
    assert(mq);
    STInit(&mq->st1);
    STInit(&mq->st2);
    return mq;
}

💯第二个接口:入队

void myQueuePush(MyQueue* obj, int x) 

我们把栈1做入队栈,栈2做出队栈。

也就是说,只要将数据入队,直接放入栈1.

出队就直接出栈2的数据,如果栈2为空,这将栈1的数据全部导入栈2.

参考代码:

void myQueuePush(MyQueue* obj, int x) 
{
    STPush(&obj->st1,x);
}

💯第三个接口:出队

int myQueuePop(MyQueue* obj) 

先要判断队列是否为空,如果队列为空则返回false。

其次如果栈2为空,就将栈1的数据全导入栈2.

参考代码:

int myQueuePop(MyQueue* obj) 
{
    if(myQueueEmpty(obj))
    {
        return false;
    }
    if(STEmpty(&obj->st2))
    {
        int n=STSize(&obj->st1);
        while(n--)
        {
            STPush(&obj->st2,STRear(&obj->st1));
            STPop(&obj->st1);
        }
    }
    int ret=STRear(&obj->st2);
    STPop(&obj->st2);
    return ret;
}

💯第四个接口:取队头元素

int myQueuePeek(MyQueue* obj)

取队头元素之前,要判断队列是否为空,如果为空,则返回false

队头元素即栈2的尾部元素。

但如果栈2为空呢?

那队列的队头元素就是栈1的头部元素。

参考代码:

int myQueuePeek(MyQueue* obj) 
{
    if(myQueueEmpty(obj))
    {
        return false;
    }
    if(STEmpty(&obj->st2))
    {
        return STFront(&obj->st1);
    }
    return STRear(&obj->st2);
}

💯第五个接口:判断队列是否为空

bool myQueueEmpty(MyQueue* obj)

队列为空,需要栈1和栈2都为空。

参考代码:

bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(&obj->st1) && STEmpty(&obj->st2);
}

💯第六个接口:销毁队列

void myQueueFree(MyQueue* obj) 

参考代码:

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->st1);
    STDestroy(&obj->st2);
    free(obj);
}

注意:当使用判断队列是否为空的接口时,注意是否在之前声明过了。

四、⏱️解题思路总结

1.用队列实现栈:

我们需要用两个队列实现栈

栈类是于尾插尾删

队列是尾插头删

第一次入栈:两个队列都为空,随便插入一个队列都可

第一次出栈:出栈要出的是尾部数据,队列只能出头部数据,这是队列不能直接实现的。

那么需要将不为空的队列前n-1个数据导入至为空的队列,再将最后一个元素pop掉。

队列一:1、2、3、4

队列二:空

那么导入后

队列一:4

队列二:1、2、3

最后pop最后一个元素

队列一:空

队列二:1、2、3、4

再次尾插:尾插至不为空的队列即可。

2.用栈实现队列

我们有两个栈要求实现队列的一般接口

栈一:空

栈二:空

第一次入队:入栈至栈一或者栈二都可,这里选择栈一。

假设入队1、2、3、4

栈一:1、2、3、4

栈二:空

出队:要先出1

将栈一全部导入栈二

栈一:空

栈二:4、3、2、1

之后入队就插入至栈一

出队就pop栈二。

标签: 数据结构 c语言

本文转载自: https://blog.csdn.net/m0_62171658/article/details/123805478
版权归原作者 李逢溪 所有, 如有侵权,请联系我们删除。

“《数据结构初阶》用队列实现栈&&用栈实现队列的细致解析”的评论:

还没有评论