Share my c++ solution with two queues


  • 0
    L
    My C++ Solution use two queues,the method of int getTop() is use to get the top element of stack,and the difference between pop() and top() is than pop() will eject the top element but top() not.
    Time consuming for pop() and top() is O(n),for push() and empty() is O(1).
    
    class Stack {
        private:
            queue<int> q1,q2;
        public:
            // Push element x onto stack.
            void push(int x) {
                q1.push(x);
            }
        
            int getTop()
            {
                int top;
                if(q1.empty()&&(!q2.empty()))
                {
                    int tmp;
                    while(!q2.empty())
                    {
                        tmp=q2.front();
                        q2.pop();
                        if(q2.empty())
                            top=tmp;
                        else
                            q1.push(tmp);
                    }
                }
                else
                {
                    int tmp;
                    while(!q1.empty())
                    {
                        tmp=q1.front();
                        q1.pop();
                        if(q1.empty())
                            top=tmp;
                        else
                            q2.push(tmp);
                    }
                }
                return top;
            }
            // Removes the element on top of the stack.
            void pop() {
                if(!(q1.empty()&&q2.empty()))
                {
                    int t=getTop();
                }
                return;
            }
        
            // Get the top element.
            int top() {
                int t;
                if(!(q1.empty()&&q2.empty()))
                {
                    t=getTop();
                }
                q1.push(t);
                return t;
            }
        
            // Return whether the stack is empty.
            bool empty() {
                return q1.empty()&&q2.empty();
            }
        };

Log in to reply
 

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