Let's first understand the characteristics of queue and stack structures

Queue queue ： fifo

The queue is only allowed to enter at the end of the queue
Head of the team to leave the team （or Delete ） operation

Schematic diagram of queue in and queue out operation

Stack Stack ： Last in, first out

Schematic diagram of stacking operation

Schematic diagram of stack out operation ：

Stack simulation queue

To simulate a queue with a stack , First of all, we should think about how to make the stack complete like a queue “ fifo ” Basic operation . The stack is characterized by last in, first out , So use the stack to simulate the queue , We need two stacks , They represent team entry and team exit operations respectively , Immediately enter the team stack in And out of the stack out.：

The stack simulates the queue entry operation ：

First step ： Before the element enters the team, you need to judge the team stack out Empty stack or not ？
The second step ： If you leave the stack out It's empty , Elements that need to be queued normally enter the queue stack in.
The third step ： If you leave the stack out Not empty , You need to get out of the stack first out All the elements of are put into the queue stack first in in , In the process of element queue operation .

The stack simulates the outgoing operation of the queue ：

One 、 It's the same as joining the team , Before leaving the team, you should first judge whether to join the team in Empty stack or not ？
Two 、 If you join the team in Empty stack , Then the normal out of line operation
3、 ... and 、 If you join the team in Not empty , You need to let the team stack first in All elements of enter the out of line stack out after , Out of line operation .

Stack simulation queue diagram

Code demonstration of stack simulation queue

public class Test01 {
    
	public static void main(String[] args) {
    
		MyQueue<String> queue1=new MyQueue<String>();
		// Store three elements respectively   Deposit in in Stack 
		queue1.offer("A");
		queue1.offer("B");
		queue1.offer("C");
		// What comes out of the stack is the first stored element 
		System.out.println(queue1.poll());
		System.out.println("----");
		queue1.offer("D");
		
		while(!queue1.isEmpty()) {
    
			System.out.println(queue1.poll());
		}
	}
	
	
}
class MyQueue<E>{
    
	
	Stack<E> in=new Stack<E>();// Join the team 
	Stack<E> out=new Stack<E>();// Out of the stack 
	// Judge whether the stack is empty 
	public boolean isEmpty() {
    
		return in.size()==0&&out.size()==0;// When both in and out of the queue stack are empty , To return to true
	}
	// Joining operation 
	public void offer(E e) {
     
		while(!out.isEmpty()) {
    // Determine whether the queue stack is not empty 
			in.push(out.pop());// If it is not empty, pop all the elements out of the queue stack into the queue stack in
		}
		in.push(e);// Element entry 
		
	}
	// Out of line operation 
	public  E poll() {
    
		while(!in.isEmpty()) {
    // Judge whether the queue stack is not empty 
			out.push(in.pop());// If it is not empty, all the elements in the queue stack will be ejected and stored out of the queue stack 
		}
		return out.pop();// Element queue 
	}
}