第一章：栈和队列（二）

猫狗队列

【题目】

宠物、狗和猫的类如下：

	public class Pet {
		private String type;

		public Pet(String type) {
			this.type = type;
		}

		public String getPetType() {
			return this.type;
		}
	}

	public class Dog extends Pet {
		public Dog() {
			super("dog");
		}
	}

	public class Cat extends Pet {
		public Cat() {
			super("cat");
		}
	}

实现一种狗猫队列的结构，要求如下：

— 用户可以调用add方法将cat类或dog类的实例放入队列中；

— 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；

— 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；

— 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；

— 用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；

— 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；

— 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

【难度】

士     ★☆☆☆

【解答】

本题考查实现特殊数据结构的能力以及针对特殊功能的算法设计能力。

本题为开放类型的面试题，希望读者能有自己的实现，在这里列出几种常见的设计错误：

— cat队列只放cat实例，dog队列只放dog实例，再用一个总队列放所有的实例。

错误原因：cat、dog以及总队列的更新问题。

— 用哈希表，key表示一个cat实例或dog实例，value表示这个实例进队列的次序。

错误原因：不能支持一个实例多次进队列的功能需求，因为哈希表的key只能对应一个value值。

— 将用户原有的cat或dog类改写，加一个计数项来表示某一个实例进队列的时间。

错误原因：不能擅自改变用户的类结构。

	public class PetEnterQueue {
		private Pet pet;
		private long count;

		public PetEnterQueue(Pet pet, long count) {
			this.pet = pet;
			this.count = count;
		}

		public Pet getPet() {
			return this.pet;
		}

		public long getCount() {
			return this.count;
		}

		public String getEnterPetType() {
			return this.pet.getPetType();
		}
	}

在构造PetEnterQueue类时，pet是用户原有的实例，count就是这个实例的时间戳。

我们实现的队列其实是PetEnterQueue类的实例。大体说来，首先有一个不断累加的数据项，用来表示实例进队列的时间；同时有两个队列，一个是只放dog类实例的队列dogQ，另一个是只放cat类实例的队列catQ。

在加入实例时，如果实例是dog，就盖上时间戳，生成对应的PetEnterQueue类的实例，然后放入dogQ；如果实例是cat，就盖上时间戳，生成对应的PetEnterQueue类的实例，然后放入catQ。具体过程请参看如下DogCatQueue类的add方法。

只想弹出dog类的实例时，从dogQ里不断弹出即可，具体过程请参看如下DogCatQueue类的pollDog方法。

只想弹出cat类的实例时，从catQ里不断弹出即可，具体过程请参看如下DogCatQueue类的pollCat方法。

想按实际顺序弹出实例时，因为dogQ的队列头表示所有dog实例中最早进队列的实例，同时catQ的队列头表示所有的cat实例中最早进队列的实例。则比较这两个队列头的时间戳，谁更早，就弹出谁。具体过程请参看如下DogCatQueue类的pollAll方法。

	public class DogCatQueue {
		private Queue<PetEnterQueue> dogQ;
		private Queue<PetEnterQueue> catQ;
		private long count;

		public DogCatQueue() {
			this.dogQ = new LinkedList<PetEnterQueue>();
			this.catQ = new LinkedList<PetEnterQueue>();
			this.count = 0;
		}

		public void add(Pet pet) {
			if (pet.getPetType().equals("dog")) {
				this.dogQ.add(new PetEnterQueue(pet, this.count++));
			} else if (pet.getPetType().equals("cat")) {
				this.catQ.add(new PetEnterQueue(pet, this.count++));
			} else {
				throw new RuntimeException("err, not dog&nbs***bsp;cat");
			}
		}

		public Pet pollAll() {
			if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
				if(this.dogQ.peek().getCount() < this.catQ.peek().Get Count()) {
					return this.dogQ.poll().getPet();
				} else {
					return this.catQ.poll().getPet();
				}
			} else if (!this.dogQ.isEmpty()) {
				return this.dogQ.poll().getPet();
			} else if (!this.catQ.isEmpty()) {
				return this.catQ.poll().getPet();
			} else {
				throw new RuntimeException("err, queue is empty!");
			}
		}

		public Dog pollDog() {
			if (!this.isDogQueueEmpty()) {
				return (Dog) this.dogQ.poll().getPet();
			} else {
				throw new RuntimeException("Dog queue is empty!");
			}
		}

		public Cat pollCat() {
			if (!this.isCatQueueEmpty()) {
				return (Cat) this.catQ.poll().getPet();
			} else
				throw new RuntimeException("Cat queue is empty!");
		}

		public boolean isEmpty() {
			return this.dogQ.isEmpty() && this.catQ.isEmpty();
		}

		public boolean isDogQueueEmpty() {
			return this.dogQ.isEmpty();
		}

		public boolean isCatQueueEmpty() {
			return this.catQ.isEmpty();
		}

	}

用一个栈实现另一个栈的排序

【题目】

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

【难度】

士     ★☆☆☆

【解答】

将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。

— 如果cur小于或等于help的栈顶元素，则将cur直接压入help；

— 如果cur大于help的栈顶元素，则将help的元素逐一弹出，逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。

	public static void sortStackByStack(Stack<Integer> stack) {
		Stack<Integer> help = new Stack<Integer>();
		while (!stack.isEmpty()) {
			int cur = stack.pop();
			while (!help.isEmpty() && help.peek() < cur) {
				stack.push(help.pop());
			}
			help.push(cur);
		}
		while (!help.isEmpty()) {
			stack.push(help.pop());
		}
	}

用栈来求解汉诺塔问题

【题目】

汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。

例如，当塔数为两层时，最上层的塔记为1，最下层的塔记为2，则打印：

Move 1 from left to mid

Move 1 from mid to right

Move 2 from left to mid

Move 1 from right to mid

Move 1 from mid to left

Move 2 from mid to right

Move 1 from left to mid

Move 1 from mid to right

It will move 8 steps.

注意：关于汉诺塔游戏的更多讨论，将在本书递归与动态规划的章节中继续。

【要求】

用以下两种方法解决。

— 方法一：递归的方法；

— 方法二：非递归的方法，用栈来模拟汉诺塔的三个塔。

【难度】

校     ★★★☆

【解答】

方法一：递归的方法。

首先，如果只剩最上层的塔需要移动，则有如下处理：

1．如果希望从“左”移到“中”，打印“Move 1 from left to mid”。

2．如果希望从“中”移到“左”，打印“Move 1 from mid to left”。

3．如果希望从“中”移到“右”，打印“Move 1 from mid to right”。

4．如果希望从“右”移到“中”，打印“Move 1 from right to mid”。

5．如果希望从“左”移到“右”，打印“Move 1 from left to mid”和“Move 1 from mid to right”。

6．如果希望从“右”移到“左”，打印“Move 1 from right to mid”和“Move 1 from mid to left”。

以上过程就是递归的终止条件，也就是只剩上层塔时的打印过程。

接下来，我们分析剩下多层塔的情况。

如果剩下N层塔，从最上到最下依次为1~N，则有如下判断：

1．如果剩下的N层塔都在“左”，希望全部移到“中”，则有三个步骤。

1）将1~N-1层塔先全部从“左”移到“右”，明显交给递归过程。

2）将第N层塔从“左”移到“中”。

3）再将1~N-1层塔全部从“右”移到“中”，明显交给递归过程。

2．如果把剩下的N层塔从“中”移到“左”，从“中”移到“右”，从“右”移到“中”，过程与情况1同理，一样是分解为三步，在此不再详述。

3．如果剩下的N层塔都在“左”，希望全部移到“右”，则有五个步骤。

1）将1~N-1层塔先全部从“左”移到“右”，明显交给递归过程。

2）将第N层塔从“左”移到“中”。

3）将1~N-1层塔全部从“右”移到“左”，明显交给递归过程。

4）将第N层塔从“中”移到“右”。

5）将1~N-1层塔全部从“左”移到“右”，明显交给递归过程。

4．如果剩下的N层塔都在“右”，希望全部移到“左”，过程与情况3同理，一样是分解为五步，在此不再详述。

	public int hanoiProblem1(int num, String left, String mid,
			String right) {
		if (num < 1) {
			return 0;
		}
		return process(num, left, mid, right, left, right);
	}

	public int process(int num, String left, String mid, String right,
			String from, String to) {
		if (num == 1) {
			if (from.equals(mid) || to.equals(mid)) {
				System.out.println("Move 1 from " + from + " to " + to);
				return 1;
			} else {
				System.out.println("Move 1 from " + from + " to " + mid);
				System.out.println("Move 1 from " + mid + " to " + to);
				return 2;
			}
		}
		if (from.equals(mid) || to.equals(mid)) {
			String another = (from.equals(left) || to.equals(left)) ? right : left;
			int part1 = process(num - 1, left, mid, right, from, another);
			int part2 = 1;
			System.out.println("Move " + num + " from " + from + " to " + to);
			int part3 = process(num - 1, left, mid, right, another, to);
			return part1 + part2 + part3;
		} else {
			int part1 = process(num - 1, left, mid, right, from, to);
			int part2 = 1;
			System.out.println("Move " + num + " from " + from + " to " + mid);
			int part3 = process(num - 1, left, mid, right, to, from);
			int part4 = 1;
			System.out.println("Move " + num + " from " + mid + " to " + to);
			int part5 = process(num - 1, left, mid, right, from, to);
			return part1 + part2 + part3 + part4 + part5;
		}
	}

方法二：非递归的方法——用栈来模拟整个过程。

修改后的汉诺塔问题不能让任何塔从“左”直接移动到“右”，也不能从“右”直接移动到“左”，而是要经过中间过程。也就是说，实际动作只有4个：“左”到“中”、“中”到“左”、“中”到“右”、“右”到“中”。

现在我们把左、中、右三个地点抽象成栈，依次记为LS、MS和RS。最初所有的塔都在LS上。那么如上4个动作就可以看作是：某一个栈（from）把栈顶元素弹出，然后压入到另一个栈里（to），作为这一个栈（to）的栈顶。

例如，如果是7层塔，在最初时所有的塔都在LS上，LS从栈顶到栈底就依次是1~7，如果现在发生了“左”到“中”的动作，这个动作对应的操作是LS栈将栈顶元素1弹出，然后1压入到MS栈中，成为MS的栈顶。其他操作同理。

一个动作能发生的先决条件是不违反小压大的原则。

from栈弹出的元素num如果想压入到to栈中，那么num的值必须小于当前to栈的栈顶。

还有一个原则不是很明显，但也是非常重要的，叫相邻不可逆原则，解释如下：

1．我们把4个动作依次定义为：L->M、M->L、M->R和R->M。

2．很明显，L->M和M->L过程互为逆过程，M->R和R->M互为逆过程。

3．在修改后的汉诺塔游戏中，如果想走出最少步数，那么任何两个相邻的动作都不是互为逆过程的。举个例子：如果上一步的动作是L->M，那么这一步绝不可能是M->L，直观地解释为：你在上一步把一个栈顶数从“左”移动到“中”，这一步为什么又要移回去呢？这必然不是取得最小步数的走法。同理，M->R动作和R->M动作也不可能相邻发生。

有了小压大和相邻不可逆原则后，可以推导出两个十分有用的结论——非递归的方法核心结论：

1．游戏的第一个动作一定是L->M，这是显而易见的。

2．在走出最少步数过程中的任何时刻，4个动作中只有一个动作不违反小压大和相邻不可逆原则，另外三个动作一定都会违反。

对于结论2，现在进行简单的证明。

因为游戏的第一个动作已经确定是L->M，则以后的每一步都会有前一步的动作。

假设前一步的动作是L->M：

1．根据小压大原则，L->M的动作不会重复发生。

2．根据相邻不可逆原则，M->L的动作也不该发生。

3．根据小压大原则，M->R和R->M只会有一个达标。

假设前一步的动作是M->L：

1．根据小压大原则，M->L的动作不会重复发生。

2．根据相邻不可逆原则，L->M的动作也不该发生。

3．根据小压大原则，M->R和R->M只会有一个达标。

假设前一步的动作是M->R：

1．根据小压大原则，M->R的动作不会重复发生。

2．根据相邻不可逆原则，R->M的动作也不该发生。

3．根据小压大原则，L->M和M->L只会有一个达标。

假设前一步的动作是R->M：

1．根据小压大原则，R->M的动作不会重复发生。

2．根据相邻不可逆原则，M->R的动作也不该发生。

3．根据小压大原则，L->M和M->L只会有一个达标。

综上所述，每一步只会有一个动作达标。那么只要每走一步都根据这两个原则考查所有的动作就可以，哪个动作达标就走哪个动作，反正每次都只有一个动作满足要求，按顺序走下来即可。

	public enum Action {
		No, LToM, MToL, MToR, RToM
	}

	public int hanoiProblem2(int num, String left, String mid, String right) {
		Stack<Integer> lS = new Stack<Integer>();
		Stack<Integer> mS = new Stack<Integer>();
		Stack<Integer> rS = new Stack<Integer>();
		lS.push(Integer.MAX_VALUE);
		mS.push(Integer.MAX_VALUE);
		rS.push(Integer.MAX_VALUE);
		for (int i = num; i > 0; i--) {
			lS.push(i);
		}
		Action[] record = { Action.No };
		int step = 0;
		while (rS.size() != num + 1) {
			step += fStackTotStack(record, Action.MToL, Action.LToM, lS, mS, 
left, mid);
			step += fStackTotStack(record, Action.LToM, Action.MToL, mS, lS, 
mid, left);
			step += fStackTotStack(record, Action.RToM, Action.MToR, mS, rS, 
mid, right);
			step += fStackTotStack(record, Action.MToR, Action.RToM, rS, mS, 
right, mid);
		}
		return step;
	}

	public static int fStackTotStack(Action[] record, Action preNoAct,
			Action nowAct, Stack<Integer> fStack, Stack<Integer> tStack,
			String from, String to) {
		if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
			tStack.push(fStack.pop());
			System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
			record[0] = nowAct;
			return 1;
		}
		return 0;
	}

生成窗口最大值数组

【题目】

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

[4  3  5] 4  3  3  6  7        窗口中最大值为5

4 [3  5  4] 3  3  6  7        窗口中最大值为5

4  3 [5  4  3] 3  6  7        窗口中最大值为5

4  3  5 [4  3  3] 6  7        窗口中最大值为4

4  3  5  4 [3  3  6] 7        窗口中最大值为6

4  3  5  4  3 [3  6  7]        窗口中最大值为7

如果数组长度为n，窗口大小为w，则一***生n-w+1个窗口的最大值。

请实现一个函数。

— 输入：整型数组arr，窗口大小为w。

— 输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。

以本题为例，结果应该返回{5,5,5,4,6,7}。

【难度】

尉     ★★☆☆

【解答】

假设数组长度为N，窗口大小为w，如果做出时间复杂度为O(N×w)的解法是不能让面试官满意的，本题要求面试者想出时间复杂度为O(N)的实现。

本题的关键在于利用双端队列来实现窗口最大值的更新。首先生成双端队列qmax，qmax中存放数组arr中的下标。

假设遍历到arr[i]，qmax的放入规则为：

1．如果qmax为空，直接把下标i放进qmax，放入过程结束。

2．如果qmax不为空，取出当前qmax队尾存放的下标，假设为j。

1）如果arr[j]>arr[i]，直接把下标i放进qmax的队尾，放入过程结束。

2）如果arr[j]<=arr[i]，把j从qmax中弹出，重复qmax的放入规则。

也就是说，如果qmax是空的，就直接放入当前的位置。如果qmax不是空的，qmax队尾的位置所代表的值如果不比当前的值大，将一直弹出队尾的位置，直到qmax队尾的位置所代表的值比当前的值大，当前的位置才放入qmax的队尾。

假设遍历到arr[i]，qmax的弹出规则为：

如果qmax队头的下标等于i-w，说明当前qmax队头的下标已过期，弹出当前对头的下标即可。

根据如上的放入和弹出规则，qmax便成了一个维护窗口为w的子数组的最大值更新的结构。下面举例说明题目给出的例子。

1．开始时qmax为空，qmax={}。

2．遍历到arr[0]==4，将下标0放入qmax，qmax={0}。

3．遍历到arr[1]==3，当前qmax的队尾下标为0，又有arr[0]>arr[1]，所以将下标1放入qmax的尾部，qmax={0,1}。

4．遍历到arr[2]==5，当前qmax的队尾下标为1，又有arr[1]<=arr[2]，所以将下标1从qmax的尾部弹出，qmax变为{0}。当前qmax的队尾下标为0，又有arr[0]<=arr[2]，所以将下标0从qmax尾部弹出，qmax变为{}。将下标2放入qmax，qmax={2}。此时已经遍历到下标2的位置，窗口arr[0..2]出现，当前qmax队头的下标为2，所以窗口arr[0..2]的最大值为arr[2]（即5）。

5．遍历到arr[3]==4，当前qmax的队尾下标为2，又有arr[2]>arr[3]，所以将下标3放入qmax尾部，qmax={2,3}。窗口arr[1..3]出现，当前qmax队头的下标为2，这个下标还没有过期，所以窗口arr[1..3]的最大值为arr[2]（即5）。

6．遍历到arr[4]==3，当前qmax的队尾下标为3，又有arr[3]>arr[4]，所以将下标4放入qmax尾部，qmax={2,3,4}。窗口arr[2..4]出现，当前qmax队头的下标为2，这个下标还没有过期，所以窗口arr[2..4]的最大值为arr[2]（即5）。

7．遍历到arr[5]==3，当前qmax的队尾下标为4，又有arr[4]<=arr[5]，所以将下标4从qmax的尾部弹出，qmax变为{2,3}。当前qmax的队尾下标为3，又有arr[3]>arr[5]，所以将下标5放入qmax尾部，qmax={2,3,5}。窗口arr[3..5]出现，当前qmax队头的下标为2，这个下标已经过期，所以从qmax的头部弹出，qmax变为{3,5}。当前qmax队头的下标为3，这个下标没有过期，所以窗口arr[3..5]的最大值为arr[3]（即4）。

8．遍历到arr[6]==6，当前qmax的队尾下标为5，又有arr[5]<=arr[6]，所以将下标5从qmax的尾部弹出，qmax变为{3}。当前qmax的队尾下标为3，又有arr[3]<=arr[6]，所以将下标3从qmax的尾部弹出，qmax变为{}。将下标6放入qmax，qmax={6}。窗口arr[4..6]出现，当前qmax队头的下标为6，这个下标没有过期，所以窗口arr[4..6]的最大值为arr[6]（即6）。

9．遍历到arr[7]==7，当前qmax的队尾下标为6，又有arr[6]<=arr[7]，所以将下标6从qmax的尾部弹出，qmax变为{}。将下标7放入qmax，qmax={7}。窗口arr[5..7]出现，当前qmax队头的下标为7，这个下标没有过期，所以窗口arr[5..7]的最大值为arr[7]（即7）。

10．依次出现的窗口最大值为[5,5,5,4,6,7]，在遍历过程中收集起来，最后返回即可。

	public int[] getMaxWindow(int[] arr, int w) {
		if (arr == null || w < 1 || arr.length < w) {
			return null;
		}
		LinkedList<Integer> qmax = new LinkedList<Integer>();
		int[] res = new int[arr.length - w + 1];
		int index = 0;
		for (int i = 0; i < arr.length; i++) {
			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
				qmax.pollLast();
			}
			qmax.addLast(i);
			if (qmax.peekFirst() == i - w) {
				qmax.pollFirst();
			}
			if (i >= w - 1) {
				res[index++] = arr[qmax.peekFirst()];
			}
		}
		return res;
	}