不使用其他数据结构逆序一个栈

题目：不使用其他的数据结构反转一个栈。

来源：程序员代码面试指南  P8

题目就是这么的简洁，不准使用其他数据结构（栈、数组、队列啥的）逆序一个栈（原来【1,2,3,4】变成【4,3,2,1】）。

分析：题目限制了不能使用其他数据结构了，所以这里肯定要使用递归了（函数的递归调用本来就是一个栈嘛）。那么使用递归的大致代码（伪代码）如下：

void reverseStack(Stack<E> stack) { if (stack.isEmpty()) { return; } E item = ???; reverseStack(stack); stack.push(item); }

问题的关键就是上面的？？？应该是多少，显然我们这里是需要逆序一个栈，因此这里的？？？我们应该是要获取到栈底元素，这样最后一行再进行push操作，栈底元素就成了栈顶元素，就实现了栈的逆序了。

下面看代码：

public static <E> void reverseStack(Stack<E> stack) { if (stack.isEmpty()) { return; } E item = getLastStackElement(stack); reverseStack(stack); stack.push(item); } private static <E> E getLastStackElement(Stack<E> stack) { E item = stack.pop(); if (stack.isEmpty()) { return item; } else { E res = getLastStackElement(stack); stack.push(item); return res; } }

既然我们已经写了栈的逆序了，所幸就在写一个队列的逆序吧。思路还是一样的，但是队列的末尾元素（队头）我们可以直接获取，不用像栈那样还要需要递归来求得栈底元素了。

下面看不使用其它数据结构逆序一个队列的代码：

public static <E> void reverseQueue(Queue<E> queue) { if(queue.isEmpty()) { return; } E item = queue.poll(); reverseQueue(queue); queue.add(item); }

好了，我们下期见！