Question

Formatted question description: https://leetcode.ca/all/232.html

 232	Implement Queue using Stacks

 Implement the following operations of a queue using stacks.
     push(x) -- Push element x to the back of queue.
     pop() -- Removes the element from in front of queue.
     peek() -- Get the front element.
     empty() -- Return whether the queue is empty.

 Example:

 MyQueue queue = new MyQueue();

 queue.push(1);
 queue.push(2);
 queue.peek();  // returns 1
 queue.pop();   // returns 1
 queue.empty(); // returns false


 Notes:

 You must use only standard operations of a stack -- which means only operations are valid
    push to top,
    peek/pop from top,
    size, and
    is empty

 Depending on your language, stack may not be supported natively.
 You may simulate a stack by using a list or deque (double-ended queue),
 as long as you use only standard operations of a stack.

 You may assume that all operations are valid
 (for example, no pop or peek operations will be called on an empty queue).

 @tag-stack

Algorithm

As long as the element is inserted from the front every time, for example, if a queue is 1, 2, 3, 4, then we save it in the stack as 4, 3, 2, 1, and then return to the top element 1, also It is the first element of the queue.

The difficulty of this question is the push function. We need an auxiliary stack tmp, and store the elements of s into tmp in reverse order. At this time, add a new element x, and then store the elements in tmp back. This is the order we want , The other three operations also directly call stack operations.

To optimize above, because every time you push, you have to flip both stacks,

So, have stacks new and old, the new pushed elements are cached in _new first, and all elements in _new are moved to _old only when the operations are pop and peek, which improves efficiency.

Code

Java

public class Implement_Queue_using_Stacks {
    class MyQueue {
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;

        public MyQueue() {
            this.stack1 = new Stack<Integer>();
            this.stack2 = new Stack<Integer>();
        }
        // Push element x to the back of queue.
        public void push(int x) {
            stack1.push(x);
        }

        // Removes the element from in front of queue.
        public int pop() {
            if (!stack2.isEmpty()) {
                return stack2.pop(); // stack is queue-order, queue-head at this-stack-top
            } else {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        }

        // Get the front element.
        public int peek() {
            int ret = 0;
            if (!stack2.isEmpty()) {
                ret = stack2.peek();
            } else {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
                ret = stack2.peek();
            }

            return ret;
        }

        // Return whether the queue is empty.
        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }
}

// OJ: https://leetcode.com/problems/implement-queue-using-stacks
// Time: O(1) amortized.
// Space: O(1)
class MyQueue {
    stack<int> in, out;
public:
    MyQueue() {}
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        int val = peek();
        out.pop();
        return val;
    }
    
    int peek() {
        if (out.empty()) {
            while (in.size()) {
                out.push(in.top());
                in.pop();
            }
        }
        return out.top();
    }
    
    bool empty() {
        return in.empty() && out.empty();
    }
};

class MyQueue:
    def __init__(self):
        self.stk1 = []
        self.stk2 = []

    def push(self, x: int) -> None:
        self.stk1.append(x)

    def pop(self) -> int:
        self.move()
        return self.stk2.pop()

    def peek(self) -> int:
        self.move()
        return self.stk2[-1]

    def empty(self) -> bool:
        return not self.stk1 and not self.stk2

    def move(self):
        if not self.stk2:
            while self.stk1:
                self.stk2.append(self.stk1.pop())


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

############

class MyQueue:

    def __init__(self):
        self.sk = []
        self.rsk = []

    def push(self, x: int) -> None:
        self.sk.append(x);
        

    def pop(self) -> int:
        self.peek()
        return self.rsk.pop()

    def peek(self) -> int:
        if self.rsk:
            return self.rsk[-1]
        else:
            while self.sk:
                self.rsk.append(self.sk.pop())
            return self.rsk[-1]
        

    def empty(self) -> bool:
        
        return not (self.sk or self.rsk)
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

232 - Implement Queue using Stacks

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions