My solution using two stacks

  • 0

    ) My solution has a higher time complexity compared to the elegent one from StefanPochmann ( Mine has O(N^2)complexity. I tried to optimize it a little bit by using two stacks to save half of the enties in each of them. So for each push, I only move half entries in the queue. sRead indicates the stack on which the next pop/peek ops should be executed while sWrite indicates the stack on which the next push op should be executed.

        class Queue {
            int sRead = 0, sWrite = 0;
            stack<int> inStack[2];
    // a helper function that moves len entries from src to dst
            void move(stack<int> &src, stack<int> &dst, int len)
                for(auto i=0; i<len;i++)
            // Push element x to the back of queue.
            void push(int x) {
                int topE, len = inStack[sWrite].size(), sHelper = 1-sWrite;
         // empty the sWrite stack       
                move(inStack[sWrite], inStack[sHelper], len);    
    // put the x at the bottom     
    // move back the poped entries to sWrite stack, sWrite is in order
                move(inStack[sHelper], inStack[sWrite], len);
    // update sWrite    
                sWrite = sHelper;
            // Removes the element from in front of queue.
            void pop(void) {
    // just pop from sRead and update sRead index
                sRead = 1-sRead;
            // Get the front element.
            int peek(void) {
                return inStack[sRead].top();
            // Return whether the queue is empty.
            bool empty(void) {
                return inStack[sRead].empty();

Log in to reply

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