こんにちは。iQeda [@iQeeeda] です。
今回はデータ構造のひとつ「キューとスタック」を解説します。
たくさん問題も解くので、エンジニア面談の傾向と対策になると思います。
目次
【LIFO】スタックとは
スタックとは「下から上にデータが積み重なった」データ構造です。
縦に積み上げられたお皿をイメージしてください。お皿は上から取るしかありませんね。
スタックは LIFO ( Last In, First Out ) つまり「後入れ先出し」です。
最後に積まれたデータが、最初に取り出される仕組みです。
配列と違って index 指定できないので、アクセスは一定時間じゃありません。
逆にシフト操作が必要ないので、要素の追加・削除は一定時間です。
スタックのメリット
問題によっては、配列よりスタックにデータを持たせる方がよい場合があります。
たとえば特定の再帰アルゴリズムを使う場合、
再帰的に一時データをスタック保存するときがあります。
再帰的なチェックが失敗した、などの理由でバックトラックしたい状況があります。
データを一手前の状態に戻したいので「一時データを削除する」場合などにスタックは便利です。
他にも「再帰アルゴリズムを反復処理で実装する」ときにもスタックが利用できます。
スタックの実装
データ追加した場所と同じ側から削除する場合、
スタックは「連結リストを使って実装できる」ことに注目してください。
public class MyStack<T> {
private static class StackNode<T> {
private T data;
private StackNode<T> next;
// コンストラクタ
public StackNode(T data) {
this.data = data;
}
}
// 最新ノードを管理する
private StaticNode<T> top;
/*
* スタックの一番上からデータを削除する (取り出す)
*/
public T pop() {
if (top == null) throw new EmptyStackException();
T item = top.data;
top = top.next;
return item;
}
/*
* スタックの一番上に item 要素を追加する
*/
public void push(T item) {
StackNode<T> t = new StackNode<T>(item);
t.next = top;
top = t;
}
/*
* スタックの一番上の要素を返す (要素は削除しない)
*/
public T peek() {
if (top == null) throw new EmptyStackException();
return top.data;
}
/*
* スタックが空の場合 true を返す
*/
public boolean isEmpty() {
return top == null;
}
}
【FIFO】キューとは
キューとは「待ち行列」のデータ構造です。
チケット売り場の行列をイメージしてください。最初の人が最初にチケットを手にできますね。
キューは FIFO ( First In First Out ) つまり「先入れ先出し」です。
最初に並んだデータが、最初に取り出される仕組みです。
キューのメリット
キューは「幅優先探索」や「キャッシュ」の実装でよく使われます。
たとえば幅優先探索では「処理対象のノードリスト」をキューで使用できます。
ノード処理のたびに、隣接ノードをキュー末尾に追加します。
こうすると、ノードが出現する順序でノード処理できます。
キューの実装
キューも連結リストで実装可能です。
要素の追加と削除が反対であるだけで、本質的には同じです。
キューは最初と最後のノードの更新が必要なので注意してください。
public class MyQueue<T> {
private static class QueueNode<T> {
private T data;
private QueueNode<T> next;
// コンストラクタ
public QueueNode(T data) {
this.data = data;
}
}
// 最初と最後のノードを管理する
private QueueNode<T> first;
private QueueNode<T> last;
/*
* 要素をリストの最後に追加する
*/
public void add(T item) {
QueueNode<T> t = new QueueNode<T>(item);
if (last != null) {
last.next = t;
}
last = t;
if (first == null) {
first = last;
}
}
/*
* 先頭の要素を削除する
*/
public T remove() {
if (first == null) throw new NoSuchElementException();
T data = first.data;
first = first.next;
if (first == null) {
last = null;
}
return data;
}
/*
* 先頭の要素を返す (要素は削除しない)
*/
public T peek() {
if (first == null) throw new NoSuchElementException();
return first.data;
}
/*
* キューが空の場合 true を返す
*/
public boolean isEmpty() {
return first == null;
}
}
スタック・キューの問題集
3 つのスタック
1 つの配列を使って 3 つのスタックを実装するにはどのようにすればよいでしょうか。
答え
問題の難易度はスタックにどの程度までの機能を持たせるかに依存します。
固定式
単純に固定領域を割り当てることで解決できます。
配列を 3 等分して個々のスタックを領域内で扱ってみましょう。
サイズ n の配列を以下のように分割してスタックに割り当てます。
- スタック 1
- [0, n/3]
- スタック 2
- [n/3, 2n/3]
- スタック 3
- [2n/3, n]
class FixedMultiStack {
private int numberOfStacks = 3;
private int stackCapacity;
// 3 つのスタックの value をこの values 1 つで管理する
// [スタック 1 の value A, スタック 1 の value B, ...
// スタック 2 の value C, スタック 2 の value D, ...
// スタック 3 の value E, スタック 3 の value F, ...]
private int[] values;
// 3 つのスタックの size をこの sizes 1 つで管理する
// [スタック 1 の size, スタック 2 の size, スタック 3 の size]
private int[] sizes;
// コンストラクタ
public FixedMultiStack(int stackSize) {
// 各スタックの限界サイズを定義
stackCapacity = stackSize;
// スタックサイズ指定 * 3 で values の領域確保する
values = new int[stackSize * numberOfStacks];
sizes = new int[numberOfStacks];
}
/*
* スタック 1 <- stackNum でいうと 0
* スタック 2 <- stackNum でいうと 1
* スタック 3 <- stackNum でいうと 2
*/
// スタックに値を加える
public void push(int stackNum, int value) throws FullStackException {
// 次の要素を追加するためのスペースがあることを確認する
if (isFull(stackNum)) {
throw new FullStackException();
}
// スタックポインタを進めてトップの値を更新する
sizes[stackNum]++;
values[indexOfTop(stackNum)] = value;
}
// スタックから要素を取り出す
public int pop(int stackNum) {
if (isEmpty(stackNum)) {
throw new EmptyStackExepition()
}
int topIndex = indexOfTop(stackNum);
// 対象スタックのトップの値を得る
int value = values[topIndex];
// 対象スタックのトップの値をクリアする
values[topIndex] = 0;
// 対象スタックのサイズを縮小する
sizes[stackNum]--;
return value;
}
// トップの要素を返す
public int peek(int stackNum) {
if (isEmpty(stackNum)) {
throw new EmptyStackException();
}
return values[indexOfTop];
}
// スタックが空かどうかを返す
public boolean isEmpty(int stackNum) {
return sizes[stackNum] == 0;
}
// スタックが一杯かどうかを返す
public boolean isFull(int stackNum) {
return sizes[stackNum] == stackCapacity;
}
// スタックのトップのインデックスを返す
private int indexOfTop(int stackNum) {
// どのスタックを指定しても、最新の要素を見つけられるように offset を使って index を調整する
int offset = stackNum * stackCapacity;
int size = sizes[stackNum];
// 配列末尾が一番新しい要素: スタックで取り出されるトップインデックス
return offset + size - 1;
}
}
この実装では使用するスタックが偏ってしまうが欠点です。
1 つのスタックがいっぱいでも、他のスタックは空の状態…という状況が起こりうります。
スタックの使い方に関する情報があれば、必要に応じてアルゴリズムを変えてください。
例えば「スタック 1 がスタック 2 よりも大きくなりそう」という情報があれば、
領域の割り当てを「スタック 1 が多く、スタック 2 は少なくする」という対応をしてください。
変動式
今度は領域の割当を変動式にしてみましょう。
固定式に比べて複雑さが増すので注意してください。
public class MultiStack {
/*
* StackInfo は各スタックに関するデータセットを保持する
* 実際のスタックの要素を持っているわけではない
* 個別の変数はまとめることもできるが、煩雑でメリットはない
*/
public class StackInfo {
public int start, size, capacity;
// コンストラクタ
public StackInfo(int start, int capacity) {
this.start = start;
this.capacity = capacity;
}
/*
* 一杯になった配列の index がスタックの範囲内かどうか確認する
* スタックの index は配列の最初に回り込むことができる
*/
public boolean isWithinStackCapacity(int index) {
// 配列の範囲外なら false を返却
if (index < 0 || index >= values.length) {
return false;
}
// 配列の前部に index が回り込むように調整する
int contiguousIndex = (index < start) ? index + values.length : index;
int end = start + capacity;
return start <= contiguousIndex && contiguousIndex < end;
}
public int lastCapacityIndex() {
return adjustIndex(start + capacity - 1);
}
public int lastElementIndex() {
return adjustIndex(start + size - 1);
}
public boolean isFull() {
return size == capacity;
}
public boolean isEmpty() {
return size == 0;
}
}
private StackInfo[] info;
private int[] values;
// コンストラクタ
public MultiStack(int numberOfStacks, int defaultSize) {
// 全スタックの情報を記述するデータを生成する
info = new StackInfo[numberOfStacks];
for (int i = 0; i < numberOfStacks; i++) {
info[i] = new StackInfo(defaultSize * i, defaultSize)
}
values = new int[numberOfStacks * defaultSize];
}
/*
* stackNum のスタックに値を追加して、必要に応じてスタックをシフト・拡張する
*/
public void push(int stackNum, int value) throws FullStackException {
// すべてのスタックが一杯の場合は例外を投げる
if (allStacksAreFull()) {
throw new FullStackException();
}
StackInfo stack = info[stackNum];
// このスタックが一杯の場合は拡張する
if (stack.isFull()) {
expand(stackNum);
}
// 配列内でのスタックのトップにあたる要素の index + 1 を探して、スタックポインタを増やす
stack.size++;
values[stack.lastElementIndex()] = value;
}
// スタックから値を取り除く
public int pop(int stackNum) throws Exception {
StackInfo stack = info[stackNum];
if (stack.isEmpty()) {
throw new EmptyStackException();
}
// 最後の要素を取り除く
int value = values[stack.lastElementIndex()];
// 要素をクリア
values[stack.lastElementIndex()] = 0;
// サイズを縮小
stack.size--;
return value;
}
// スタックのトップの要素を得る
public int peek(int stackNum) {
StackInfo stack = info[stackNum];
return values[stack.lastElementIndex()];
}
/*
* スタック要素を 1 つ分シフトする
* 許容サイズ内であれば 1 要素分スタックを縮小する
* そうでない場合、次のスタックもシフトする必要がある
*/
private void shift(int stackNum) {
System.out.println("/// Shifting " + stackNum);
StackInfo stack = info[stackNum];
// このスタックが一杯の場合、次のスタックを 1 要素分移動させる必要がある
// 移動させて空いた index をこのスタックに割り当てる
if (stack.size >= stack.capacity) {
int nextStack = (stackNum + 1) % info.length;
shift(nextStack);
// 次のスタックで空けた index の分、容量を増やす
stack.capacity++;
}
// スタック上のすべての値を 1 つ分シフトする
int index = stack.lastCapacityIndex();
while (stack.isWithinStackCapacity(index)) {
values[index] = values[previousIndex(index)];
index = previousIndex(index);
}
/*
* スタックデータの調整
*/
// 要素をクリア
values[stack.start] = 0;
// start の位置を移動
stack.start = nextIndex(stack.start);
// シフト時に増やした容量を減らす
stack.capacity++;
}
// 他のスタックをシフトすることでスタックを拡張する
private void expand(int stackNum) {
shift((stackNum + 1) % info.length);
info[stackNum].capacity++;
}
// スタック上の現在の要素数を返す
public int numberOfElements() {
int size = 0;
for (StackInfo sd : info) {
size += sd.size;
}
return size;
}
// すべてのスタックが一杯の場合は true を返す
public boolean allStacksAreFull() {
return numberOfElements() == values.length;
}
// index を 0 から length - 1 の範囲内に調整する
private int adjustIndex(int index) {
/*
* Java の剰余演算子は負の値を返す
* たとえば (-11 % 5) は 4 ではなく -1 になる
* index が配列前部に回り込むようにしているため、実際には 4 になってほしい
*/
int max = values.length;
return ((index % max) + max) % max;
}
// この index の次の調整された index を得る
private int nextIndex(int index) {
return adjustIndex(index + 1);
}
// この index の前の調整された index を得る
private int previousIndex(int index) {
return adjustIndex(index - 1);
}
}
最小値を返すスタック
push と pop に加えて、
最小の要素を返す関数 min を持つスタックをデザインしてください。
push, pop, min 関数の実行時間は O(1) になるようにしてください。
答え
最小値はあまり頻繁に変化しません。
最小値が変化するのは「より小さい値が追加されたとき」だけです。
Stack クラスがメンバ変数 minValue で最小値を保持していればよいでしょう。
もし minValue が pop されたときは新たな最小値を探しましょう。
しかしこれでは実行時間 O(1) を満たすことができません。
- push(5)
- {5}
- 最小値は 5
- push(6)
- {6, 5}
- 最小値は 5
- push(3)
- {3, 6, 5}
- 最小値は 3
- push(7)
- {7, 3, 6, 5}
- 最小値は 3
- pop()
- 7 を pop
- {3, 6, 5}
- 最小値は 3
- pop()
- 3 を pop
- {6, 5}
- 最小値は 5
ノード追加するごとに、一番上のノードにその時点での最小値を持たせましょう。
最小値を調べたいときは、一番上のノードが管理する最小値を見るだけです。
public class StackWithMin extends Stack<NodeWithMin> {
// Java の Stack クラスの push メソッドをオーバーライド
public void push(int value) {
// 最小値を検索
int newMin = Math.min(value, min());
super.push(new NodeWithMin(value, newMin));
}
public int min() {
if (this.isEmpty()) {
// エラー値
return Integer.MAX_VALUE;
} else {
// 一番上の NodeWithMin の min が返ってくる
return peek().min;
}
}
}
class NodeWithMin {
public int value;
public int min;
// コンストラクタ
public NodeWithMin(int v, int min) {
value = v;
this.min = min;
}
}
各ノード要素が最小値を管理しています。
これでもよいのですが、スタックが大きくなるとメモリ消費が大きくなってしまいます。
スタックのサイズが n とすれば、整数値を n 個も保持しないといけません。
ここで元のスタックの中に「最小値を保持するスタック」も持たせてみましょう。
これでメモリ消費量をいくらか改善できます。
public class StackWithMin2 extends Stack<Integer> {
Stack<Integer> s2;
// コンストラクタ
public StackWithMin2() {
// 最小値を保持するスタック
s2 = new Stack<Integer>();
}
// Java の Stack クラスの push メソッドをオーバーライド
public void push(int value) {
// 追加する値が最小値じゃなければ管理する必要がない
if (value <= min()) {
// 最小値を保持するスタックに最小値を追加する
s2.push(value);
}
// 元のスタックに値を追加する
super.push(value);
}
// Java の Stack クラスの pop メソッドをオーバーライド
public Integer pop() {
// 元のスタックから値を取り出す
int value = super.pop();
if (value == min()) {
// 最小値を保持するスタックから最小値を取り出す
s2.pop();
}
return value;
}
public int min() {
if (s2.isEmpty()) {
// エラー値
return Integer.MAX_VALUE;
} else {
// 最小値を返却する
return s2.peek();
}
}
}
積み上がっている皿
皿が積み上がっている状況をイメージしてください。
もし、高く積み上がり過ぎたら倒れてしまうでしょう。
スタックの場合もある領域を超えたら新しい領域を用意した方が安全なので、
データ構造 SetOfStacks を実装することにします。
SetOfStacks はいくつかのスタックを持ち、
スタックのデータが一杯になったら新たにスタックを作ります。
SetOfStacks.push() と SetOfStacks.pop() は通常の単一スタックのようにふるまってください。
また、任意の部分スタックから pop する popAt(int, index) も実装してください。
答え
class SetsOfStacks {
// index が大きくなるほど新しいスタックに近づく
ArrayList<Stack> stacks = new ArrayList<Stack>();
public int capacity;
// コンストラクタ
public SetsOfStacks(int capacity) {
this.capacity = capacity;
}
/*
* 配列から最後のスタックを取り出す
*/
public getLastStack() {
if (stacks.size == 0) {
return null;
}
return stacks.get(stacks.size() - 1);
}
/*
* スタックを保持する配列の「最後のスタック」に対して push する
* ただしそのスタックが一杯の場合、新たにスタックを生成する
*/
public void push(int v) {
Stack last = getLastStack();
// 最後のスタックに追加する
if (last != null && !last.isFull()) {
last.push(v);
// 新しいスタックを作成して、配列に追加する
} else {
Stack stack = new Stack(capacity);
stack.push(v);
stacks.add(stack);
}
}
/*
* スタックを保持する配列の「最後のスタック」に対して pop する
* 取り出した結果、そのスタックが空になった場合、リストからそのスタックを削除する
*/
public int pop() {
Stack last = getLastStack();
if (last == null) {
throw new EmptyStackException();
}
int v = last.pop();
if (last.size == 0) {
stacks.remove(stacks.size() - 1);
}
return v;
}
public boolean isEmpty() {
Stack last = getLastStack();
return last == null || last.isEmpty();
}
/*
* 繰り越しシステム
* スタック[0] (もっとも古いスタック) 〜 スタック[3] (もっとも新しいスタック) があって、
* スタック[0] を pop した場合
* -> スタック[0]の一番上を削除して、その値が最終的に pop で返却される
* -> スタック[1]の一番下を削除して、その値はスタック[0]の一番上に push する
* -> スタック[2]の一番下を削除して、その値はスタック[1]の一番上に push する
* -> スタック[3]の一番下を削除して、その値はスタック[2]の一番上に push する
* 最終的にスタック[3] の size だけ 1 減少する
*/
public int popAt(int index) {
return leftShift(index, true);
}
public int leftShift(int index, boolean removeTop) {
Stack stack = stacks.get(index);
int removed_item;
if (removeTop) {
removed_item = stack.pop();
} else {
removed_item = stack.removeBottom();
}
if (stack.isEmpty()) {
stacks.remove(index);
} else if (stacks.size() > index + 1) {
// 次の index で再起実行: あるスタックの一番下が削除される
int v = leftShift(index + 1, false);
// 削除された一番下を、追加する
stack.push(v);
}
return removed_item;
}
}
public class Stack {
private int capacity;
public Node top, bottom;
public int size = 0;
// コンストラクタ
public Stack(int capacity) {
this.capacity = capacity;
}
public boolean isFull() {
return capacity == size;
}
public void join (Node above, Node below) {
if (below != null) {
below.above = above;
}
if (above != null) {
above.below = below;
}
}
public boolean push(int v) {
if (size >= capacity) {
return false;
}
size++;
Node n = new Node(v);
if (size == 1) {
bottom = n;
}
join(n, top);
top = n;
return true;
}
public int pop() {
Node t = top;
top - top.below;
size--;
return t.value;
}
public boolean isEmpty() {
return size == 0;
}
public int removeBottom() {
Node b = bottom;
bottom = bottom.above;
if (bottom != null) {
bottom.below = null;
}
size--;
return b.value;
}
}
スタックでキュー
MyQueue というクラス名で 2 つのスタックを用いてキューを実装してください。
答え
- キュー
- 先入れ先出し
- スタック
- 後入れ先出し
キュートとスタックはこの違いがあるので peek()と pop() の順序を逆にする必要があります。
2 つ目のスタックは要素をが逆順に並び替えるために使います。
スタック 1 から pop した要素はスタック 2 へ push すればよいでしょう。
しかし、このような実装では peek() や pop() を呼び出すたびに、
すべての要素をスタック 1 からスタック 2 へ pop() と push() しないといけなくなります。
不必要な要素移動は避けるべきです。
なので「本当に必要になるまで、スタック 2 に要素を入れたままにする」遅延評価をしておきます。
public class MyQueue<T> {
Stack<T> stackNewest, stackOldest;
// コンストラクタ
public MyQueue() {
// top に最も新しい要素を持たせる Stack
stackNewest = new Stack<T>();
// top に最も古い要素を持たせる Stack
stackOldest = new Stack<T>();
}
public int size() {
return stackNewest.size() + stackOldest.size();
}
/*
* stackNewest に要素を追加する
* このスタックでは新しい要素が一番上にくる
*/
public void add(T value) {
stackNewest.push(value);
}
/*
* stackNewest の要素を stackOldest に移す
* 通常、stackOldest に対する操作を行えるようにするために実行される
*/
private void shiftStacks() {
// もし stackOldest が空っぽの場合
if (stackOldest.isEmpry()) {
// stackNewest すべての要素から逆順に移動させる
while (!stackNewest.isEmpry) {
stackOldest.push(stackNewest.pop());
}
}
}
/*
* キューとして最も古い要素を取得する
*/
public T peek() {
// stackOldest に要素が移されている状態にする
shiftStacks();
return stackOldest.peek();
}
/*
* キューとして最も古い要素を取り除く
*/
public T remove() {
// stackOldest に要素が移されている状態にする
shiftStacks();
return stackOldest.pop();
}
}
スタックのソート
最も小さい項目がトップにくるスタックを並べ替えるプログラムを書いてください。
別のスタックを 1 つ用意しても構いません。
配列など、スタック以外のデータ構造にスタック上のデータをコピーしてはいけません。
またスタックは以下の操作のみ仕様できます。
- push
- pop
- peek
- isEmpty
答え
スタックを 3 つ使う場合
基本的なソーティングアルゴリズムを考えることになります。
その時点のスタック全体の最大値を見つけて、新しいスタックに push していきます。
これには 3 つのスタック s1, s2, s3 が必要です。
元のスタックを s1 として、
ソート済みのスタックを s2 としましょう。
s1 から最大値を探す際、s1 から pop した要素を s3 に push します。
このようにバッファとして s3 を使いましょう。
スタックを 2 つ使う場合
繰り返し最小値を探す代わりに、s1 の要素を s2 に挿入する形でソート可能です。
元のスタックを s1 として、
ソート済みのスタックを s2 としましょう。
| s1 | s2 |
|---|---|
| 12 | |
| 5 | 8 |
| 10 | 3 |
| 7 | 1 |
s1 の 5 を pop して s2 の 「 3 と 8 の間」に挿入したい。
| s1 | s2 |
|---|---|
| 12 | |
| 8 | |
| 10 | 3 |
| 7 | 1 |
まず s1 を pop して一時変数 tmp に 5 を保存する。
| s1 | s2 |
|---|---|
| 8 | |
| 12 | |
| 10 | 3 |
| 7 | 1 |
tmp = 5 を保持したまま、s2 の 8, 12 を pop して s1 にpush する。
| s1 | s2 |
|---|---|
| 8 | |
| 12 | 5 |
| 10 | 3 |
| 7 | 1 |
tmp = 5 を s2 に push すると、s1 の最小値 5 が s2 の top にくる。
| s1 | s2 |
|---|---|
| 12 | |
| 8 | |
| 5 | |
| 10 | 3 |
| 7 | 1 |
s1 の 8, 12 を pop して s2 に push する。
すると、s1 の 5 を pop して s2 の 「 3 と 8 の間」に挿入できました。
s1 の 10 と 7 も同じ要領で挿入していけば大丈夫です。
void sort(Stack<Integer> s) {
Stack<Integer> r = new Stack<Integer>();
/*
* s の各要素をソート順で r に挿入する
*/
while(!s.isEmpty()) {
int tmp = s.pop();
while(!r.isEmpty() && r.peek() < tmp) {
s.push(r.pop());
}
r.push(tmp);
}
/*
* 要素を r から s に戻す (小さい順になる)
*/
while(!r.isEmpty()) {
s.push(r.pop());
}
}
このアルゴリズムの計算時間は O(N^2) で、消費メモリは O(N) になります。
スタック容量が無制限ならクイックソート・マージソートに変形することもできます。
その場合、再起の深さごとに 2 つのスタックを追加する必要がある点に注意してください。
マージソートを利用する方法
追加のスタックを 2 つ作り、元のスタックを 2 つに分けます。
各スタックで再帰的にソートを行い、ソート順になるように元のスタックにマージします。
クイックソートを利用する方法
追加のスタックを 2 つ作り、元のスタックを「ピボットの値によって」 2 つに分けます。
各スタックは再帰的にソートを行い、ソート順になるように元のスタックにマージします。
動物保護施設
イヌとネコしか入ることのできない動物保護施設があります。
この施設は「先入れ先出し」の操作を厳密に行います。
施設からは一番長い時間入っている動物を外に出すか、
イヌとネコの好きなほう (で一番長い時間入っているもの) を外に出すことができます。
つまり、どの動物でも好きなように連れ出せるわけではありません。
このような仕組みを扱う構造を作ってください。
さらに enqueue(), dequeueAny(), dequeueDog(), dequeueCat() の操作を実装してください。
あらかじめ用意された連結リストのデータ構造は用いてよいものとします。
答え
単一のキューだけを持つ場合、dequeAny() は簡単に実装できます。
しかし dequeueDog(), dequeueCat() で最初の dog, cat を見つける処理が必要になります。
これは計算量が大きくなり、非効率な結果となります。
よって dog と cat それぞれのキューを用意するのがよいでしょう。
AnimalQueue というラッパークラスに入れてしまいましょう。
dog や cat が追加されたとき、タイムスタンプを並べて記録しておきます。dequeuAny() を呼び出すときは dog キューと cat キュー両方の先頭を調べて、古い方を返します。
abstract class Animal {
private int order;
protected String name;
// コンストラクタ
public Animal(String n) {
name = n;
}
public void setOrder(int ord) {
order = ord;
}
public int getOrder() {
return order;
}
// より古い要素を返すために動物の順序を比較する
public boolean isOlderThan(Animal a) {
return this.order < a.getOrder();
}
}
// ラッパークラス
class AnimalQueue {
LinkedList<Dog> dogs = new LinkedList<Dog>();
LinkedList<Cat> cats = new LinkedList<Cat>();
// タイムスタンプとして機能する
private int order = 0;
/*
* order をタイムスタンプとして使い、
* イヌとネコの挿入順序を比較できるようにする
*/
public void enqueue(Animal a) {
a.setOrder(order);
order++;
if (a instanceof Dog) {
dogs.addLast((Dog) a);
} else if (a instanceof Cat) {
cats.addLast((Cat) a);
}
}
/*
* イヌとネコのキューの一番上を比較し、古い方を取り出す
* Animal クラスを継承しておき、Dog クラス、Cat クラス両方のクラスを返却する
*/
public Animal dequeueAny() {
if (dogs.size() == 0) {
return dequeueCats();
} else if (cats.size() == 0) {
return dequeueDogs();
}
Dog dog = dogs.peek();
Cat cat = cats.peek();
if (dog.isOlderThan(cat)) {
return dequeueDogs();
} else {
return dequeueCats();
}
}
public Dog dequeueDogs() {
return dogs.poll();
}
public Cat dequeueCats() {
return cats.poll();
}
}
public class Dog extends Animal {
// コンストラクタ
public Dog(String n) {
super(n)
}
}
public class Cat extends Animal {
// コンストラクタ
public Cat(String n) {
super(n)
}
}
順序は番号管理じゃなく、実際の日時によるタイムスタンプの方が好ましいでしょう。
もし 2 つの動物が同じタイムスタンプになってしまった場合、
動物の順序はつけずにどちらか一方を返すようにしてもかまいません。
CS シリーズ
次回
前回
お仕事ください！
僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。 なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。
カテゴリ「CS」の最新記事
【ロードマップ】文系の元ラーメン屋が学んだコンピュータサイエンス 
【データ構造】「木とグラフ・探索アルゴリズム」をわかりやすく解説 
【データ構造】連結リスト・ランナーテクニックを解説！【頻出問題】 
【データ構造】面談対策！文字列・配列の問題解説【ハッシュテーブル】 
AnsibleでUbuntuにLaravel環境を構築するサンプル 
TerraformによるLinodeインスタンス新規作成サンプル 
【Fingerprint】CircleCIがSSHできない問題解決 
【Laravel】セッションタイムアウト後のログイン処理で前回URLに遷移するバグ修正 
M1 Mac(2021)でanyenv/phpenvの初期設定！ 
コメント