今天要實做兩個著名的資料結構 Stack 和 Queue

• Stack 是一種後進先出（Last-In-First-Out，LIFO）的資料結構，
  其中最後添加到 Stack 的元素首先被取出。
• Queue 是一種先進先出（First-In-First-Out，FIFO）的資料結構，
  其中最早添加到 Queue 的元素首先被取出。

Stack

Kotlin 中可以使用 Stack 類別實做，但更常見的做法是使用 LinkedList 或 ArrayDeque 來模擬 stack 的行為。

其中值得注意的是 java.util.ArrayDeque
它是 Java 標準庫提供的一個實現了 Double-ended Queue (簡稱Deque）介面的類別。
雙端佇列是一種特殊的 Queue，它允許在 Queue 的前端和後端進行元素的添加和刪除操作，因此可以用來實現 Stack 和 Queue 等資料結構。

import java.util.ArrayDeque

fun main() {
    val stack = ArrayDeque<Int>()

    // 推入元素到 stack
    stack.push(1)
    stack.push(2)
    stack.push(3)

    // 彈出元素
    val poppedElement = stack.pop()
    println("Popped element: $poppedElement") // 輸出 3
}

Queue

Kotlin 中可以使用 Queue 介面實做，最常見的實做是使用 LinkedList 或 ArrayDeque。

import java.util.ArrayDeque

fun main() {
    val queue = ArrayDeque<Int>()

    // 將元素添加到 queue 尾部
    queue.offer(1)
    queue.offer(2)
    queue.offer(3)

    // 取出 queue 的頭元素
    val polledElement = queue.poll()
    println("Polled element: $polledElement") // 輸出 1
}

下方演示 Stack 可以實做 Queue

Stack to Queue

import java.util.Stack

class QueueWithStacks<T> {
    private val stack1 = Stack<T>()
    private val stack2 = Stack<T>()

    fun enqueue(item: T) {
        // 將元素壓入 stack1
        stack1.push(item)
    }

    fun dequeue(): T? {
        // 如果 stack2 是空的，將 stack1 中的元素進行反轉，然後壓入 stack2
        if (stack2.isEmpty()) {
            while (stack1.isNotEmpty()) {
                stack2.push(stack1.pop())
            }
        }
        // 從 stack2 中彈出元素，實現 Queue 的行為
        return if (stack2.isNotEmpty()) {
            stack2.pop()
        } else {
            null
        }
    }
}

我們必須使用兩個 Stack，stack1 和 stack2 來實現 Queue。

當要取出元素時，我們首先檢查 stack2 是否為空，如果是空的，我們將 stack1 中的元素反轉壓入 stack2，然後從 stack2 中彈出元素，以實現 Queue 的 FIFO 行為。

反之，Queue 也可以實做 Stack

Queue to Stack

import java.util.LinkedList

class StackWithQueue<T> {
    private val queue = LinkedList<T>()

    fun push(item: T) {
        // 將元素添加到 Queue 的尾部
        queue.offer(item)
    }

    fun pop(): T? {
        // 將 Queue 中除了最後一個元素外的其他元素重新排列到 Queue 中
        val size = queue.size
        for (i in 0 until size - 1) {
            queue.offer(queue.poll())
        }
        // 取出最後一個元素，模擬 Stack 的行為
        return if (size > 0) {
            queue.poll()
        } else {
            null
        }
    }
}

這裡我們使用 LinkedList 來實現 Stack。

當要取出元素時，我們將 Queue 中除了最後一個元素外的其他元素重新排列到 Queue 中，然後取出最後一個元素，以實現 Stack 的 LIFO 行為。

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！

Reference

• Stack and Queue