用两个栈实现队列，java代码实现

1 队列的功能介绍

队列的功能就是FIFO（先进先出）原则。不管是队列还是栈，他们的功能都是存储数据，底层实现可以数组也可以是链表，但是他们各自有他们的特点。既然队列也是存储数据的一种数据结构，那么他就有增删改查等功能。队列的添加元素是在队尾添加，删除元素是在队头删除。

下面介绍一下队列的增删改查操作：

push(int x)：在队列尾部添加一个元素
pop()：删除队列头部第一个元素
empty()：判断是否为空队列
peek()：获取队列头部元素

2 栈的功能介绍

栈也是一种存储数据的数据结构，和队列不同的是，这是一种FILO（先进后出）的数据结构，插入和删除都在栈顶完成。

下面介绍一下的栈的增删改查操作：

push(int x)：向栈中插入一个元素
pop()：删除栈顶元素
top()：获得栈顶元素，打印，不删除
empty()：判断是否为空

3 栈实现队列的原理介绍

3.1 方式1原理介绍

方式1将栈A作为最终的栈，即栈A中的元素排序和队列中的排序一致，此种方式在push元素入队列时，需要同时操作两个栈，比较消耗时间和空间，但是其他的操作（比如pop,top等）就不会消耗太多的时间和空间资源了。

假设需要向队列中插入4个元素，分别是1,2,3,4：

有两个栈，分别是栈A和栈B：

第一步：向队列中插入元素1，即：向栈A中插入元素1：

插入元素1

第二步：向队列中插入元素2，即：向将栈A中的元素1放到栈B中，然后将元素2插入栈A中，在将栈B中的元素1放到栈A中：

将栈A中的元素放到栈B中

向栈A中插入新元素

将栈B中的元素放回到栈A

如果在插入元素3也是如此，将栈A中的元素放到栈B中，将元素插入到栈A，在将栈B中的元素放回到栈A中即可。

3.2 方式1的`java`代码实现

import java.util.Stack;

/*
用两个栈实现队列的功能
 */
public class StackToQueue {
    public static void main(String[] args) {
        StackToQueue stackToQueue = new StackToQueue();
        stackToQueue.push1(12);
        stackToQueue.push1(13);
        stackToQueue.push1(14);
        stackToQueue.push1(15);
        stackToQueue.pop1();
        stackToQueue.push1(16);
        stackToQueue.size1();
    }

    Stack<Integer> stackA = new Stack<>();
    Stack<Integer> stackB = new Stack<>();
  
 	//add a element to queue
    public void push1(int x){
        if (stackA.empty()){
            stackA.push(x);
        }else{
            while (!stackA.empty())
                stackB.push(stackA.pop());
            stackA.push(x);
            while (!stackB.empty())
                stackA.push(stackB.pop());
        }
    }
    //remove the front element of the queue
    public int pop1(){
        if (!stackA.empty())
            return stackA.pop();
        return Integer.MIN_VALUE;
    }
	//print the front element of the queue, do not delete, just print
    public void peek1(){
        if (!stackA.empty())
            System.out.println(stackA.peek());
    }
	//print the size of the queue
    public void size1(){
        System.out.println(stackA.size());
    }
}

运行结果：

3.3 方式2原理介绍

下面介绍的方式1，是在push操作的时候，将其栈中顺序做了调整，也就是变成队列的顺序，但是如果面对那种需要频繁push操作的程序，那么方式1的设计显然有些不合理，那么可以使用方式2，push时，栈A和栈B不做顺序调整，到调用pop或者peek时在调整。

向队列中插入三个元素（1,2,3）

向队列中插入元素1

向队列中插入元素2

向队列中插入元素3

删除队列中一个元素（1）

向栈A中元素放到栈B中

删除栈B中元素，此时两个栈中元素顺序不做改动：

删除栈B中的栈顶元素

再向队列中插入一个新元素（4）

将栈B中的元素放回到栈A中

向栈A中插入新元素4

打印队列的第一个第一个元素，peek操作

向栈A中的元素放到栈B中

然后将栈B中的栈顶元素打印，就是队列的第一个元素了。

3.4 方式2的`java`代码实现

public class StackToQueue {
    public static void main(String[] args) {
        StackToQueue stackToQueue = new StackToQueue();
        stackToQueue.push2(12);
        stackToQueue.push2(13);
        stackToQueue.push2(14);
        stackToQueue.push2(15);
        stackToQueue.pop2();
        stackToQueue.push2(16);
        stackToQueue.peek2();
        stackToQueue.size2();
    }

    Stack<Integer> stackA = new Stack<>();
    Stack<Integer> stackB = new Stack<>();

    //push a data to the stack
    public void push2(int data) {
        if (stackA.empty() && !stackB.empty()) {
            while (!stackB.empty()) {
                stackA.push(stackB.pop());
            }
        }
        //A is not empty, so push the data to A
        stackA.push(data);
    }

    //get the size of the stack
    public void size2() {
        int length = 0;
        if (!stackA.empty())
            while (!stackA.empty()) {
                stackA.pop();
                length++;
            }
        else if (!stackB.empty())
            while (!stackB.empty()) {
                stackB.pop();
                length++;
            }
        System.out.println(length);
    }

    //remove the top element data
    public void pop2() {
        if (stackA.empty() && stackB.empty())//都为空时
            System.out.println("null");
        else if (!stackA.empty()){//执行pop之前的操作，都是push，此时栈B是空的
            while (!stackA.empty())
                stackB.push(stackA.pop());
            stackB.pop();
        }else if (stackA.empty() && !stackB.empty())//上一步执行的pop操作，栈A是空的，
            stackB.pop();
    }

    //print the top element data
    public void peek2() {
        if (stackA.empty() && stackB.empty())//都为空时
            System.out.println("null");
        else if (!stackA.empty()){//执行pop之前的操作，都是push，此时栈B是空的
            while (!stackA.empty())
                stackB.push(stackA.pop());
            System.out.println(stackB.peek());
        }else if (stackA.empty() && !stackB.empty())//上一步执行的pop操作，栈A是空的，
            System.out.println(stackB.peek());
    }
}