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

This article mainly explains "how to use the Java stack to achieve the queue", the content of the article is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "how to use the Java stack to achieve the queue" bar!

Example:

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

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

Problem-solving ideas

After reading the question, the first step is to think clearly about the difference between the stack and the queue. As shown in the following figure, the basic implementation of the stack and queue can actually be regarded as a list:

1) if it is a stack, after [1,2,3] enters the stack, the pointer will point to 3, and when it goes out of the stack, it will pop the 3 in the list.

2) if it is a queue, [1, 2, 3] after joining the queue, the pointer will point to 1, and when you leave the queue, it will pop the 1 in the list.

In other words, if it is a stack, the list will be [3, 2, 1] from top to bottom, and if it is a queue, it will be [1, 2, 3]. Therefore, the question becomes: how to change a list that will become [3, 2, 1] after insertion into [1, 2, 3] after insertion.

It's hard to find an answer to this question all of a sudden, so let's step back and think about another question: if it's [1, 2, 3] now, how can we keep it [1, 2, 3, 4] if we want to insert 4 into this list? (as shown in the following figure)

To solve this problem, you need to insert 4 into the bottom of the list (rather than directly to the top). Under what circumstances can 4 be inserted into the bottom? Notice that the list is a stack, and only if the stack is empty can 4 be inserted at the bottom. Therefore, if we want to construct an empty stack, if we want to turn a non-empty stack into an empty stack, we must have pop elements, and these elements must be saved and cannot be discarded, so there must be a place, and there must be another data structure to store these pop elements.

Based on the above thinking process, we will naturally think of using an extra stack.

To store these elements from pop, as shown in the following figure. By pop the elements of the main stack stack2 one by one and push them into the secondary stack stack1, you can empty the main stack and make it an empty stack.

In this way, the main stack can put the new element 4 at the bottom. At the same time, because elements enter the auxiliary stack stack1, the order becomes reverse [3, 2, 1], so when these elements are pop out to the main stack stack2, they will be the same as the original order [1, 2, 3].

At this point, the logic of the whole algorithm is clear, let's go over it again. First of all, when the main stack stack2 has no elements, it can be put directly into the main stack stack2.

The second element 2 will come in next, so follow these steps:

When the new element 3 is about to be inserted, just continue with this operation:

As you can see, in this way, you can always keep the main stack storing elements in the order of the queue (see the first figure in this article). As for the pop and peek methods, all you have to do is judge and process the main stack stack2 directly.

Time complexity

According to the above solution, the time complexity of the basic operation of the queue is as follows:

Push operation: the whole process needs to move the element from the main stack stack2 to the auxiliary stack stack1 (the time complexity of this step is O (n)), then insert the new element (time complexity O (1)), and finally move back to the main stack stack2 (time complexity O (n)), so the time complexity is O (2n+1), which is equal to O (n).

Pop operation: because only the main stack stack2 needs to be judged, only O (1) is needed.

Peek operation: because only the main stack stack2 needs to be judged, only O (1) is needed.

Finally, Java implements class MyQueue {private LinkedList stack1 = new LinkedList (); / / the aux one private LinkedList stack2 = new LinkedList (); / / the true one / * Initialize your data structure here. * / public MyQueue () {} / * * Push element x to the back of queue. * / public void push (int x) {if (stack2.isEmpty ()) {stack2.push (x);} else {while (! stack2.isEmpty ()) {stack1.push (stack2.pop ());} stack2.push (x) While (! stack1.isEmpty ()) {stack2.push (stack1.pop ());} / * * Removes the element from in front of queue and returns that element. * / public int pop () {if (! stack2.isEmpty ()) {return stack2.pop ();} return-1;} / * Get the front element. * / public int peek () {if (! stack2.isEmpty ()) {return stack2.peek ();} return-1;} / * Returns whether the queue is empty. * / public boolean empty () {return stack2.isEmpty ();}} Thank you for reading. The above is the content of "how to use Java stack to implement queues". After the study of this article, I believe you have a deeper understanding of how to use Java stack to implement queues, and the specific usage needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.