package stack;

import java.util.Deque;
import java.util.LinkedList;
/**
 * @author dx
 * @version 1.0
 * @date 2022年3月28日 10:47
 * @description: 仅使用两个栈实现先入先出队列,队列应当支持一般队列支持的所有操作(push、pop、peek、empty)
 *
 * 思路:队列是一种先进先出的数据结构,队列中的元素都从后端(real)入队(push),从前端(front)出队(pop)
 * 为了满足队列的FIFO的特性,需要用到两个栈,用其中一个来反转元素的入队顺序,用另一个来存储元素的最终顺序。
 * 每次入队 先把栈1(按队列存储的) 倒腾到 栈2(栈顶就是队列的最后一个元素) 然后把新元素放到栈2 重新再放到栈1中 新元素就放在了栈1的最后
 */
public class Stack_to_Queue {

 Deque<Integer> stack1 = null;
 Deque<Integer> stack2 = null;
 private int front;

 public Stack_to_Queue(){
 stack1 = new LinkedList<Integer>();
 stack2 = new LinkedList<Integer>();
 }

 public void push(int x){
 if(stack1.isEmpty())
 front = x;
 while(!stack1.isEmpty()){
 stack2.push(stack1.pop());
 }
 stack2.push(x);
 while (!stack2.isEmpty()){
 stack1.push(stack2.pop());
 }
 }
 public int pop(){
 return stack1.pop();
 }
 public int peek(){
 return stack1.peek();
 }
 public boolean empty(){
 return stack1.isEmpty();
 }
}