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");
    }

}