剑指offer 用两个队列实现一个栈

深藏阁楼爱情的钟 2021-11-04 12:42 377阅读 0赞

题目描述

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

<分析>：

  • 入栈：将元素进队列A
  • 出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素依次出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把队列B中的元素出队列以此放入队列A中。

C++实现代码如下：

  1. class A
  2. {
  3. public:
  4.     void push(int v);
  5.     int pop();
  6. private:
  7.     queue<int> q1;
  8.     queue<int> q2;
  9. }
  11. A::push(int v)
  12. {
  13.     q1.push(v);
  14. }
  16. int A::pop()
  17. {
  18.     int front;
  20.     while(q1.size() > 1)
  21.     {
  22.         front = q1.front();
  23.         q2.push(front);
  24.         q1.pop();
  25.     }
  27.     if(q1.size() == 1)
  28.     {
  29.         front = q1.front();
  30.         q1.pop();
  31.         return front;
  32.     }
  34.     while(q2.size() > 1)
  35.     {
  36.         front = q2.front();
  37.         q1.push(front);
  38.         q2.pop();
  39.     }
  41.     if(q2.size() == 1)
  42.     {
  43.         front = q2.front();
  44.         q2.pop();
  45.         return front;
  46.     }
  48.     return -1;
  49. }

发表评论

表情：
评论列表 （有 0 条评论，377人围观）

还没有评论，来说两句吧...

相关阅读