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

This article will explain in detail how to convert stack and queue in Java. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

Stacks and queues are essentially the same, and can only be inserted and deleted at one end of the online table. As a result, stacks and queues can be converted to each other.

Using stack to realize queue-force buckle 232 questions

Topic requirements: only use two stacks to achieve first-in, first-out queue. Queues should support all operations supported by general queues

By using dual stacks to implement queues, we can make one stack store specific elements and the other stack as an auxiliary

As you can see in the above figure, when a new element enters the stack, make sure that the stack is empty. The elements that enter the stack are stored in the auxiliary stack in order, and after the new elements enter the stack, the elements in the auxiliary stack are put out to the stack in order. After doing this, the elements in the stack are stored in the same order as the queue.

Code implementation:

/ / dual stack simulation queue public class MyQueue {/ / stack private Stack S1 = new Stack (); / / auxiliary stack private Stack S2 = new Stack (); public MyQueue () {} / / push element x to the end of the queue public void push (int x) {if (s1.empty ()) {/ / stack is empty and directly put into x s1.push (x) } else {/ / is not empty at this time / / first eject all S1 elements into S2 while (! s1.empty ()) {s2.push (s1.pop ()); / / the value put in by S2 is the value popped up by S2 / / the following two sentences are the same as the previous sentence / / int val = s1.pop () / / s2.push (val);} / / put the new element directly into S1, and the new element is at the top of S1 s1.push (x); / / eject all values of S2 into S1 while (! s2.empty ()) {s1.push (s2.pop ()) again. } / / remove from the beginning of the queue and return the element public int pop () {return s1.pop ();} / / return the element public int peek () {return s1.peek ();} / / determine whether the queue is empty public boolean empty () {return s1.empty ();}}

Using queue to realize stack-force buckle 225 questions

Topic requirements: use only two queues to implement a last-in-first-out (LIFO) stack, and support all four operations of the ordinary stack

1. Dual queue implementation stack

Using dual queues to implement the stack, Q1 is the queue for storing elements, ensuring that Q2 will always be empty after adding elements (the new elements go directly into Q2) and ensure that the new elements are at the head of the line. In this way, after the new element joins the queue, the elements of another queue leave the queue and then join the queue, thus implementing a stack.

Code implementation:

Public class MyStack {/ / Q1 is the queue for storing elements private Queue Q1 = new LinkedList (); / / Q2 is the secondary queue / / after adding elements to ensure that Q2 is always empty private Queue Q2 = new LinkedList () Public MyStack () {} / / presses the element x into the top of the stack public void push (int x) {/ / the new queue element directly into Q2, becoming the Q2 team leader q2.offer (x); / / all the elements in Q1 are dequeued in turn into Q2 while (! q1.isEmpty ()) {q2.offer (q1.poll ()) } / / Q1 is empty, and Q2 is the queue for storing elements. After the swap reference points to / /, Q1 is still the queue for storing elements, and Q2 is empty Queue temp = Q1; Q1 = Q2; Q2 = temp;} / / remove and return the top element public int pop () {return q1.poll () } / / returns the top element public int top () {return q1.peek ();} / / to determine whether the stack is empty public boolean empty () {return q1.isEmpty ();}} 2. A queue implementation stack

First put the elements into the team, and then put the previous elements out of the team and then join the team! In other words, make sure the new element is at the head of the team.

Code implementation:

Public class MyStack {private Queue queue = new LinkedList (); public MyStack () {} public void push (int x) {/ / record the number of previous elements int size = queue.size (); / / add the new elements to the team queue.offer (x); / / put the previous elements out of the team and then join the team, and the new elements are at the head of the team for (int I = 0; I < size) Queue.offer (queue.poll ());}} public int pop () {return queue.poll ();} public int top () {return queue.peek ();} public boolean empty () {return queue.isEmpty ();}}

The practical purpose of these examples is to be more familiar with mastering and understanding stacks and queues, which are not recommended in practical applications.

This is the end of this article on "how to convert stack and queue in Java". 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, please 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.