两个栈实现队列和两个队列实现栈 Java-蒲公英云

两个栈实现队列和两个队列实现栈 Java

public class Test07 {
    /**
     * 用两个栈实现一个队列（先进后出）
     * 队列的声明如下：实现它的两个函数appendTail(队列尾部插入结点)和deleteHead(队列头部删除结点)
     */
    public static class MyQueue<T> {
        private Stack<T> stack1 = new Stack<>();
        private Stack<T> stack2 = new Stack<>();
        public MyQueue() {
            super();
        }
        /**
         * 队列尾部插入结点
         *
         * @param t
         */
        public void appendTail(T t) {
            stack1.push(t);
        }
        /**
         * 队列头部删除结点
         *
         * @return
         */
        public T deleteHead() {
            //先判断弹出栈是否为空，如果为空就将插入栈的所有数据弹出栈，
            //并且将弹出的数据压入弹出栈中
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            if (stack2.isEmpty()) {
                throw new RuntimeException("queue is empty.");
            }
            return stack2.pop();
        }
    }
    /**
     * 用两个队列实现一个栈（先进后出）
     * 栈的声明如下：实现它的两个函数appendTail(栈顶插入结点)和deleteHead(栈顶删除结点)
     */
    public static class MyStack<T> {
        private Queue<T> queue1 = new LinkedBlockingQueue<>();
        private Queue<T> queue2 = new LinkedBlockingQueue<>();
        public MyStack() {
            super();
        }
        /**
         * 栈顶插入结点
         *
         * @param t
         * @return
         */
        public boolean appendTail(T t) {
            return queue1.add(t);
        }
        /**
         * 栈顶删除结点
         *
         * @return
         */
        public T deleteHead() {
            if (queue1.isEmpty() && queue2.isEmpty()) {
                throw new RuntimeException("stack is empty.");
            }
            //queue2不为空，把queue2的数据放入queue1中，直到queue2只剩下一个元素，弹出
            if (queue1.isEmpty()) {
                while (queue2.size() > 1) {
                    queue1.add(queue2.poll());
                }
                return queue2.poll();
            }
            //queue1不为空，把queue1的数据放入queue2中，直到queue1只剩下一个元素，弹出
            if (queue2.isEmpty()) {
                while (queue1.size() > 1) {
                    queue2.add(queue1.poll());
                }
                return queue1.poll();
            }
            return null;
        }
    }
    public static void main(String[] args) throws InterruptedException {
        MyQueue<Integer> myQueue = new MyQueue<>();
        myQueue.appendTail(1);
        myQueue.appendTail(2);
        myQueue.appendTail(3);
        myQueue.appendTail(4);
        System.out.println(myQueue.deleteHead());
        System.out.println(myQueue.deleteHead());
        System.out.println(myQueue.deleteHead());
        System.out.println(myQueue.deleteHead());
        MyStack<Integer> myStack = new MyStack<>();
        myStack.appendTail(1);
        myStack.appendTail(2);
        myStack.appendTail(3);
        myStack.appendTail(4);
        System.out.println(myStack.deleteHead());
        System.out.println(myStack.deleteHead());
        System.out.println(myStack.deleteHead());
        System.out.println(myStack.deleteHead());
    }
}