［LeetCode］Implement Stack using Queues-白红宇

［LeetCode］Implement Stack using Queues

阅读量：2236 次

发布时间：2019-05-09

本文共 1591 字，大约阅读时间需要 5 分钟。

解题思路：

1，跟Implement Queue using Stacks这道题类似；

2，用两个Queue，一个叫Queue1,一个叫Queue2。

3，对于top或者pop操作，把当前存数据的那个Q1前n-1个elem都转移到另外一个Q2，只剩下最后一个elem，也就是最新push进的。

4，对于push来说，如果Q1和Q2都为空，那么随便找一个添加elem。然后，必须保证Q1和Q2至少有一个为空

5，不能单纯的通过size=1来判断这个queue是不是要top的queue

6，通过 queueToPush() 和 emptyQueue() 这两个helper方法，找到数据搬迁是from哪里to哪里

//编译错误

Line 21: ‘class std::queue<int>’ has no member named ‘top’

Line 18: ‘from’ declared as reference but not initialized

引用类型定义时要赋值；

能不用指针就不用指针；

class Stack {public:    // Push element x onto stack.    void push(int x) {        queue
    
      & q = queueToPush();        q.push(x);    }    // Removes the element on top of the stack.    void pop() {        queue
     
       & from = queueToPush();        queue
      
        & to = emptyQueue();        transport(from, to);        from.pop();    }    // Get the top element.    int top() {        queue
       
         & from = queueToPush();        queue
        
          & to = emptyQueue();        transport(from, to);        int ret = from.front();        to.push(ret);        from.pop();        return ret;    }    // Return whether the stack is empty.    bool empty() {        return q1.empty() && q2.empty();    }    queue
         
          & queueToPush(){ return q1.empty() ? q2 : q1; } queue
          
           & emptyQueue(){ return q1.empty() ? q1 : q2; } void transport(queue
           
             &from, queue
            
              &to){ while (from.size() > 1){ int temp = from.front(); to.push(temp); from.pop(); } }private: queue
             
               q1; queue
              
                q2;};