C++, save only 1 stack, O(2N) for push and O(1) for others (with explanation)


  • 0

    I see on the discussion there are many ways to solve this problem. It is basically trade-off between time vs space and time complexity among different methods. My solution is to save only one stack in class and with the help from a temporary "reverse" stack to implement push so I can push the new incoming element to the bottom of the stack (i.e., the back of queue), which costs O(2N) time complexity. After pushing all time complexity into this single method, all other methods will be simply the wrapper for std::stack from STL. Unfortunately, we do not know how client's side will be using this new Queue, so we do not know which method will be called more often. I think my solution is efficient if peek() is used more often than push(int). Well, of course, one shouldn't call pop() more than push(int).

    class Queue {
    private:    
        stack<int> s;
    public:
        // Push element x to the back of queue.
        void push(int x) {
            stack<int> reverse;
            while (!s.empty()) {
                int y = s.top(); s.pop();
                reverse.push(y);
            }
            s.push(x);
            while (!reverse.empty()) {
                int y = reverse.top(); reverse.pop();
                s.push(y);
            }
            
        }
    
        // Removes the element from in front of queue.
        void pop(void) {
            s.pop();
        }
    
        // Get the front element.
        int peek(void) {
            return s.top();
        }
    
        // Return whether the queue is empty.
        bool empty(void) {
            return s.empty();
        }
    };
    

Log in to reply
 

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