两个队列实现栈 || 两个栈实现队列

两个栈实现队列

我们知道队列是先入先出的，如果分别输入1，2，3。poll的时候应该得到1，2，3。而栈的特性呢是后入先出，怎么用两个栈实现一个队列呢？
我们准备两个栈inStack，outStack。插入都插入到inStack中；取的时候先判断out是否为空，如果为空，就把in中的数据存到out中，因为栈是后入先出的，所以到out中就会反序，就能正常顺序取出来了。
下图所示：

代码如下：

public class Stack2Queue {
    private Stack<Integer> in = new Stack<>(), out = new Stack<>();

    public void add(int tar) {
        in.add(tar);
    }

    private int pop() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.empty() ? 0 : out.pop();
    }
}

两个队列实现栈

上图所示，Queue1和Queue2两个队列实现一个栈的功能。
图1. 分别插入123后Queue1和Queue2的状态。
图2. 实现栈的功能就是要取出3，那先把12移到Queue2，就可以得到3了。
图3. 继续插入4，这个时候就要插入Queue2了。
图4. 取出4就继续把12移到另外一个Queue就可以取出4了。

public class Queue2Stack {
    private Queue<Integer> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
    private int current = 0;

    public void add(Integer i) {
        Queue<Integer> queue = current == 0 ? q1 : q2;
        queue.add(i);
    }

    private int poll() {
        Queue<Integer> src = current == 0 ? q1 : q2, target = current == 0 ? q2 : q1;
        if (src.isEmpty()) {
            return 0;
        }
        int index = 0, result = 0, size = src.size();
        while (src.peek() != null) {
            index++;
            result = src.poll();
            if (index < size) {
                target.add(result);
            }
        }
        current = current == 0 ? 1 : 0;
        return result;
    }
}

最小栈

实现一个栈，可以随时返回当前栈内的最小值。
思路：两个栈，一个data栈装数据，一个min栈装最小值，min是一个单调栈。

1. add(3) data:3|min:3
   2.add(4) 直接入data，比较min顶部的数字跟自己比较大小，add一个比较小的值：data：3，4|min：3，3
2. add(1) data:3,4,1|min:3,3,1
   代码如下：

public class MinStack {
    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> min = new ArrayList<Integer>();

    public void add(int num) {
        data.add(0, num);
        if (min.isEmpty()) {
            min.add(num);
        } else {
            min.add(0, (num > min.get(0) ? min.get(0) : num));
        }
    }

    private int pop() {
        if (data.isEmpty()) {
            return -1;
        }
        int i = data.get(0);
        data.remove(0);
        min.remove(0);
        return i;
    }

    private int min() {
        if (data.isEmpty()) {
            return -1;
        }
        return min.get(0);
    }
}