Shulou(Shulou.com)06/02 Report--

This article introduces how to use queue to implement stack in Python. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

Title:

Use queues to implement the following actions of the stack:

Push (x)-element x stacks

Pop ()-removes the top stack element

Top ()-gets the top element of the stack

Empty ()-returns whether the stack is empty

Implement the following operations of a stack using queues.

Push (x)-Push element x onto stack.

Pop ()-Removes the element on top of the stack.

Top ()-Get the top element.

Empty ()-Return whether the stack is empty.

Example:

MyStack stack = new MyStack (); stack.push (1); stack.push (2); stack.top (); / / return 2stack.pop (); / / return 2stack.empty (); / / return false

Note:

You can only use the basic operations of the queue-that is, push to back, peek/pop from front, size, and is empty-these operations are legal.

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

You can assume that all operations are valid (for example, pop or top operations are not called on an empty stack)

Notes:

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.

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

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

Ideas for solving the problem:

Method 1 (two queues):

The queue is first in and out, and the stack is in and out. Using the queue to implement the stack, you can use two queues to complete the problem solution: queue1 is used to store the node when entering the stack; the nodes in the queue1 are sequentially out of the queue and merged into the queue to the queue2 until the last element is left in the queue1, which is the top element of the stack and pops up; and a top pointer is used to point to the top element of the stack, and the top () method can directly return the top pointer when querying the top element of the stack.

Method 2 (a queue):

With only one queue, you only need to reverse the queue when you enter the stack:

Stack queue node 1: queue:1 reverse queue 0 times: queue:1 node 2 stack queue:1- > 2 reverse queue 1: queue:1- > 2-> queue:2- > 1 node 2 stack queue:2- > 1-> 3 reverse queue twice: queue:2- > 1-> 3-- > queue:1- > 3-> 2-> queue:3- > 2-> 1.

In this way, no matter when you go out of the team, the order is in the order of going out of the stack.

Java:

Method one

Class MyStack {Queue queue1; Queue queue2; private int top;// points to the top element public MyStack () {queue1 = new LinkedList (); queue2 = new LinkedList ();} public void push (int x) {queue1.offer (x); top = x queue1.offer (x) / the newly added element is the top element} public int pop () {while (queue1.size () > 1) {/ / if the number of elements in queue 1 is greater than one top = queue1.poll () / / use top to temporarily store the element. When the loop ends, top happens to be the top element of the stack queue2.add (top);} / / queue 1 exchanges Queue tmp = queue2; queue2 = queue1; queue1 = tmp; return queue2.poll () with queue 2; / / returns the queue header element of queue 2, which also has only one element} public int top () {return top;} public boolean empty () {return queue1.isEmpty () / / queue 1 determines whether the stack is empty}}

Method 2:

You can reverse the queue every time you join the queue. Only special operations are required to enter the stack. Destack, take the top element of the stack, and whether it is empty or not are all operated according to the normal exit of the queue, the header element of the queue, and whether it is empty or not. The following is the code when entering the stack:

Queue queue = new LinkedList (); public void push (int x) {queue.add (x); int sz = queue.size (); / / get the queue length while (sz > 1) {/ / the number of reversals is the queue length minus one queue.add (queue.remove ()); / / reverse sz--;}}

Python:

The Python language has no stack and queue data structure and can only be implemented with array List or double-ended queue deque.

Such programming languages do not need to use queues to implement stacks or queues at all, because stacks and queues themselves must be implemented with the help of List and deque.

So this problem is very simple in this language, which can be said to be cheating.

Class MyStack: def _ init__ (self): self.stack = [] def push (self, x: int)-> None: self.stack.append (x) def pop (self)-> int: return self.stack.pop (- 1) def top (self)-> int: return self.stack [- 1] def empty (self)-> bool: return not self.stack on how to use the queue stack in Python is shared here. I hope the above can be helpful to you. You can learn more. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.