スタック・キュー・デック・優先度付きキュー[Java]

はじめに

こんにちは。
プログラミング初心者wakinozaと申します。
Java勉強中に調べたことを記事にまとめています。

十分気をつけて執筆していますが、なにぶん初心者が書いた記事なので、理解が浅い点などあるかと思います。
間違い等あれば、指摘いただけると助かります。

記事を参考にされる方は、初心者の記事であることを念頭において、お読みいただけると幸いです。

対象読者

• Javaを勉強中の方
• Javaのデータ構造について知りたい方

記事のテーマ

• 「AtCorder」のために、アルゴリズムとデータ構造の勉強をはじめました
• 本記事では、代表的なデータ構造であるスタック、キュー、デック、優先度付きキューについて解説します

目次

1.データ構造
2.スタック
3.キュー
4.デック
5.優先度付きキュー

本文

1. データ構造

データ構造 (Data Structure) は、「データを格納し、特定の方法でアクセス・操作するための構造」を指します。

Java言語には、配列、リスト、マップ、セット、スタック、キュー、二分探索木、ヒープなど様々なデータ構造が用意されています。
それぞれのデータ構造は、データの配置とデータの操作方法に独自のルールを持っています。
そのため、個々の特徴やルールを理解しなければ、問題解決に最適なデータ構造を選択することができません。
もし、問題解決に適していないデータ構造を選択すると、プログラムの処理効率（時間計算量や空間計算量）を低下させてしまう可能性もあります。
よって、データ構造の特徴を理解することが、プログラムの処理効率を上げる重要な要素の一つとなるのです。

この記事では、スタック・キュー・デック・優先度キューの4つのデータ構造について、データ格納・操作のルール、主な使用用途、コード例を挙げて説明していきます。

2. スタック

2.1. スタックの特徴

スタック(stack)は、データを一時的に蓄えるためのデータ構造の一つです。

データの出し入れに、「後入れ先出し(LIFO/Last In First Out)」というルールがあることが特徴となります。
「後入れ先出し」とは、最後に入れたデータが最初に取り出されるということです。

例えば、本が積み上がっている状態を想像してみてください。
新しい本を加えようと思うと、最上段に本を積み上げることになります。この積み上がった状態から本を１冊取り出そうと思うと、一番上に置いてある本を手に取ることになります。下の方から本を取ろうと思うと、積み上げた本が崩れてしまうためです。
この時、一番上の本が、一番最後に積み上げた本であることに注目してください。

このように、データを積み上げた際に、最後に入れたデータが最初に取り出される構造を「後入れ先出し（LIFO）」といいます。

2.2. スタックの主なメソッド

スタックは、以下の３種類のメソッドによって、データを操作します。

振る舞い	メソッド名	時間計算量
末尾に追加	push	O(1)
末尾を削除して取得	pop	O(1)
末尾を参照	peek	O(1)

スタックの操作は、常に最後に追加された要素（末尾）に対して行われるため、インデックス計算が不要です。そのため、時間計算量はO(1)と非常に高速に行えます。

2.3. スタックの主な使用用途

• 関数呼び出し（コールスタック） : プログラム実行時に、メソッドの呼び出しやローカル変数を管理する仕組みを「コールスタック」と呼びます。コールスタックは、その名の通り、スタック構造でデータを処理しています

• ブラウザの履歴 : Webページの「戻る」機能などは、ページ履歴をスタック構造で取り出すことで実現しています。最新のページ（最後に追加されたもの）から順番に戻ります

• 深さ優先探索 (DFS) : グラフやツリー構造の探索アルゴリズムでスタック構造が用いられています

2.4. スタックのコード例

標準ライブラリにjava.util.Stackクラスがありますが、現在はStackクラスを用いず、ArrayDequeクラスを利用することが推奨されています。
コード例では、わかりやすさを優先して、自作クラスで、コード例を紹介します。
ArrayDequeクラスを用いた、スタックの実装方法は、後々説明します。

import java.util.ArrayList;

// スタック構造の自作クラス
class CustomStack<E> {
  // ArrayListを内部データ格納に使用する
  private final ArrayList<E> elements = new ArrayList<>();

  // pushメソッド
  public void push(E item) {
   elements.add(item); 
  }

  // popメソッド
  public E pop() {
    if (elements.isEmpty()) {
      return null;
    }
    return elements.remove(elements.size() - 1);
  }

  // peekメソッド
  public E peek() {
    if (elements.isEmpty()) {
      return null;
    }
    return elements.get(elements.size() - 1);
  }
}

public class StackExample {
  public static void main(String[] args) {
    // String型の自作スタックを作成
    CustomStack<String> stack = new CustomStack<>();

    // データの追加 
    stack.push("1");
    stack.push("2");
    stack.push("3"); 
    stack.push("4"); 

    //現在の末尾を参照する
    System.out.println(stack.peek());
    //結果：4

    // 末尾を削除と取得
    System.out.println(stack.pop());
    //結果：4

      //現在の末尾を参照する
    System.out.println(stack.peek());
    //結果：3

    // 末尾を削除と取得
    System.out.println(stack.pop());
    //結果：3

      //現在の末尾を参照する
    System.out.println(stack.peek());
    //結果：2
  }
}

3. キュー

3.1. キューの特徴

キュー(Queue)は、データを一時的に蓄えるためのデータ構造の一つです。
データの出し入れに、「先入れ先出し(FIFO/First In First Out)」というルールがあることが特徴です。
「先入れ先出し」とは、最初に入れたデータが最初に取り出されるということです。

このデータ構造は、店の前で行列に並んでいる時の状態を考えるとイメージしやすいです。
行列では、最初に並んだ人が先頭になり、最初に店に入ることができます。
このように、データを積み上げる際に、最初に入れたデータが先頭に来るデータ構造を「先入れ先出し」といいます。

3.2. キューの主なメソッド

キューは、以下の３種類の振る舞いが可能です。それぞれの振る舞いには、例外をスローするものと、特殊な値を返すものに分けられます。

振る舞い	例外をスローするメソッド名	特殊な値を返すメソッド名	時間計算量
末尾に挿入(enqueue)	add	offer	O(1)
先頭を削除して取得(dequeue)	remove	poll	O(1)
先頭を参照	element	peek	O(1)

キューの操作は、常に両端の要素に対して行うものであるため、時間計算量はO(1)と高速に行えます。

3.3. キューの主な使用用途

キューの特性は、順番待ちやタスク処理など順序を保証する必要がある処理に適しています。

• タスクスケジューリング : OSなどで、次に実行すべきプロセスやタスクの順序を管理します

• 入出力バッファ : データの読み書きなど、速度の異なるデータの受け渡しに利用されます

• 幅優先探索(BFS) : グラフやツリーの探索アルゴリズムで、現在のノードの隣接ノードを順番に訪れるために使用されます

3.4. キューのコード例

Javaでは、キューはインターフェースであり、具体的な実装はLinkedListクラスやArrayDequeクラスなどが用意されています。

わかりやすさを優先し、自作クラスでコード例を紹介します。
ArrayDequeを用いた、キュー実現方法は、後々説明します。

import java.util.ArrayList;
import java.util.NoSuchElementException;

class CustomQueue<E> {
  // データの格納に ArrayList を利用
  private final ArrayList<E> elements = new ArrayList<>();

  //enqueue: 末尾に挿入
  public boolean enqueue(E item) {
    elements.add(item);
    return true;
  }

  //dequeue: 先頭から削除
  public E dequeue() {
    if (elements.isEmpty()) {
      return null;
    }
    return elements.remove(0); 
    //自作クラスではArrayListを利用しているため、dequeueメソッドの時間計算量は O(N) ですが、実装クラスのLinkedListやArrayDequeではO(1)となります。
  }

  //peek
  public E peek() {
    if (elements.isEmpty()) {
      return null;
    }
    return elements.get(0); // O(1)
  }
}

public class QueueExample {
  public static void main(String[] args) {
    // 文字列型の自作キューを作成
    CustomQueue<String> queue = new CustomQueue<>();

    // データの追加
    queue.enqueue("Aさん"); 
    queue.enqueue("Bさん"); 
    queue.enqueue("Cさん");

    //現在の先頭を参照する
    System.out.println(queue.peek()); 
    // 結果：Aさん

    // 先頭を削除する
    queue.dequeue();

    //現在の先頭を参照する
    System.out.println(queue.peek()); 
    // 結果：Bさん

    // 先頭を削除する
    queue.dequeue();

    // 現在の先頭を参照する
    System.out.println(queue.peek()); 
    // 結果：Cさん
  }
}

4. デック

4.1. デックの特徴

デック(Deque、Double-Ended Queue)は、データを一時的に蓄えるためのデータ構造の一つです。
デックは「両端キュー」とも呼ばれ、キュー（FIFO）としてもスタック（LIFO）としても機能できるハイブリッドなデータ構造です。
要素の追加と削除を両端（先頭と末尾）のどちらからでも行うことができる柔軟性が特徴です。

4.2. デックの主なメソッド

デックは、java.util.ArrayDequeクラスを主に利用するので、ここでは、ArrayDequeクラスのメソッドを紹介します。

また、スタックとキューを実現する際にも、ArrayDequeクラスを利用することが推奨されています。
そのため、スタック用やキュー用のメソッド名が用意されていますが、これらはすべて同じデックの機能を呼び出しており、振る舞いに違いはありません。

これは、デック・スタック・キューのどの用途でArrayDequeクラスを利用しているのを、メソッド名から判別できるようにするために用意されていると思われます。

振る舞い	失敗した時に例外をスローするメソッド名	失敗した時に特殊な値を返すメソッド名	キューに相当	スタックに相当	時間計算量
先頭に要素を追加	addFirst	offerFirst	-	push	O(1)
末尾に要素を追加	addLast	offerLast	add / offer	-	O(1)
先頭から削除と取得	removeFirst	pollFirst	remove / poll	pop	O(1)
末尾から削除と取得	removeLast	pollLast	-	-	O(1)
先頭を参照	getFirst	peekFirst	element / peek	peek	O(1)
末尾を参照	getLast	peekLast	-	-	O(1)

4.3. デックの主な使用用途

デックは、スタックやキューを実現できるため、スタックやキューに向いている用途に利用できます。
また、両端性キューの特性を活かして、以下の用途などで用いられています。

• スライディングウィンドウの最小値／最大値のアルゴリズム
• 双方向探索
• 時間順データ管理

4.4. デックのコード例

デック具体的な実装は配列ベースのArrayDequeクラスや連結リストベースのLinkedListクラスとして提供されています。
ここでは、ArrayDequeクラスのコード例を紹介していきます。

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {
  public static void main(String[] args) {
    Deque<String> arrayDeque = new ArrayDeque<>();

    //末尾に追加
    arrayDeque.offerLast("タスクB");
    arrayDeque.offerLast("タスクC");
    arrayDeque.offerLast("タスクD");

    //先頭に追加
    arrayDeque.offerFirst("タスクA");

    System.out.println(arrayDeque); 
    // 結果：タスクA、タスクB、タスクC、タスクD 

    // 先頭要素の取得と削除 
    String pollFirst = arrayDeque.pollFirst();
    System.out.println(pollFirst); 
    // 結果：タスクA
    System.out.println(arrayDeque);
    // 結果：タスクB、タスクC、タスクD 

    // 末尾要素の取得と削除 
    String pollLast = arrayDeque.pollLast();
    System.out.println(pollLast); 
    // 結果：タスクD
    System.out.println(arrayDeque);
    // 結果：タスクB、タスクC


    // 先頭の要素を参照
    String peekFirst = arrayDeque.peekFirst();
    System.out.println(peekFirst); 
    // 結果：タスクB

    // 末尾の要素を参照
    String peekLast = arrayDeque.peekLast();
    System.out.println(peekLast); 
    // 結果：タスクC
}

5. 優先度付きキュー

5.1. 優先度付きキューの特徴

優先度付きキュー（PriorityQueue）は、要素が追加された順序ではなく、要素の順位づけに基づいて順序が決定される特殊なキューです。
「キュー」の一種ではありますが、「先入れ先出し」の原則は無視されます。

順位の優先度を指定しない場合は、要素の自然順位づけに基づいて順序が構成され、最小要素が先頭になります。コンストラクタの引数にComparatorを渡すことで、順位の優先度を指定することもできます。

内部では優先度ヒープが用いられています。

5.2. 優先度付きキューの主なメソッド

振る舞い	メソッド名	時間計算量
末尾に挿入	add / offer	O(logN)
先頭を削除して取得	remove / poll	O(logN)
先頭を参照	peek	O(1)

5.3. 優先度付きキューの主な使用用途

優先度付きキューは、タスクやイベントを優先度順に処理する必要がある場合に適しています。

• スケジューリング：オペレーティングシステムにおいて、次に実行すべき最も優先度の高いタスクを管理するために利用されます。

• イベントシミュレーション：シミュレーションシステムで、次に発生すべき最も早い時刻のイベントを効率的に取り出すために使用されます。

• アルゴリズム：ダイクストラ法（最短経路問題）やプリム法（最小全域木問題）など、貪欲法に基づく多くのグラフアルゴリズムで、次に処理すべき最も優先度の高いノードを効率的に選択するために不可欠です。

5.4. 優先度付きキューのコード例

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueExample {
  public static void main(String[] args) {
    //デフォルトの優先度付きキュー
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    minHeap.offer(10);
    minHeap.offer(5);   // 最小値
    minHeap.offer(15);   

    System.out.println(minHeap.peek());
    //結果：5

    //最小値から取り出される
    System.out.println(minHeap.poll());
    //結果：5
    System.out.println(minHeap.poll());
    //結果：10
    System.out.println(minHeap.poll());
    //結果：15

    //Comparator引数で渡すことで、数値が大きいほど優先度が高くなるように指定
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    
    maxHeap.offer(10);
    maxHeap.offer(5);
    maxHeap.offer(20);  // 最大値

    System.out.println(maxHeap.peek());
    //結果：20

    //最大値から取り出される
    System.out.println(maxHeap.poll());
    //結果：20
    System.out.println(maxHeap.poll());
    //結果：10
    System.out.println(maxHeap.poll());
    //結果：5

  }
}

まとめ

• スタック（Stack）: 最後に格納したデータが最初に取り出される（LIFO）データ構造。関数呼び出しやブラウザの「戻る」機能などで利用されます

• キュー（Queue）: 最初に格納したデータが最初に取り出される（FIFO）データ構造。タスクの順番待ちなど、順序性が重要な処理で利用されます

• デック（Deque）: データの先頭と末尾の両方から追加・削除ができる柔軟なデータ構造で、スタックとキューのどちらの用途でも利用できます

• 優先度付きキュー（PriorityQueue）: 格納された順序ではなく、設定された優先度順にデータを取り出すデータ構造。タスクスケジューリングや最短経路探索アルゴリズムなどで利用されます

---

記事は以上です。
最後までお読みいただき、ありがとうございました。

参考情報一覧

この記事は以下の情報を参考にして執筆しました。

• [プロになるJava]
• [Java本格入門]
• [新・明解Javaで学ぶアルゴリズムとデータ構造 第２版]
• [競技プログラミングの鉄則]
• アルゴリズムとデータ構造(java)) (最終更新 2025-01-09) (参照 2025-10-01)
• 一目で思い出せるJavaのArrayDequeのキュー/スタックとしての使い方 (最終更新 2021-05-09) (参照 2025-10-01)
• 【Java】Queue、Deque、Stackの関係 (最終更新 2021-02-12) (参照 2025-10-01)
• 公式ドキュメント) (参照 2025-10-01)