明解 Javaによるアルゴリズムとデータ構造 4_スタックとキュー

4-1 スタック

フィールド: スタックの容量・ポインタ。後入れ先出し(LIFO - Last In First Out)。

  • push, pop, peek, dump
  • indexOf, size, clear, capacity
  • isEmpty, isFull
疑問
  • 総称クラスが java.lang.Throwable をサブクラス化できないのってなんでだっけ?
    • 例) hogeクラス内に、例外クラス FugaException extends RuntimeException を作れない。
    • static class FugaException extends RuntimeException だと OK
  • staticだといけるということは、インスタンス化に問題有りということなんかな?

4-2 キュー

フィールド: キューの容量・ポインタ。先入れ先出し(FIFO - First In First Out)。

  • 配列キュー
    • enqueue, dequeue, peek, dump
    • indexOf, size, clear, capacity
    • isEmpty, isFull
  • リングバッファ(ring buffer)キュー
    • 要素ピックアップ時の残要素シフトコストが、配列キューよりも下がるのがメリット
    • max, front, rear, num


明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造