用队列实现栈和用栈实现队列

这篇具有很好参考价值的文章主要介绍了用队列实现栈和用栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前面我们实现了栈和队列,其实栈和队列之间是可以相互实现的

下面我们来看一下 用 队列实现栈用栈实现队列

用队列实现栈

使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ,否则返回 false

如图是2个队列和1个栈
用队列实现栈和用栈实现队列
此时我们已经向栈中插入了5个元素,因为用队列去模拟,所以元素存放在栈中

因为用2个队列实现栈,所以我们创建一个MyStack的结构体,里面的元素是2个队列

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

创建栈

因为函数会返回创建栈的地址,如果定义的这个栈为局部遍历,则出函数后这个值就会被销毁,所以我们需要将这个栈开辟到堆区

然后也调用队列中的初始化函数,队栈结构体中2个队列进行开辟和初始化

MyStack* myStackCreate() {
    MyStack* new = (MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

实现入栈

在非空的队列中插入元素,就相当于入栈了

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
         QueuePush(&obj->q2,x);
    }
}

实现出栈

假设我们现在要出栈,按照栈的特点,先出的应该是5,但是由于队列的特点,只能先进先出,所以我们可以把最后一个元素之前的所有元素都出队并放到为空的那个队列中,再将最后一个元素出队,就做到的出栈的操作
用队列实现栈和用栈实现队列

所以这里需要找到空的那个队列,将有元素的队列中前面元素都放到空队列中后,再将最后一个元素出队,这样还是一个空队列一个有元素队列
所以一直会有一个空队列和一个非空队列
用队列实现栈和用栈实现队列

根据这个思路我们实现一下代码

首先要判断出空队列和非空队列,如果直接使用if else语句就会是语句冗余

所以我们可以定义emptyQnonemptyQ指针表示空队列和非空队列,然后判断出q1和q2哪个才是空队列和非空队列,emptyQ指向空队列,nonemptyQ指向非空队列

	Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    }

然后将非空队列中最后一个元素前的所有元素放入空数组中

	while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }

最后返回原非空队列中唯一的那个值,然后将它出队列

完整代码:

int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    }

    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int front = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return front;
}

判空

当两个队列都为空,那么模拟的栈也为空

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

取栈顶元素

元素都存在非空队列中,先找到非空队列,然后调用队列的QueueBack取出队列中最后一个值

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

其实这里可以体现出在实现队列时,设计QueueBack函数的原因


释放

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

用栈实现队列

使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty)
实现 MyQueue类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

我们先将一些数据入到一个栈中
用队列实现栈和用栈实现队列
如果我们想实现出队,首先出队的数据应该是1,但是根据栈的特点,1是最后一个出

所以需要将栈中非栈底元素全都入栈到另一个栈中,根据栈的特点,这些元素到另一个栈中后,元素的顺序对于队列来说就是“正的了”

用队列实现栈和用栈实现队列
所以对于这个栈,它的出栈顺序和要模拟的队列出队顺序是一样的

如果想入栈,如果入到之前“顺序正常”的栈中,则会改变最后出队的顺序

所以从上面的分析可以看出,2个栈可以单独负责一项任务,一个栈负责入队,一个负责出队

在定义MyQueue时,直接定义一个叫PushStack和一个叫PopStack的栈

typedef struct {
    ST PushStack;
    ST PopStack;
} MyQueue;

用队列实现栈和用栈实现队列

只要是入队,就往PushStack中入

当出队时,如果PopStack为空,就需要把PushStack中的数据先出栈,在入栈到PopStack中,然后出PopStack的栈顶元素
用队列实现栈和用栈实现队列
如果PopStack不为空,出队其实就是直接从PopStack中出栈,出PopStack的栈顶元素

所以可以看出,最终都是出PopStack的栈顶元素,只是如果PopStack为空,就需要将元素放到PopStack中,在实现时判断PopStack是否为空

所以下面我们来实现一下:


创建队列

MyQueue* myQueueCreate() {
    MyQueue*new = (MyQueue*)malloc(sizeof(MyQueue));
    if(new ==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    STInit(&new->PushStack);
    STInit(&new->PopStack);

    return new;

}

入队

根据前面的分析,入队就是将元素入栈到PushStack

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

出队

如果PopStack为空,就需要把PushStack中的元素都放到PopStack

if(STEmpy(&obj->PopStack))
    {
        while(obj->PushStack.top>0)
        {
            STPush(&obj->PopStack,STTop(&obj->PushStack));
            STPop(&obj->PushStack);
        }
    }

如果PopStack为不为空,就直接出栈顶元素

 int top = STTop(&obj->PopStack);
    STPop(&obj->PopStack);
    return top;

完整代码:

int myQueuePop(MyQueue* obj) {
    if(STEmpy(&obj->PopStack))
    {
        while(obj->PushStack.top>0)
        {
            STPush(&obj->PopStack,STTop(&obj->PushStack));
            STPop(&obj->PushStack);
        }
    }

    int top = STTop(&obj->PopStack);
    STPop(&obj->PopStack);
    return top;
}

返回队列开头的元素

其实返回队列开头的元素的操作与上面出队列操作类似

PopStack为空时,就将PushStack中的元素出栈,再依次入栈到PopStack
PopStack不为空时,就直接返回栈顶元素

可以看出,这个操作与出队列的操作唯一有差距的一点就是,不用pop掉PopStack中的栈顶元素

int myQueuePeek(MyQueue* obj) {
    if(STEmpy(&obj->PopStack))
    {
        while(obj->PushStack.top>0)
        {
            STPush(&obj->PopStack,STTop(&obj->PushStack));
            STPop(&obj->PushStack);
        }
    }

    int top = STTop(&obj->PopStack);
   
    return top;
}  

判空

如果当PushStackPopStack都为空的话,模拟出的队列才为空

bool myQueueEmpty(MyQueue* obj) {
    return STEmpy(&obj->PushStack)&&STEmpy(&obj->PopStack);
}

释放

调用STDestroy函数,销毁模拟队列的2个栈,然后再free掉队列文章来源地址https://www.toymoban.com/news/detail-408869.html

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->PushStack);
    STDestroy(&obj->PopStack);
    free(obj);
    obj = NULL;
}

到了这里,关于用队列实现栈和用栈实现队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 关于用栈和队列分别解决走迷宫问题的方法讨论(参与者:陈卓,毛敏磊)

    对于生活中最常见的小游戏——走迷宫,相信大家都不陌生,人为走相信大家都会走,但能不能用代码实现,我们认为是可以的,以下是我们对如何走迷宫的一些看法和代码实现(cz负责队列解决,mml负责用栈解决) 先简单介绍一下 队列 :队列是一种操作受限的线性表,只

    2024年04月08日
    浏览(78)
  • 【用队列实现栈】【用栈实现队列】Leetcode 232 225

    ---------------🎈🎈题目链接 用队列实现栈🎈🎈------------------- ---------------🎈🎈题目链接 用栈实现队列🎈🎈-------------------

    2024年01月20日
    浏览(42)
  • 数据结构-用栈实现队列

    前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否

    2023年04月08日
    浏览(88)
  • 【数据结构】用栈实现队列

    前言:本节博客分享了用栈实现队列效果的思路以及代码,有需要借鉴即可。 LINK 如果要用栈实现队列,我们直到栈是先入后出的一个效果,所以我们可以用两个栈,这样逆转两次数不就是入栈之前数组的顺序嘛。下面是一些图辅助理解: 完。

    2024年03月10日
    浏览(55)
  • 【leetcode】232. 用栈实现队列

    1.使用两个栈结构构建队列 我们需要自定义栈及其相关操作 栈结构遵循后入先出的原则,队列结构遵循先入先出的原则 构建具有两个栈结构的队列,栈pushST用于数据的插入,栈popST用于数据的删除 为栈结构动态开辟空间并初始化栈结构 2.入队操作 模拟入队操作,即将所有元

    2024年02月12日
    浏览(42)
  • leetcode 232.用栈实现队列

    🌟 leetcode链接:用栈实现队列 1️⃣ 思路和图解: push: pop: peek: 和 pop 类似。 代码: ✨ 栈和队列相关接口代码(可复制): 【数据结构】栈和队列

    2024年02月13日
    浏览(37)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、

    2024年01月20日
    浏览(43)
  • 算法刷题Day 10 用栈实现队列+用队列实现栈

    之前做过,但现在还是卡壳了,想了有一会儿才想出来。 其实使用一个队列就可以实现栈

    2024年02月16日
    浏览(38)
  • 算法第10天|232.用栈实现队列225. 用队列实现栈

    力扣链接 题目描述: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作( push 、 pop 、 peek 、 empty ): 实现  MyQueue  类: void push(int x)  将元素 x 推到队列的末尾 int pop()  从队列的开头移除并返回元素 int peek()  返回队列开头的元素 boolean empty(

    2024年02月22日
    浏览(37)
  • 【数据结构与算法】7、队列(Queue)的实现【用栈实现队列】

    ☘️ 队列 (Queue)是一种特殊的 线性表 , 只能在头尾两端进行操作 🎁 队尾(rear):只能从 队尾添加 元素,一般叫做 enQueue , 入队 🎁 队头(front):只能从 队头移除 元素,一般叫做 deQueue , 出队 🎁 先进先出 的原则, F irst I n F irst O ut, FIFO ☘️ 队列内部的实现可

    2024年02月12日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包