Sharing my implementation using three queues.


  • 0
    C

    This solution is concrete.

    class Stack {
        queue<int> in;
        queue<int> out;
        queue<int> middle;
        
    public:
        // Push element x onto stack.
        void push(int x) {
            in.push(x);
        }
    
        // Removes the element on top of the stack.
        void pop(void) {
           moveIn2Out();
           out.pop();
        }
    
        // Get the top element.
        int top(void) {
            moveIn2Out();
            return out.front();
        }
    
        // Return whether the stack is empty.
        bool empty(void) {
            return (in.empty() && out.empty());
        }
        
        void moveIn2Out(){
            int flag = 0;
            while(in.size() > 0){
                if(flag == 0){
                    middle.push(in.front());
                    in.pop();
                    while(out.size() > 0){
                        middle.push(out.front());
                        out.pop();
                    }
                    flag = 1;
                }else{
                    out.push(in.front());
                    in.pop();
                    while(middle.size() > 0){
                        out.push(middle.front());
                        middle.pop();
                    }
                    flag = 0;
                }
            }
            
            while(middle.size() > 0){
                out.push(middle.front());
                middle.pop();
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.