Javaのキューとスタックのデータ構造をサンプルコードを見ながら理解する

Java をはじめとするプログラミング言語には、「キュー」と「スタック」というデータ構造があります。

キューは最初に入れたデータを、最初に取り出す「先入れ先出しの（FIFO）」のデータ構造で、スタックは後から入れたデータを、最初に取り出す「後入れ先出し（LIFO）」データ構造です。

この記事では、Java でキューとスタックを使って、データの出し入れをする基本的な操作方法を解説します。

大量アクセスを伴うシステム開発では、「キュー」と「スタック」は重要な概念になるため、是非覚えておきましょう。

キュー（Queue）とは？

キュー（Queue）は、先入れ先出し（FIFO）のデータ構造で、先に入れたデータを先に取り出していきます。

例えるなら、人気がある飲食店での行列のように、最初に列に並んだ人から順に、お店の中に入っていくようなイメージです。

コンピューターの内部でも、CPUや入出力装置の順番待ちなどにキューの仕組みが使われており、パソコンの処理が重くて反応が遅くなるのも、多くのキューが追加されて処理が溜まってしまい、後から追加されたキューがなかなか処理されず待たされることにより、パソコンが遅くなるといったこともあります。

ポテパンダの一言メモ

Java では java.util.Queue インターフェイスを実装したクラスを使って、先入れ先出しのキューの処理を実装します。 java.util.Queue インターフェイスを実装したクラスには次のようなものがあります

ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

スタック（Stack）

スタック（Stack）は、後入れ先出し（LIFO）のデータ構造で、キューとは逆に、最後に入れたデータが最初に取り出される配列データです。

例えるなら、洗い終わって下から積み上げた皿を、上から順に取りだしていくイメージのデータ構造です。また、テキストエディタで最後の編集を元に戻す Undo（アンドゥ）」なども LIFOに該当します。

ArrayDequeクラスはキューもスタックも

Java には ArrayDeque というクラスがあります。

ArrayDeque クラスは、先出し先入れ構造のキューや、後入れ後出し構造のスタックも両方のデータ構造が扱うことができ、両端キューともこのクラスは呼ばれます。

ArrayDeque でキューを実装

まずは、ArrayDeque クラスの addLast と removeFirst メソッドを使って、先入れ先出し構造のキューを実装してみます。

次のサンプルコードをご覧ください、

import java.util.ArrayDeque;

public class Main {
  // キューのサンプルコード
  public static void main(String[] args) {
    Deque<String> queue = new ArrayDeque<String>();
    // キューにデータを登録（エンキュー）
    q.addLast("Java");
    q.addLast("Ruby");
    q.addLast("Python");

    System.out.println(q);  // 配列の内容を表示
    System.out.println(q.removeFirst());  // キューから１つ取り出し（デキュー）
    System.out.println(q);  // デキュー後の配列の内容を表示
  }
}

【実行結果】

[Java, Ruby, Python]
Java
[Ruby, Python]

addLast は配列の先頭にデータを追加するメソッドで、removeFirst は配列の先頭のデータを削除するメソッドです。この２つのメソッドを組み合わせることでキューを実装します。

ArrayDeque でスタックを実装

つぎは、ArrayDeque クラスの addLast と removeLast メソッドを使って、後入れ後出し構造のスタックを実装してみます。

import java.util.ArrayDeque;

public class Main {
  // スタックのサンプルコード
  public static void main(String[] args) {
    Deque<String> q = new ArrayDeque<String>();
    // スタックにデータを登録（プッシュ）
    q.addLast("Java");
    q.addLast("Ruby");
    q.addLast("Python");

    System.out.println(q);  // 配列の内容を表示
    System.out.println(q.removeLast());  // スタックから１つ取り出し（ポップ）
    System.out.println(q);  // デキュー後の配列の内容を表示
  }
}

【実行結果】

[Java, Ruby, Python]
Python
[Java, Ruby]

addLast および removeLast は配列の末尾にデータを追加・削除するメソッドです。この２つのメソッドを組み合わせることでスタックを実装できます。

値を削除せずに次に取り出す値を参照する方法

removeFirst や removeLast メソッドは、先頭または末尾の要素を取得したのち、取得した要素を配列から削除します。

要素を削除せすに次に取り出す値を参照する場合は、キューの場合は peekFirst メソッド、スタックの場合は peekLast メソッドを使用します。

実際に、キューの配列に対し、peekFirstメソッドを使って配列の先頭要素を参照してみるサンプルコードを見てみましょう。

import java.util.ArrayDeque;

public class Main {
  // キューのサンプルコード
  public static void main(String[] args) {
    Deque<String> queue = new ArrayDeque<String>();
    // キューにデータを登録（エンキュー）
    q.addLast("Java");
    q.addLast("Ruby");
    q.addLast("Python");

    System.out.println(q);  // 配列の内容を表示
    System.out.println(q.peekFirst());  // キューの先頭要素を参照
    System.out.println(q);  // デキュー後の配列の内容を表示
  }
}

【実行結果】

[Java, Ruby, Python]
Python
[Java, Ruby, Python]

このように、peekFirst メソッドを使用した場合は、配列から要素を削除せずに、次に取り出される要素を参照することができます。

まとめ

Java で先入れ先出しの FIFO 構造である「キュー」と、後入れ後出しの LIFO 構造である「スタック」の概念とサンプルコードを解説してきました。

「キュー」と「スタック」はさまざまなシーンで利用され、特に大規模な Webシステムや、多くのデバイスからアクセスが行われる Iot などのシステムでは、処理の順の制御するために「キュー」や「スタック」が用いられています。

【関連記事】
▶ RubyでQueue(キュー)プログラミング！キューとスタック概要から丁寧に解説