【LeetCode】【Kotlin】232. Implement Queue using Stacks

在 Kotlin 中使用 Stack

import java.util.Stack
fun main() {
    val stack = Stack()
    println(stack)
    
    stack.addAll(listOf(1,2,3,4))
    println(stack)
    
    stack.push(5) //加入元素到stack
    println(stack)
    
    print("pop ${stack.pop()}") //返回最上面的元素並刪除
    println(" -> $stack")
    
    print("peek ${stack.peek()}") //返回最上面的元素，但不刪除
    println(" -> $stack")
    
    println(stack.empty())
}

[]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
pop 5 -> [1, 2, 3, 4]
peek 4 -> [1, 2, 3, 4]
false

方法一 : 在 peek 與 pop 時，都將所有元素倒出取出第一個，再倒回去

class MyQueue() {
    val mainStack = Stack()
    val tempStack = Stack()

    //將元素 x 推到隊列末尾
    fun push(x: Int) {
        mainStack.push(x)
    }

    //從隊列的前面刪除元素並返回它
    fun pop(): Int {
        while(!mainStack.empty()){
            tempStack.push(mainStack.pop())
        }
        val firstElement = tempStack.pop()
        while(!tempStack.empty()){
            mainStack.push(tempStack.pop())
        }
        return firstElement
    }

    //返回隊列前面的元素
    fun peek(): Int {
        while(!mainStack.empty()){
            tempStack.push(mainStack.pop())
        }
        val firstElement = tempStack.pop()
        mainStack.push(firstElement)
        while(!tempStack.empty()){
            mainStack.push(tempStack.pop())
        }
        return firstElement
    }

    fun empty(): Boolean {
        return mainStack.empty()
    }

}

方法二 : 在push時就整理成反向的到stack

class MyQueue() {
    val mainStack = Stack()
    val tempStack = Stack()
    //var front : Int? = null

    fun push(x: Int) {
        while(!mainStack.empty()){
            tempStack.push(mainStack.pop())
        }
        mainStack.push(x)
        while(!tempStack.empty()){
            mainStack.push(tempStack.pop())
        }
        //front = mainStack.pop()
    }

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

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

    fun empty(): Boolean {
        return mainStack.empty()
    }

}

方法三 : 使用 stack1 存正序的， stack2 存倒序的

示意圖

除了stack1、stack2，另外用 front 存放在 stack1內的第一個元素。

在 pop 的時候，會丟出 stack2 最上面的元素出去。若 stack2 為空，則把 stack1 裡面的元素倒給 stack2。

在 peek 的時候，如果 stack2不為空，就把 stack2最上面的 pop 出去。若 stack2 為空，而stack1部為空，則 return 存有 stack1 內第一個元素 value 的 front。(在 push 時，一律把元素存進 stack1。如果 stack1為空，則代表要存進來的元素會是 stack1 內的第一個元素，就把它的值存進 front。)

class MyQueue() {
    val stack1 = Stack()
    val stack2 = Stack()
    var front : Int? = null

    fun push(x: Int) {
        if(stack1.empty()){
            front = x
        }
        stack1.push(x)
    }

    fun pop(): Int {
        if (stack2.empty()) {
            while(!stack1.empty()){
                stack2.push(stack1.pop())
            }
        }
        return stack2.pop()
    }

    fun peek(): Int {
        if(stack2.empty() && !stack1.empty()){
            return front ?: -1  
        }
        return stack2.peek()
    }

    fun empty(): Boolean {
        return stack1.empty() && stack2.empty()
    }

}