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

This article introduces the relevant knowledge of "what are the methods of implementing the queue stack". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Let's review the features and common methods of stack (Stack) and queue (Queue).

Stack is a last-in, first-out (LIFO) data structure. Common methods are as follows:

Push (): stack method to add elements to the top of the stack

Pop (): unstack method that removes and returns elements from the top of the stack

Peek (): queries the elements at the top of the stack and does not remove them.

Queues are first-in, first-out (FIFO) data structures. Common methods are as follows:

Offer (): queue joining method, adding elements to the end of the queue

Poll (): dequeue method that removes and returns elements from the head of the line

Peek (): querying the line header element does not remove the element.

After knowing the basics, let's take a look at today's question.

The topic describes the following actions that use queues to implement the stack:

Push (x)-- element x stacks

Pop ()-removes the top element of the stack

Top ()-- get the top element of the stack

Empty ()-returns whether the stack is empty

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

LeetCode 225: https://leetcode-cn.com/problems/implement-stack-using-queues/

Topic analysis

The title of this question is easy to understand: we only need to convert the first-in, first-out queue to a LIFO "stack". We can achieve this function from many directions, such as using two queues to insert and swap, or a queue to insert and swap, or a dual-end queue to achieve this function, the specific implementation method and code are as follows.

Implementation method 1: two queues implementation stack

In the previous article in which we implemented a queue with two stacks, we mainly used the idea of "negative and negative". Then when we see this problem, the first thing we should think of is to use two queues to implement a stack. however, the idea of implementing a queue here is slightly different from that of implementing a queue with a stack, because queues are first-in, first-out, and we can understand it as a "positive number". Then we can not use the idea of "negative and positive". Here we use two queues to implement the stack. The main operation idea is to insert the elements into a temporary queue first, and then insert all the elements of another queue into the tail of the temporary queue, so as to achieve the LIFO function. The specific steps are as follows.

Step one

Add the first element to the temporary queue queue2:

Step two

Since there are no elements in the formal queue, there is no need to move the elements in the queue1 to the end of the temporary queue queue2, just swap the temporary queue with the formal queue:

Step three

Add a second element to the temporary queue queue2:

Step 4

Then move the elements in the queue1 to the end of the queue2, as follows:

Step 5

Then swap queue1 and queue2:

Step 6

Perform the dequeue operation:

Final effect

From the final effect diagram, we can see that the LIFO feature has been implemented through the two queues, that is, the conversion from queue to stack has been completed. The implementation code is as follows:

Import java.util.Queue; class MyStack {Queue queue1; Queue queue2; public MyStack () {queue1 = new LinkedBlockingQueue (); queue2 = new LinkedBlockingQueue ();} / * stack * / public void push (int x) {/ / 1. Queue 2 queue2.offer (x); / / 2. Move all elements of queue 1 to queue 2 while (! queue1.isEmpty ()) {queue2.offer (queue1.poll ());} / / 3. Queue 1 and queue 2 interchange Queue temp = queue1; queue1 = queue2; queue2 = temp;} / * * out of the stack and return this element * / public int pop () {return queue1.poll ();} / * query top stack element * / public int top () {return queue1.peek () } / * determine whether it is empty * / public boolean empty () {return queue1.isEmpty ();}}

We submit the above test code in LeetCode, and the execution result is as follows:

This method is so stable that it beats 100% of users.

Implementation method 2: a queue implementation stack

Can we use a queue to implement the stack? The answer is yes.

We only need to perform the following two steps to convert the queue to a stack. The specific steps are as follows:

List elements at the end of the line

All elements except the end of the line are removed and rewritten into the column.

After this operation, the last entered end of the line element becomes the head of the line element, and the last-in-first-out function is realized, as shown in the following figure.

Step one

Element 1 is listed:

Step two

Element 2 is listed:

Step three

All elements before the last element, that is, element 1, are delisted and re-listed:

Step 4

Perform the dequeue operation:

Final effect

The implementation code of the above idea is as follows:

Import java.util.Queue; class MyStack {Queue queue1; public MyStack () {queue1 = new LinkedBlockingQueue ();} / * stack * / public void push (int x) {/ / get the original queue length (number of times to be moved) int count = queue1.size (); / / put the element at the end of the queue (x) / / for (int I = 0; I < count; iTunes +) {System.out.println ("for"); queue1.offer (queue1.poll ()) will be rejoined except the last element. }} / * destack and return this element * / public int pop () {return queue1.poll ();} / * query top stack element * / public int top () {return queue1.peek () } / * determine whether it is empty * / public boolean empty () {return queue1.isEmpty ();}} We put the above code in LeetCode

We submit the above code in LeetCode, and the execution result is as follows:

This method is still stable and beats 100% of users, but it performs better in terms of memory.

Implementation method 3: double-ended queue implementation stack

If you find the above methods difficult, finally we have a simpler implementation. We can use the double-ended queue ArrayDeque in Java to insert elements into the head or tail of the queue, and also remove them, so that we can enter and exit from the end of the queue, thus realizing the function of the stack.

The structure of the double-ended queue is as follows:

Let's demonstrate the concrete steps of implementing a stack with a double-ended queue.

Step one

Element 1 to join the team:

Step two

Element 2 join the team (end of the line):

Step three

Then get out of the line at the end of the line:

Final effect

The implementation code of the above idea is as follows:

Import java.util.ArrayDeque; class MyStack {ArrayDeque deque; public MyStack () {deque = new ArrayDeque ();} / * * on the stack * / public void push (int x) {deque.offer (x);} / * off the stack and return this element * / public int pop () {return deque.pollLast () } / * query the top element of the stack * / public int top () {return empty ()?-1: deque.peekLast ();} / * determine whether it is empty * / public boolean empty () {return deque.isEmpty ();}}

We submit the above code in LeetCode, and the execution result is as follows:

This is the end of the content of "what are the ways to implement the stack of queues". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.