Implement Queue using Stacks


  • 0
    2

    Why my code can not pass?

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

  • 0
    W

    I think your peek() method is incorrect, assume the situation that s2 is empty, while s1 have elements. At this situation, you need to pop elements from s1 first. The following is my implements:

    // Get the front element.
    public int peek() {
        if (!s2.isEmpty()) {
            return s2.peek();
        } else {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            return s2.peek();
        }
    }

  • 0
    2
    This post is deleted!

  • 0
    2

    @WuQiFu
    you are right. Not only the peek(),but also the pop(), I need to consider weather s2 is empty or not. Here is my new code, but I still can not pass. I don't know why.

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

  • 0
    W

    You should insert only when s2 is empty. The following is my passed codes, FYI:

    class MyQueue {
        // 思路: 两个栈模拟队列
        private Stack<Integer> s1 = new Stack<>(); // 用于push
        private Stack<Integer> s2 = new Stack<>(); // 用于pop
    
        // Push element x to the back of queue.
        public void push(int x) {
            s1.push(x);
        }
    
        // Removes the element from in front of queue.
        public void pop() {
            if (!s2.isEmpty()) {
                s2.pop();
            } else {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
                s2.pop();
            }
        }
    
        // Get the front element.
        public int peek() {
            if (!s2.isEmpty()) {
                return s2.peek();
            } else {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
                return s2.peek();
            }
        }
    
        // Return whether the queue is empty.
        public boolean empty() {
            return s1.isEmpty() && s2.isEmpty();
        }
    }

  • 0
    F

    @284169645
    Your push should be modified
    void push(int x) {
    while(!s2.empty())
    {
    s1.push(s2.top());
    s2.pop();
    }
    s1.push(x);
    while(!s1.empty())
    {
    s2.push(s1.top());
    s1.pop();
    }


  • 0
    2

    @fzhml I forgot the pop() after s2.push(s1.pop());
    After I add the pop() after s2.push(s1.pop()), it is accepted.
    Thank you for your help!


Log in to reply
 

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