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

输出结果:

1
2
3
4
5

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

输出结果:

1
2
3
4
5

引用声明

该题目引用自
牛客网