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

How to use two stacks to achieve a queue and its Push and Pop operations, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, hope you can get something.

One of the questions brushed today is to use two stacks to represent a queue. We know that the main difference between stack and queue is: stack: last-in first-out queue: first-in, first-out.

Title

Use two stacks to implement a queue to complete the Push and Pop operations of the queue. The elements in the queue are of type int.

Analysis.

A first-in-first-out queue needs to be implemented through two LIFO stacks. As shown in the following figure: suppose you press the data 1, 2, 3, 4, 5, 6, 7 into the stack stack1. If you take it directly from the stack1, it is 7, 6, 5, 4, 3, 2, and 1. It doesn't match the first-in, first-out we want you to do. So we take the data of stack1 out of the stack and press it into the stack stack2, so the data that comes out of the stack from stack2 is 1, 2, 3, 4, 4, 5, 6, 7. However, the above only considers the back stack of the advanced stack. What if it is alternating between the stack and the stack? For example, initially, press 1, 2, and 3 into the stack1. Then, unstack the data from the stack1 into the stack2. So at this time, if you enter the stack in the stack1, how do you press it into the stack stack2? In fact, you should note that if there is data in the stack2, then the data should be the first to go out of the stack, so just go out of the stack directly, regardless of the data in stack1, because those are later data, it must be late out of the stack. When there is no data in the stack stack2, all the data in the stack1 is removed from the stack and pressed into the stack2. In this way, you can achieve the first-in-first-out of a queue.

Solution method

Just queue up and push the data directly into the stack stack1.

Public void push (int node) {

Stack1.push (node)

}

Out of the queue, first determine whether there is data in the stack2, if so, directly out of the stack from the stack2. If not, the data from the stack1 is pushed into the stack stack2. Then take the stack out of the stack2.

Public int pop () {

If (! stack2.isEmpty ()) {

Return stack2.pop ()

}

While (! stack1.isEmpty ()) {

Stack2.push (stack1.pop ())

}

Return stack2.pop ()

}

However, the above code can also be simplified, after all, two return stack2.pop (); are a little uncomfortable.

Public int pop () {

If (stack2.isEmpty ()) {

While (! stack1.isEmpty ()) {

Stack2.push (stack1.pop ())

}

}

Return stack2.pop ()

}

Source code: public class Solution {

Stack stack1=new Stack ()

Stack stack2=new Stack ()

Public static void main (String [] args) {

Solution solution= new Solution ()

Solution.push (0)

Solution.push (1)

Solution.push (2)

Solution.push (3)

Solution.push (4)

Solution.push (5)

System.out.print (solution.pop () + "\ t")

System.out.print (solution.pop () + "\ t")

System.out.print (solution.pop () + "\ t")

Solution.push (6)

Solution.push (7)

Solution.push (8)

System.out.print (solution.pop () + "\ t")

System.out.print (solution.pop () + "\ t")

System.out.print (solution.pop () + "\ t")

}

Public void push (int node) {

Stack1.push (node)

}

Public int pop () {

If (stack2.isEmpty ()) {

While (! stack1.isEmpty ()) {

Stack2.push (stack1.pop ())

}

}

Return stack2.pop ()

}

}

test

Is it helpful for you to read the above content? 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.