A simple 0 ms C++ solution


  • 2
    Y
    class Stack {
    public:
        // Push element x onto stack.
        void push(int x) {
            myStack.push(x);
        }
    
        // Removes the element on top of the stack.
        void pop() {
            int len = myStack.size();
            for(int i = 0; i < len - 1; i++) {
                myStack.push(myStack.front());
                myStack.pop();
            }
            myStack.pop();
        }
    
        // Get the top element.
        int top() {
            int len = myStack.size();
            if(len) {
                for(int i = 0; i < len - 1; i++) {
                    myStack.push(myStack.front());
                    myStack.pop();
                }
            }
            int ans = myStack.front();
            myStack.push(ans);
            myStack.pop();
            return ans;
        }
    
        // Return whether the stack is empty.
        bool empty() {
            return myStack.empty();
        }
    private:
        std::queue<int> myStack;
    };

  • 0
    R

    there is a empty() function we could use in queue.and the temp queue in pop function is needless. similar solution below

    class Stack {
    public:
        // Push element x onto stack.
        void push(int x) {
            int s = m_queue.size();
    		m_queue.push(x);
            for(int i=0; i<s; ++i) {
    			m_queue.push(m_queue.front());
                m_queue.pop();
            }
        }
    
        // Removes the element on top of the stack.
        void pop() {
    		m_queue.pop();
        }
    
        // Get the top element.
        int top() {
    		return m_queue.front();
        }
    
        // Return whether the stack is empty.
        bool empty() {
    		return m_queue.empty();
        }
    private:
        queue<int> m_queue;
    };

  • 0
    B

    Technically you are not supposed to use .back() on a queue.


  • 0
    B

    I like the simplicity of your implementation. I have an implementation that has uses 2 queues, and has an O(1) push, but an O(n) pop (which feels overkill now...).

    class stack {
    public:
        stack() {
            mReceiver = &mQueue1;
            mTransfer = &mQueue2;
        }
    
        // push element x onto stack.
        void push(int x) {
            if (!mReceiver->empty()) {
                int front = mReceiver->front();
                mReceiver->pop();
                mTransfer->push(front);
            }
            mReceiver->push(x);
        }
    
        // removes the element on top of the stack.
        void pop(void) {
            // 1. kill what's on the receiver
            mReceiver->pop();
    
            // early out case
            if (mTransfer->empty()) return;
    
            // 2. transfer
            while (mTransfer->size() != 1) {
                int front = mTransfer->front();
                mTransfer->pop();
                mReceiver->push(front);
            }
    
            // 3. swap receiver and transfer
            std::swap(mReceiver, mTransfer);
        }
    
        // Get the top element.
        int top(void) {
            return mReceiver->front(); 
        }
    
        // Return whether the stack is empty.
        bool empty(void) {
            return mQueue1.empty() && mQueue2.empty();
        }
    
    private:
        std::queue<int> mQueue1;
        std::queue<int> mQueue2;
        std::queue<int>* mReceiver;
        std::queue<int>* mTransfer;
    };

  • 0
    Y

    Yes, you are right, redace1985. Thank you for your suggestion! I have update my code


  • 0
    Y

    I don't think so. queue.back() is a avilable function that we can use and it can simplify our implementation. I think the goal here is to implement a structure that is easy and can function well.

    If using .back() is prohibited, I can use the updated code below:
    // Get the top element.
    int top() {
    int len = myStack.size();
    if(len) {
    for(int i = 0; i < len - 1; i++) {
    myStack.push(myStack.front());
    myStack.pop();
    }
    }
    int ans = myStack.front();
    myStack.push(ans);
    myStack.pop();
    return ans;
    }


  • 0
    Y

    Is it Ok to just use queue itself instead of pointer?


  • 0
    B

    Quoting the problem description; you'll notice that .back() is not mentioned.

    """
    You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
    """

    But given that the STL queue give one access to the back of a queue, I agree that it's interesting to see how the stack implementation can be simplified by using .back()


  • 0
    Y

    Yes, you are right. I have already updated the code. Thank you very much!


Log in to reply
 

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