感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

スタックとキューのサンプルをJavaで作って遊んでみる。

<スポンサーリンク>

アルゴリズムとデータ構造の勉強は、部活でフットワークやるみたいに、コツコツやっていきたい。
アルゴリズムは、(現時点では)パズルを解くみたいで面白い。
難しくなると苦しくなるかもしれないけれど。

今日は定番のスタックとキュー。

スタックとは

スタックとは、データを一時的に蓄えるための基本的なデータ構造の一つ。
データの出し入れは後入れ先出し(Last In First Out)で行われる。

後入れ先出しとは、重ねた皿が上から順番に使われていくみたいに、あとに入れたデータが先に取り出されるということ。

スタックにデータを入れる操作をプッシュ(push)という。
スタックからデータを取り出す操作をポップ(pop)という。

単純なスタックのサンプルはこちら。

package dataStructure.stack;

public class StackExample {
	private int stackSize;
	private int stackPointer;
	private int[] stack;

	public StackExample(int size) {
		this.stackPointer = 0;
		this.stackSize = size;

		stack = new int[stackSize];
	}

	public int push(int num) {
		if (stackPointer >= stackSize) {
			throw new StackOverflowException();
		}
		return stack[stackPointer++] = num;
	}

	public int pop() {
		if (stackPointer <= 0) {
			throw new EmptyStackException();
		}
		return stack[--stackPointer];
	}

	public int peek() {
		if (stackPointer <= 0) {
			throw new EmptyStackException();
		}
		return stack[stackPointer - 1];
	}

	public class StackOverflowException extends RuntimeException {
		public StackOverflowException() {
			super("スタックのサイズを超えています!");
		}
	}

	public class EmptyStackException extends RuntimeException {
		public EmptyStackException () {
			super("スタックが空ですよ!");
		}
	}
}

上のスタックをイメージしたクラスを使うのが以下のMainクラス。

package dataStructure.stack;

public class StackMain {
	public static void main(String[] args) {
		int stackSize = 3;
		StackExample stack = new StackExample(stackSize);
		//stack.pop(); //→EmptyStackException: スタックが空ですよ!
		stack.push(10);
		stack.push(5);
		System.out.println("ピーク(一番上を見てみると・・・):" + stack.peek());  //頂上の「5」が見える
		stack.push(7);
		//stack.push(15); //→StackOverflowException
		System.out.println("ポップ:" + stack.pop()); //一番上の「7」が取り出される
		System.out.println("ポップ:" + stack.pop()); //一番上の「5」が取り出される
	}
}

実行すると以下のように、あとにいれたものから取り出されていく。

ピーク(一番上を見てみると・・・):5
ポップ:7
ポップ:5

キューとは

キューは先入れ先出し(First In First Out)のデータ構造のこと。

先入れ先出しとは、最初に入れられたデータから取り出されていくということ。
ディズニーランドの行列に並んだ人たちが、最初に並んだ順に中に入っていくみたいに。

データを追加する操作をエンキュー(enqueue)。
データを取り出す操作をデキュー(dequeue)という。

データが取り出される側を先頭(front)、データが押し込まれる側を末尾(rear)という。

以下にキューのサンプルを作ってみる。
配列を一つずつずらしてみたり、いい頭の運動になった。

package dataStructure.queue;

public class QueueExample {
	private int queueSize;
	private int queueNum;
	private int[] queue;

	public QueueExample(int size) {
		this.queueSize = size;
		this.queueNum = 0;
		queue = new int[queueSize];
	}

	public int enqueue(int num) {
		if (queueNum >= queueSize) {
			throw new QueueOverflowException();
		}
		return queue[queueNum++] = num;
	}

	public int dequeue() {
		if (queueNum <= 0) {
			throw new EmptyQueueException();
		}
		int ret = queue[0];
		queueNum--;
		shift(queue);
		return ret;
	}

	public void shift(int[] array) {
		int retArray[] = new int[queueSize];
		int tmp=0;
		for (int i=1; i < array.length; i++) {
			retArray[tmp] = array[i];
			tmp++;
		}
		this.queue = retArray;
	}

	public void see(int[] array) {
		for (int i=0; i < array.length;i++) {
			System.out.println("array[" + i + "] = " + array[i]);
		}
	}

	public class QueueOverflowException extends RuntimeException {
		public QueueOverflowException() {
			super("キューのサイズを超えています!");
		}
	}

	public class EmptyQueueException extends RuntimeException {
		public EmptyQueueException () {
			super("キューが空ですよ!");
		}
	}
}

上記のキューのサンプルを使うMainクラス

package dataStructure.queue;

public class QueueMain {
	public static void main(String[] args) throws InterruptedException {
		QueueExample queue = new QueueExample(3);
		queue.enqueue(5);
		queue.enqueue(7);
		queue.enqueue(10);
		//queue.enqueue(15); //QueueOverflowException: キューのサイズを超えています!
		System.out.println("デキュー:" + queue.dequeue());
		System.out.println("デキュー:" + queue.dequeue());
		System.out.println("デキュー:" + queue.dequeue());

		Thread.sleep(100);
		System.out.println("デキュー" + queue.dequeue()); //EmptyQueueException: キューが空ですよ!
	}
}

実行すると以下のようにコンソールに表示される。

デキュー:5
デキュー:7
デキュー:10
Exception in thread "main" dataStructure.queue.QueueExample$EmptyQueueException: キューが空ですよ!
	at dataStructure.queue.QueueExample.dequeue(QueueExample.java:23)
	at dataStructure.queue.QueueMain.main(QueueMain.java:15)

参考にした本

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

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

いつもアルゴリズムの勉強するときにこの本を参考にしている。
キューのところはサンプルコードがなかったので、自分で適当に作った感じになってしまった。
頭の体操として、午前中にこういうのをやると目が覚めることに気付いた。