My solution using two stacks


  • 0
    D

    ) My solution has a higher time complexity compared to the elegent one from StefanPochmann (https://leetcode.com/discuss/44106/short-o-1-amortized). 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++)
                {
                    dst.push(src.top());
                    src.pop();
                }
            }
        public:
            // 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     
           inStack[sWrite].push(x);
    // 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
                inStack[sRead].pop();
                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.