📌

データ構造

2024/08/12に公開

Java

tech

スタック

一時的にデータを退避させたい時に有効なデータ構造。データの最後に入ったものが最初に取り出されるLIFO(Last in First Out)の規則に基づきデータを管理する。

JavaではStackクラスで実装することができる。

以下は逆ポーランド記法で計算するプログラムの例である。スタックを利用している。

import java.util.Scanner;
import java.util.Stack;

public class ALDS_1_3_A {
    public static void main(String[] args){
        // スタックオブジェクトの定義
        Stack<Object> stack = new Stack<>();
        try {
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                String input = sc.next();
                if(input.equals("+")){
                    // スタックから取り出す
                    int a = (int)stack.pop();
                    int b = (int)stack.pop();
                    stack.push(a + b);
                } else if(input.equals("-")){
                    int a = (int)stack.pop();
                    int b = (int)stack.pop();
                    stack.push(b - a);
                } else if(input.equals("*")){
                    int a = (int)stack.pop();
                    int b = (int)stack.pop();
                    stack.push(a * b);
                } else {
                    // スタックに追加する
                    stack.push(Integer.parseInt(input));
                }
            }
            System.out.println(stack.pop());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

※JavaのドキュメントではStackクラスよりもDequeインターフェースを持つArrayDequeクラスが推奨されている。

Javaのスタックオブジェクトのメソッドと対応するDequeインターフェースのメソッドは以下の通り。

メソッド	処理	Dequeメソッド
empty	スタックが空かどうか判定する。	-
peek	スタックの先頭にあるオブジェクトを取り出す。取り出すオブジェクトは削除されない。	getFirst()
pop	スタックの先頭にあるオブジェクトを削除して取り出す。	removeFirst()
push(E item)	スタックの先頭にオブジェクトを入れる。	addFirst(E item)
search(Object o)	スタックにあるオブジェクトの位置を位置から始まるインデックスで返す。	-

キュー

待ち行列と呼ばれ、データの到着順に処理したい時に使用するデータ構造。データの中で最初に入ったものが、最初に取り出されるFIFO(First in First Out)の規則に基づきデータを管理する。

JavaではQueueインターフェースが定義されており、複数のオブジェクトで実装されている。

以下はラウンドロビンスケジュールをシミュレートするプログラムの例である。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class ALDS1_3_B {
    public static void main(String[] args){
        try {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int q = sc.nextInt();
            sc.nextLine();
            Queue<Process> queue = new LinkedList<Process>();
            for(int i = 0; i < n; i++){
                String[] input = sc.nextLine().split(" ");
                queue.add(new Process(input[0], Integer.parseInt(input[1])));
            }
            int time = 0;

            while(!queue.isEmpty()){
                // キューの先頭を取り出す
                Process p = queue.poll();
                // 指定の時間内であれば処理を終了
                if(p.time <= q){
                    time += p.time;
                    System.out.println(p.name + " " + time);
                } else {
                    // 指定の時間を超えればその分時間を削減し、キューに入れ直す
                    time += q;
                    p.time -= q;
                    queue.add(p);
                }
            }
        }catch (Exception e) {
            e.printStackTrace();
        }
    }

    static class Process {
        String name;
        int time;
        Process(String name, int time){
            this.name = name;
            this.time = time;
        }
    }
}

Queueインターフェースのメソッドは以下の通り。

メソッド	処理
add(E e)	キューに要素を追加する
element	キューの先頭を取得する
offer(E e)	キューに要素を追加する
peek	キューの先頭を取得する。キューがからの場合はnullを返す。
poll	キューの先頭を取得して削除する。キューがからの場合はnullを返す。
remove	キューの先頭を取得して削除する。

QueueもまたDequeインターフェースのArrayDequeクラスで実装可能。

データ構造

スタック

キュー

リスト

Discussion