A little trick, which can make top() O(1)


  • 0
    E
    class Stack {
    public:
    	Stack() : flag(0), top_val(0) {}
        // Push element x onto stack.
        void push(int x) {
            que[flag].push(x);
    		top_val = x;
        }
    
        // Removes the element on top of the stack.
        void pop() {
            int n = que[flag].size();
    		int tmp = 0;
    		for(int i=0; i<n-1; ++i)
    		{
    			tmp = que[flag].front();
    			que[flag].pop();
    			que[1-flag].push(tmp);
    		}
    		que[flag].pop();
    		top_val = tmp;
    		flag = 1 - flag;
        }
    
        // Get the top element.
        int top() {
            return top_val;
        }
    
        // Return whether the stack is empty.
        bool empty() {
            return que[flag].empty();
        }
    private:
    	int flag;
    	int top_val;
    	queue<int> que[2];
    };

Log in to reply
 

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