C++, 0ms, optimized for continuous push or pop/peek operations


  • 0
    class Queue {
    private:
        stack<int> a,b;
    public:
    // Push element x to the back of queue.
    void push(int x) {
        if (b.empty()) a.push(x);
        else {
            while (!b.empty()){
                a.push(b.top());
                b.pop();
            }
            a.push(x);
        }
    }
    // Removes the element from in front of queue.
    void pop(void) {
        if (a.empty()) b.pop();
        else{
            while(!a.empty()){
                b.push(a.top());
                a.pop();
            }
            b.pop();
        }
    }
    // Get the front element.
    int peek(void) {
        if (a.empty()) return b.top();
        else {
            while(!a.empty()){
                b.push(a.top());
                a.pop();
            }
            return b.top();
        }
    }
    // Return whether the queue is empty.
    bool empty(void) {
        return a.empty()&&b.empty();
    }
    };

  • 0
    This post is deleted!

  • 1

    @haiwei624 You're wrong, this solution is correct. And it doesn't fail your example, so you never even tested that?


  • 0

    @StefanPochmann OMG....Sorry again. This code may be not perfect bot is obviously correct. Always only one of stack a or stack b contain elements. One for input, another one for output can always keep the correct order.

    Why I always misread the code?

    This is my code, a bit different from his method. This time I also think his code in my limited direction, it's obviously a bad habit.

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

  • 0

    @haiwei624 You code is better than my posted one, and I learned of it several months ago when I revisited this problem. If being asked in a interview, definitely should use your version.

    Just an extra improvement. In pop(), you can just do

    void pop(void) {
        peek();
        ost.pop();
    }
    

    to reuse the code.


Log in to reply
 

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