自学内容网 自学内容网

【算法专题--栈】用队列实现栈 -- 高频面试题(图文详解,小白一看就懂!!)

目录

一、前言

二、题目描述

三、解题方法

⭐两个队列实现栈

🥝解题思路

🍍案例图解

⭐用一个队列实现栈 

🍇解题思路

🍍案例图解

四、总结与提炼

五、共勉    


一、前言

        用队列实现栈 这道题,可以说是--栈专题--,最经典的一道题,也是在面试中频率最高的一道题目,通常在面试中,面试官可能会从多个方面考察这道题目,所以大家需要对这道题目非常熟悉哦!!
       本片博客就来详细的讲讲解一下 用队列实现栈 的实现方法,让我们的面试变的更加顺利!!!

二、题目描述

题目链接: 225. 用队列实现栈 - 力扣(LeetCode)

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppop 和 empty)。

 三、解题方法

首先,需要了解一下,栈 和 队列基本概念  

⭐两个队列实现栈

🥝解题思路

两个队列 que1 que2 实现 的功能que2 其实完全就是一个备份的作用,把 que1除最后一个元素外的其它元素全部备份到 que2 中,然后弹出最后面的元素,再把其他元素从que2 导回 que1。

干涩的语言可能让大家不太好理解,我们在来看一下 详细的图解

🍍案例图解

 模拟的队列执行语句如下:

queue.push(1);        
queue.push(2);        
queue.pop();   // 注意弹出的操作       
queue.push(3);        
queue.push(4);       
queue.pop();  // 注意弹出的操作    
queue.pop();    
queue.pop();    
queue.empty();    
  • 首先,向 que1 中  入队列元素 【1】【2】 ,模拟元素入栈

  • 将 que1 中除队尾元素外 的其它元素,转移到 que2,在移除 que1 中的元素【2】 

  •  移除 que1 中的元素【2】 ,将 que1 赋值给 que2 ,模拟 移除 栈顶元素

  •  继续 向 que1 中入队列元素 【3】【4】,模拟入栈

  • 模拟 栈 的 pop 删掉元素 【4】【3】【1】,和之前的步骤一样,将【4】之前的元素,转移到 que2 中

  •  删除元素【4】,再将 que2 赋值给 que1 ,清空 que2

  • 按照 同样的思路 删除 【3】【1】 

 代码:

class MyStack {
public:
    MyStack() 
    {
        // 程序自己创建构造函数进行初始化
    }
    
    void push(int x)  // 入队列 
    {
        que1.push(x);
    }
    
    int pop()  // 出队列 
    {
        int size = que1.size();
        size--;
        while(size--)   // 将 que1 导入 que2 ,但是要留下最后一个元素
        {
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front();  // 留下的最后一个元素就是要返回的元素
        que1.pop();
        que1 = que2;        // 在将 que2 赋值给 que1
        // 清空 que2
        while(!que2.empty())
        {
            que2.pop();
        }
        return result;
    }
    
    int top() // 取 队顶 
    {
        return que1.back();
    }
    
    bool empty() // 判断队列是否为空 
    {
        return que1.empty();
    }
private:
    queue<int> que1;
    queue<int> que2;
};

⭐用一个队列实现栈 

🍇解题思路

其实这道题目就是用一个队列就够了。 

一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时在去弹出元素就是栈的顺序了。 

🍍案例图解

queue.push(1);        
queue.push(2);        
queue.pop();   // 注意弹出的操作 
queue.pop();

 模拟的队列执行语句如上:

  •  向  队列 中插入 元素【1】【2】,模拟入栈

  • 删除元素【2】,将元素【1】出队列,然后再重新入队列 

  •  将元素【2】出队列即可 ,模拟栈 删除元素【2】

  • 删除 元素【1】同理 


代码: 

class MyStack {
public:
    MyStack() 
    {
        // 程序自己创建构造函数进行初始化
    }
    
    void push(int x)  // 入队列 
    {
        que.push(x);
    }
    
    int pop()  // 出队列 
    {
        int size = que.size();
        size--;                 // 保留最后一个元素
        while(size--)
        {
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() // 取 队顶 
    {
        return que.back();
    }
    
    bool empty() // 判断队列是否为空 
    {
        return que.empty();
    }
private:
    queue<int> que;
};


四、总结与提炼

        最后我们来总结一下本文所介绍的内容,本文讲解来一道力扣中有关 用队列实现栈 的题目,这道题目是校招笔试面试中有关栈章节非常高频的一道题目大家下去一定要自己再画画图,分析一下,把这段代码逻辑自己实现一遍,才能更好地掌握 !! 

五、共勉    

以下就是我对 用队列实现栈 的理解,如果有不懂和发现问题的小伙伴,请在评论区说出来哦,同时我还会继续更新对 栈专题 的理解,请持续关注我哦!!!  


原文地址:https://blog.csdn.net/weixin_45031801/article/details/140082491

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!