算法练习：用堆栈实现队列

题目：用堆栈实现队列或用队列实现堆栈

我们首先要知道堆栈和队列各自的特点：

堆栈的特点：后入先出

队列的特点：先入先出

我们以stack实现队列为例，来做说明。

主要思路：使用两个stack，一个作为input，一个作为output，同时实现三个方法，进入队列push方法，出队列pop方法，查看队列第一个元素peek方法。入从input的stack入，出则从output的stack出。

例如：input现在存放有元素1–>2–>3，1在栈底，3在栈定，如下：

input stack 数据存储顺序

3

2

1

当使用peek查看栈顶元素时，因为我们是要将堆栈模拟成队列，队列获取和查看，都是获取第一个元素；此时就将input中的元素，依次取出放入output中，此时output中的数据如下：

output stack 数据存储顺序

1

2

3

此时操作output stack pop或peek，获取的栈顶元素，就实现了队列的效果。

代码如下：

package com.example.demo;

import java.util.Stack;

public class StackToQueue {

    private static Stack<String> input = new Stack<>();
    private static Stack<String> output = new Stack<>();

    public static void main(String[] args) {
        input.push("a");
        input.push("b");
        input.push("c");

        StackToQueue sq = new StackToQueue();
        System.out.println(sq.pop());
        //出栈以后,查看两个栈中的数据
        System.out.println("input size:"+input.size());
        System.out.println("output size:"+output.size());
        //输出结果： input size:0
        //          output size:2
        //output size:2 说明数据已经从input移动到了output
        String pop = output.pop();
        String pop2 = output.pop();
        System.out.println("output :"+pop);
        System.out.println("output :"+pop2);
        //出栈后的输出：
        //output :b
        //output :c

    }

    public void push(String s) {
        input.push(s);
    }

    public String pop() {
        if(!output.isEmpty()) {
            return output.pop();
        } else {
            changeDate();
            if(!output.isEmpty()) {
                return output.pop();
            }
        }
        return null;
    }

    public String peek() {
        //todo
        return "";
    }

    public synchronized void changeDate() {
        while(!input.isEmpty()) {
            String pop = input.pop();
            output.push(pop);
        }
    }
}

输出结果：

a
input size:0
output size:2
output :b
output :c