如何仅用递归函数和栈操作逆序一个栈

如何仅用递归函数和栈操作逆序一个栈

【题目】

一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

【难度】

尉　★★☆☆

【解答】

本题考查栈的操作和递归函数的设计，我们需要设计出两个递归函数。

递归函数一：将栈stack的栈底元素返回并移除。

具体过程就是如下代码中的getAndRemoveLastElement方法。

public static int getAndRemoveLastElement(Stackstack) { int result = stack.pop(); if (stack.isEmpty()) { return result; } else { int last = getAndRemoveLastElement(stack); stack.push(result); return last; } }

如果从stack的栈顶到栈底依次为3、2、1，这个函数的具体过程如图1-4所示。

图1-4

递归函数二：逆序一个栈，就是题目要求实现的方法，具体过程就是如下代码中的reverse方法。该方法使用了上面提到的getAndRemoveLastElement方法。

public static void reverse(Stackstack) { if (stack.isEmpty()) { return; } int i = getAndRemoveLastElement(stack); reverse(stack); stack.push(i); }

如果从stack的栈顶到栈底依次为3、2、1，reverse函数的具体过程如图1-5所示。

图1-5

getAndRemoveLastElement方法在图中简单表示为get方法，表示移除并返回当前栈底元素。

猫狗队列

【题目】

宠物、狗和猫的类如下：

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类改写，加一个计数项来表示某一个实例进队列的时间。