「後進先出的Stack要變成先進先出的Queue，後進先出的Stack要變成先進先出的Queue，後進先出的Stack要變成先進先出的⋯⋯」學妹反覆念誦，有點走火入魔的趨勢。「⋯⋯後進先出要變成先進先出，那就把後進的變成先進的！」

學妹想通之後馬上就寫好了程式碼。

class MyQueue() {
    private val stack1 = Stack<Int>()
    private val stack2 = Stack<Int>()

    fun push(x: Int) {
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop())
        }
        stack2.add(x)
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop())
        }
    }

    fun pop(): Int {
        return stack2.pop()
    }

    fun peek(): Int {
        return stack2.peek()
    }

    fun empty(): Boolean {
        return stack2.isEmpty()
    }

}

「恭喜恭喜，妳成功啦！姐妹題225. Implement Stack using Queues妳應該也能依樣畫葫蘆完成。」

「嗯，讓先進的變成後進的就可以了！」學妹說著就把所有程式碼裡的stack取代成queue。

「咦？錯誤訊息說Queue只是interface，不能實體化。那我們要改用LinkedList嗎？」學妹轉頭問我。

我倒是有別的想法。「我比較想用ArrayDeque耶。」

「怎麼名字那麼像ArrayList？」

「嗯。LinkedList和ArrayDeque都實作了Deque，所以都可以從首尾查資料。而ArrayDeque和ArrayList一樣，有Array字眼還能增長長度，就是全家搬家。保持Array連續特性的情形下，查詢中間成員的時候比LinkedList有效率。不過在刪除中間成員的時候，反而是自由的LinkedList更有優勢，因為Array要重新整隊啊。」

「嗯⋯⋯這個題目沒有刪除中間成員的要求，那我就來試試ArrayDeque！」學妹很有實驗精神的試了幾個方法名稱。
發現add方法和平常一樣是新成員加在尾端，push方法卻是放在首端。「我怎麼感覺ArrayDeque有想要取代Stack的野心啊？」

「哈哈，有可能，畢竟程式的世界是很常汰舊換新的。」有時候用到被捨棄的方法還滿尷尬的。

「應該沒問題了，那我交出去囉。」學妹一臉輕鬆的說。早上失敗的陰影已經完全不見。

class MyStack() {
    private val queue1 = ArrayDeque<Int>()
    private val queue2 = ArrayDeque<Int>()

    fun push(x: Int) {
        while (!queue2.isEmpty()) {
            queue1.add(queue2.pop())
        }
        queue2.add(x)
        while (!queue1.isEmpty()) {
            queue2.add(queue1.pop())
        }
    }

    fun pop(): Int {
        return queue2.pop()
    }

    fun top(): Int {
        return queue2.peek()
    }

    fun empty(): Boolean {
        return queue2.isEmpty()
    }

}