よくあるスタック、キュー面接問題

この文章のテーマはすべてCracking the Code Interview 2 nd Editionに整理されている.スタックとキューは一般的に面接問題の中で単独で問題全体として現れることはなく、補助的なデータ構造としてスタックとキューの性質を利用してある問題を解決することが多い.
スタックスタックStackの特徴は、先進的な後出、LIFO.スタックの基本操作:pushスタック、popスタック、peekスタックトップ要素を返しますが、スタックは変わりません.
スタックとキューの要素はin Javaを実現し、ここで使用するモデルです.Javaのモデルとは何か分からない場合は、この記事を参照してください.http://blog.csdn.net/explorers/article/details/454837

public class Node {
	
	public T data;
	public Node next;
	
}

スタックの簡単な実装in Java:

public class Stack {
	Node top;

	public void push(T data) {
		Node item = new Node();
		item.data = data;
		item.next = top;
		top = item;
	}

	public Node pop() {
		if (top == null) {
			return null;
		} else {
			Node item = top;
			top = top.next;
			return item;
		}
	}

	public Node peek() {
		return top;
	}
}

キューQueueの特徴は、先進先出、FIFO.キューの基本操作:enqueueがキューに入り、dequeueがキューから出ます.割り込まないように気をつけてthe_queue.最近夏休みに帰国して买い物をする时、いつも人に割り込まれて大変でした.
キューの簡単な実装in Java:

public class Queue {
	private Node first, last;

	public void enqueue(T data) {
		Node item = new Node();
		item.data = data;
		if (first == null) {
			last = item;
			first = item;
		} else {
			last.next = item;
			last = item;
		}
	}

	public Node dequeue() {
		if (first == null) {
			return null;
		} else {
			Node item = first;
			first = first.next;
			return item;
		}
	}
}

1. How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push,pop and min should all operate in O(1)time.は定数時間でスタックの挿入,削除,および最小値を返す動作を実現する.
出典:Cracking the Coding Interview 2 nd Edition Charpter 3 Question 2.
【解答】:スタックの挿入と削除操作は定数時間で完了できますが、このmin()関数をどのように設計しますか?最も直感的な考え方は,この最小値を新しいfieldで保存し,pushのたびにこの最小値をチェックすることである.しかし、問題はpopの時、どのようにpopが最小値を出すのかということです.では、最小値を再選択し、O(1)時間にこの新しい最小値を見つけるにはどうすればいいのでしょうか.
ここではstack:s 2を再構築し、これまでの位置でスタック操作のたびに得られた最小値を保存する方法を示す.元のスタックがpopによって最小値であると、s 2もpop動作を実行する.
解答のJava実装:http://pastebin.com/ivRpMT8Y ここでのstackはjdk utilパッケージの下のStackから継承される.
2.Implement a MyQueue class which implements a queue using two stacks.2つのスタックで1つのキューMyClassを実現します.
出典:Cracking the Coding Interview 2 nd Edition Charpter 3 Question 5.
【解答】:スタックの特徴:LIFO、キューはFIFO、つまりスタックに押し込まれた要素が底から上がるスタックがあれば、キューを満たす場合.では考えられる方法は、stackを反転することです.ここで2つのstackは、push用の新しい要素をnewStackと呼び、もう1つはoldStackと呼ばれる反転した要素を格納します.enqueue操作のたびにnewStackに格納され、dequeueがoldStackからpopされる.oldStackが空の場合、newStackの要素をoldStackに反転して格納します.
また、1つのqueueに関する基本API、enqueue()、dequeue()、size()、isEmpty()などについて注意するが、大まかな考え方は間違いなく、特にenqueueとdequeue操作である.
実装in Java:http://pastebin.com/WkFzrh8Z ここでのstackはjdk utilパッケージの下のStackから継承される.