7. 用两个栈实现一个队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

解题思路

栈的特征是『先进后出』，队列的特征是『先进先出』，要用两个栈A和B实现队列，则可以使用两个栈的『先进后出』特性来实现队列
push时，将数据压入栈A；pop时，如果栈B没有数据，则将栈A数据全部压入栈B,在由栈B取出数据，进行返回，即可实现「先进先出」的队列

代码实现

java 代码

     /**
     * 简易队列
     */
    public class Queue {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();

        /**
         * 将数据放入队列
         *
         * @param node
         */
        public void push(int node) {
            stack1.push(node);
        }

        /**
         * 从队列中取出数据
         *
         * @return
         */
        public int pop() {
            //当栈2为空时，将栈1所有数据出栈，压入栈2
            //原则：当调用pop()方法且栈2数据为空的时候要一次性将栈1中的数据取出，并且在栈2数据不为空时，不能将栈1数据放入栈2,否则会出现后进先出的现象
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            if (stack2.isEmpty()) {
                throw new NoSuchElementException("current not find element");
            }
            return stack2.pop();
        }

        /**
         * 判断队列数据是否为空
         * @return
         */
        public boolean isEmpty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

    public static void main(String[] args){
        Queue queue = new Queue();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        System.out.println(queue.pop());
        queue.push(5);
        while (!queue.isEmpty()) {
            System.out.println(queue.pop());
        }
    }

输出结果：

Kotlin 代码

    /**
     * 简易队列
     */
    class Queue {
        private var stack1 = Stack<Int>()
        private var stack2 = Stack<Int>()

        /**
         * 将数据放入队列
         *
         * @param node
         */
        fun push(node: Int) {
            stack1.push(node)
        }

        /**
         * 从队列中取出数据
         *
         * @return
         */
        fun pop(): Int {
            //当栈2为空时，将栈1所有数据出栈，压入栈2
            //原则：当调用pop()方法且栈2数据为空的时候要一次性将栈1中的数据取出，并且在栈2数据不为空时，不能将栈1数据放入栈2,否则会出现后进先出的现象
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop())
                }
            }
            if (stack2.isEmpty()) {
                throw NoSuchElementException("current not find element")
            }
            return stack2.pop()
        }

        /**
         * 判断队列数据是否为空
         * @return
         */
        val isEmpty: Boolean
            get() = stack1.isEmpty() && stack2.isEmpty()
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val queue = Queue()
        queue.push(1)
        queue.push(2)
        queue.push(3)
        queue.push(4)
        println(queue.pop())
        queue.push(5)
        while (!queue.isEmpty) {
            println(queue.pop())
        }
    }

输出结果：

引用声明

该题目引用自
牛客网