乐趣区

关于程序员:算法题用两个栈实现队列

7

要求

工夫限度:1 秒 空间限度:32768K

题目形容

用两个栈来实现一个队列,实现队列的 Push 和 Pop 操作。队列中的元素为 int 类型

解题思路

利用栈能够颠倒一个序列的程序这个个性来思考

像这类题目只有模仿一下就能找到答案:先退出一些元素,而后思考如何弹出你想要的元素,这样就解决了弹出的问题;再思考增加的问题

这道题中,stack1 用于入队,stack2 用于出队,只是出队是要留神:要保障 stack2 不为空时才能够出队;如果它为空,就要先将 stack1 中所有元素弹出到 stack2 中,再从 stack2 中弹出一个元素;如果它不为空,间接从 stack2 中弹出一个元素即可

代码

class Solution
{
public:
  void push(int node)
  {stack1.push(node);
  }

  int pop()
  {if(stack2.empty())
    {while(!stack1.empty())
      {stack2.push(stack1.top());
         stack1.pop();}
    }
      
    if(stack2.empty())
    {
      cout << "队列为空" << endl;
      abort();}
    
    int res = stack2.top();
    stack2.pop();
    return res;
  }

private:
    stack<int> stack1;    // 入
    stack<int> stack2;    // 出
};

拓展

用两个队列来模仿栈,思考形式和这道题一样

两个队列的元素要不停的倒来倒去


小弟才浅,如果本篇文章有任何谬误和倡议,欢送大家留言

感激大家的点赞、珍藏

微信搜「三年游戏人」第一工夫浏览最新内容,获取一份收集多年的书籍包 以及 优质工作内推

退出移动版