1、如何用栈构造实现队列构造

首先，用一个栈必定是实现不了的。所以，思考两个栈来实现。一个是push栈、一个是pop栈。

放数据的时候往push栈放，当取数据的时候，将数据全副倒到pop栈，再从pop栈取数据。

留神：

（1）倒数据的时候要一次性倒完
（2）如果pop栈没有拿完，不能倒数据

具体代码：

package basic.stackqueue;import java.util.Stack;/** * 应用栈构造实现队列构造的性能  * * @author 周一 */public class TwoStacksImplementQueue {    /**     * 应用两个栈来实现队列构造     */    public static class TwoStackQueue<T> {        // 用于寄存增加数据的栈        public Stack<T> stackPush;        // 用于寄存获取数据的栈        public Stack<T> stackPop;        public TwoStackQueue() {            stackPush = new Stack<>();            stackPop = new Stack<>();        }        /**         * 倒数据         */        private void pushToPop() {            // pop为空才倒数据            if (stackPop.empty()) {                // push有数据可倒，并且一次性倒完                while (!stackPush.empty()) {                    stackPop.push(stackPush.pop());                }            }        }        /**         * 增加数据都往stackPush栈放         */        public void add(T data) {            stackPush.push(data);        }        public T poll() {            if (stackPush.empty() && stackPop.empty()) {                throw new RuntimeException("Queue is empty");            }            // 拿数据前先执行倒数据办法            pushToPop();            // 拿数据都从stackPop栈拿            return stackPop.pop();        }        public T peek() {            if (stackPush.empty() && stackPop.empty()) {                throw new RuntimeException("Queue is empty");            }            pushToPop();            return stackPop.peek();        }    }    public static void main(String[] args) {        TwoStackQueue<Integer> test = new TwoStackQueue<>();        test.add(1);        test.add(4);        test.add(3);        test.add(2);        System.out.println(test.peek());        System.out.println(test.poll());        System.out.println(test.peek());        System.out.println(test.poll());        System.out.println(test.peek());        System.out.println(test.poll());        System.out.println(test.peek());        System.out.println(test.poll());    }}

2、如何用队列构造实现栈构造

同理，想用一个队列来实现，是不行的。所以，思考两个队列来实现。

留神：

（1）加数据的时候，往以后存在数据的队列加；
（2）拿数据的时候，将所有数据移到空队列中，留下一个数返回即可。

具体代码：

package basic.stackqueue;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;/** * 应用队列构造实现栈构造 * * @author 周一 */public class TwoQueuesImplementStack {    /**     * 两个队列实现栈构造     */    public static class TwoQueueStack<T> {        public Queue<T> queue;        public Queue<T> help;        public TwoQueueStack() {            queue = new LinkedList<>();            help = new LinkedList<>();        }        public void push(T data) {            queue.offer(data);        }        public T poll() {            while (queue.size() > 1) {                // 将queue中数据倒入help中，留下一个                help.offer(queue.poll());            }            // 将queue中剩下的一个数据取出后返回            T res = queue.poll();            // 替换queue和help的援用            // 这样就不必判断以后哪个队列存在数据，每次都是从queue倒到help，取数据、替换援用，取后又是queue队列存放数据            // 下次拿就间接从queue中拿，大大减少代码复杂程度            Queue<T> tmp = queue;            queue = help;            help = tmp;            return res;        }        public T peek() {            while (queue.size() > 1) {                // 将queue中数据倒入help中，留下一个                help.offer(queue.poll());            }            // 将queue中剩下的一个数据取出后返回            T res = queue.poll();            // 因为是peek，所以将最初这一个数放到help队列中            help.offer(res);            // 替换queue和help的援用            Queue<T> tmp = queue;            queue = help;            help = tmp;            return res;        }        public boolean isEmpty() {            return queue.isEmpty();        }    }    public static void main(String[] args) {        System.out.println("test begin");        TwoQueueStack<Integer> myStack = new TwoQueueStack<>();        Stack<Integer> stack = new Stack<>();        int testTime = 100000;        int maxValue = 100000;        for (int i = 0; i < testTime; i++) {            if (myStack.isEmpty()) {                if (!stack.isEmpty()) {                    System.out.println("error");                }                int value = (int) ((maxValue + 1) * Math.random());                myStack.push(value);                stack.push(value);            } else {                if (Math.random() < 0.25) {                    int value = (int) ((maxValue + 1) * Math.random());                    myStack.push(value);                    stack.push(value);                } else if (Math.random() < 0.5) {                    if (!myStack.peek().equals(stack.peek())) {                        System.out.println("error");                    }                } else if (Math.random() < 0.75) {                    if (!myStack.poll().equals(stack.pop())) {                        System.out.println("error");                    }                } else {                    if (myStack.isEmpty() != stack.isEmpty()) {                        System.out.println("error");                    }                }            }        }        System.out.println("test end");    }}