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

àì夳堔傛蜴生んèń 2021-11-16 06:08 357阅读 0赞

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