一、题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

二、解题思路

Notzuonotdied的实现思路

因为队列是“先见先出”，而栈是“先进后出”，所以我们采用了两个栈，实现了“先进先出”的队列。

采用两个栈，一个栈为反向栈（作为中转，调换栈顶栈尾），一个栈为正向栈（即pop操作就是出队）。如果不懂也没事，请继续看下去，O(∩_∩)O～

正向栈作为队列头，反向栈作为队列的尾。

入队的时候，都是将数据压栈到反向栈中。

出队的时候，首先判断正向栈中是否有数据。如果正向栈中存在数据，就弹出正向栈的数据；如果正向栈为空，就将反向栈中的数据依次弹出，压栈到正向栈中。

存放演示

初始化一个实现好的队列，此时正向栈和反向栈均为空。
将数据[1,2,3]存放队列中；
首先，存放到反向栈中->[栈尾1,2,3栈顶]；
- 注意，这个时候如果pop出来，数据的顺序是反的->[3,2,1]，所以才要采用两个栈。
之后，因为正向栈是空的，所以，需要将反向栈的数据弹出并压栈到正向栈中->[栈尾3,2,1栈顶]
这个时候，我们在出队的时候，顺序就是[1,2,3]。

Kotlin实现

import java.util.Stack

fun main(args: Array<String>) {
    val testQueue = QueueEnhance<String>()
    testQueue.appendTail("Scala")
    testQueue.appendTail("Kotlin")
    testQueue.appendTail("Python")
    testQueue.appendTail("Ruby")
    testQueue.appendTail("C++")
    testQueue.appendTail("Java")

    while (testQueue.hasNext()) println(testQueue.deleteHead())
    // 测试栈为空异常
    testQueue.deleteHead()
}

class QueueEnhance<T> {
    private val stackForward = Stack<T>()
    private val stackReverse = Stack<T>()

    fun hasNext(): Boolean {
        return !stackForward.isEmpty() || !stackReverse.isEmpty()
    }

    fun appendTail(t: T) {
        stackReverse.add(t)
    }

    fun deleteHead(): T {
        // 先判断正向的栈是否为空，如果为空就将反向的栈pop出来放入正向的栈中
        if (stackForward.isEmpty()) {
            while (!stackReverse.isEmpty()) {
                stackForward.add(stackReverse.pop())
            }
        }

        // 如果正向的栈还是为空，就直接抛出异常
        if (stackForward.isEmpty()) throw Exception("栈为空")

        return stackForward.pop()
    }
}

输出结果

Scala
Kotlin
Python
Ruby
C++
Java
Exception in thread "main" java.lang.Exception: 栈为空
	at QueueEnhance.deleteHead(KDemo5.kt:38)
	at KDemo5Kt.main(KDemo5.kt:14)