How to implement queues with Stack in leetcode

This article is about how leetcode implements queues with stacks. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

I. the content of the topic

Please use only two stacks to implement the first-in, first-out queue. The queue should support all the operations supported by the general queue (push, pop, peek, empty):

Implement the MyQueue class:

Void push (int x) pushes element x to the end of the queue

Int pop () removes from the beginning of the queue and returns the element

Int peek () returns the element at the beginning of the queue

Boolean empty () returns true if the queue is empty; otherwise, returns false

Description:

You can only use standard stack operations-that is, only push to top, peek/pop from top, size, and is empty operations are legal.

The language you are using may not support stacks. You can use list or deque (double-ended queue) to simulate a stack, as long as it is a standard stack operation.

Advanced:

Can you achieve a queue with a time complexity of O (1) for each operation? In other words, the total time complexity of performing n operations is O (n), even though one of them may take a long time.

Example:

Enter:

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], []]

Output:

[null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue ()

MyQueue.push (1); / / queue is: [1]

MyQueue.push (2); / / queue is: [1,2] (leftmost is front of the queue)

MyQueue.peek (); / / return 1

MyQueue.pop (); / / return 1, queue is [2]

MyQueue.empty (); / / return false

Tip:

1 int: "Removes the element from in front of queue and returns that element." If len (self.sb) = 0: while len (self.sa)! = 0: self.sb.append (self.sa.pop ()) return self.sb.pop () def peek (self)-> int: "Get the front element." If len (self.sb) = 0: while len (self.sa)! = 0: self.sb.append (self.sa.pop ()) return self.sb [- 1] def empty (self)-> bool: "Returns whether the queue is empty." Return len (self.sa) = = 0 and len (self.sb) = "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 () if _ _ name__ ='_ _ main__': myQueue = MyQueue () myQueue.push (1) myQueue.push (2) ans1 = myQueue.peek () Ans2 = myQueue.pop () ans3 = myQueue.empty () print (ans1 Ans2, ans3) Thank you for reading! This is the end of the article on "how to implement queue with leetcode stack". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it out for more people to see!