不能擅自改变用户的类结构

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

本题实现将不同的实例盖上时间戳的方法，但是又不能改变用户本身的类，所以定义一个新的类，具体实现请参看如下的PetEnterQueue类。

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方法。

DogCatQueue类的整体代码如下：

public class DogCatQueue { private QueuedogQ; private QueuecatQ; private long count; public DogCatQueue() { this.dogQ = new LinkedList(); this.catQ = new LinkedList(); 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 or 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。

一直执行以上操作，直到stack中的全部元素都压入到help。最后将help中的所有元素逐一压入stack，即完成排序。

public static void sortStackByStack(Stackstack) { Stackhelp = new Stack(); 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同理，一样是分解为五步，在此不再详述。

以上递归过程经过逻辑化简之后的代码请参看如下代码中的hanoiProblem1方法。

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; } }