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

Python in how to use the stack to achieve the queue, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Implementing queues with stacks

Title:

Use the stack to implement the following actions of the queue:

Push (x)-places an element at the end of the queue.

Pop ()-removes the element from the header of the queue.

Peek ()-returns the element at the head of the queue.

Empty ()-returns whether the queue is empty.

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 (); / / return 1queue.pop (); / / return 1queue.empty (); / / return 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.

Assume that all operations are valid (for example, an empty queue does not invoke pop or peek operations).

Notes:

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

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).

Ideas for solving the problem:

The queue is first in and out, and the stack is in and out. Using the stack to implement the queue, you can use two stacks to solve the problem. When entering the queue, the stack1 is used to store the nodes, and when leaving the queue, the nodes in the stack1 are sequentially out of the stack and pressed into the stack2.

For example, 1, 2, 3 elements are put into the stack stack1: [1, 2, 3] when leaving the queue, the order should be: 1-> 2-> 3, but the stack first-out order is: 3-> 2-> 1 is not consistent with the out-queue order with the help of the element order in another stack stack2stack1: [1, 2, 3]-- > stack2: [3, 2, 1] at this time the stack2 stack order: 1-> 2-> 3 coincides with the out-queue order.

[note]: when leaving the queue, there is no need to rush to push the nodes in the stack1 into the stack2. Because the queue to be implemented is first in and then out, all the nodes in the stack2 can be popped up and then the nodes in the stack1 can be sequentially pressed into the stack2, which can amortize the time complexity out of the stack to O (1).

Java:

Class MyQueue {private Stack stack1; private Stack stack2; public MyQueue () {stack1 = new Stack (); stack2 = new Stack ();} public void push (int x) {stack1.push (x);} public int pop () {if (stack2.isEmpty ()) {while (! stack1.isEmpty ()) {stack2.push (stack1.pop ());}} return stack2.pop () } public int peek () {/ / stack1 node pops up and presses stack2 if (stack2.isEmpty ()) {/ / condition: stack2 is empty, not stack1 is not empty, so amortize complexity O (1) while (! stack1.isEmpty ()) {stack2.push (stack1.pop ()); / / stack1 eject node and press stack2}} return stack2.peek ();} public boolean empty () {return stack1.isEmpty () & stack2.isEmpty ();}}

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 MyQueue: def _ init__ (self): self.queue = [] def push (self, x: int)-> None: self.queue.append (x) def pop (self)-> int: # Pop up the first element return self.queue.pop (0) def peek (self)-> int: # return the first element return self.queue [0] def empty (self)-> bool: does return not self.queue help you after reading the above? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.