1.描述如何只用一个数组来实现三个栈。
思路：将整个数组划分为三等份，将每个栈的增长限制在各自的空间里。
栈1， 使用【0，n/3）。 栈2，使用【n/3，2n/3）。 栈3，使用【2n/3 , n)。
public class ArrayStack { static int stackSize = 100; static int[] buffer = new int[stackSize * 3]; static int[] stackPointer = {-1, -1, -1}; public static void main(String[] args) throws Exception { // TODO Auto-generated method stub push(2, 4); System.out.println("Peek 2: " + peek(2)); push(0, 3); push(0, 7); push(0, 5); System.out.println("Peek 0: " + peek(0)); pop(0); System.out.println("Peek 0: " + peek(0)); pop(0); System.out.println("Peek 0: " + peek(0)); } //stackNum取值为0,1,2 分别代表三个栈 static void push(int stackNum, int value) throws Exception { //检查有无空闲空间 if (stackPointer[stackNum] + 1 >= stackSize) { throw new Exception("Out of space."); } //栈指针自增，然后更新栈顶元素的值 stackPointer[stackNum]++; buffer[absTopOfStack(stackNum)] = value; } static int pop(int stackNum) throws Exception { //检查栈是否为空 if (stackPointer[stackNum] == -1) { throw new Exception("Trying to pop an empty stack."); } //获取栈顶元素 int value = buffer[absTopOfStack(stackNum)]; //清零指定索引元素的值 buffer[absTopOfStack(stackNum)] = 0; //指针自减 stackPointer[stackNum]--; return value; } static int peek(int stackNum) { int index = absTopOfStack(stackNum); return buffer[index]; } static boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; } //返回栈"stackNum"栈顶元素的索引，绝对量 static int absTopOfStack(int stackNum) { return stackNum * stackSize + stackPointer[stackNum]; }} 2.请设计一个栈，除pop和push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为o(1)。
思路：入栈时不是最小值，永远都没有机会成为最小值。利用额外的栈minStack来记录每个元素入栈时当前的最小值。
import java.util.Stack;public class MinStack { private static Stack stack = new Stack (); private static Stack minStack = new Stack (); public static void main(String[] args) { // TODO Auto-generated method stub push(5); System.out.println("最小值: " + min()); push(6); push(3); push(7); System.out.println("最小值: " + min()); pop(); System.out.println("最小值: " + min()); pop(); System.out.println("最小值: " + min()); } public static void push(int value) { stack.push(value); if (!minStack.empty()) { int min = minStack.peek(); if (value <= min) { minStack.push(value); } } else { minStack.push(value); } } public static void pop() { if(minStack.size() != 0 && ((int)stack.peek() == (int)minStack.peek())) { minStack.pop(); } stack.pop(); } public static int top() { return (int)stack.peek(); } public static int min() { return (int)minStack.peek(); }} 3.设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
思路：push()的行为必须跟单一栈一样，意味着push()要对栈数组的最后一个栈调用push()。若最后一个栈被填满，就需新建一个栈。
pop()跟push()的行为类似，应该操作最后一个栈。若最后一个栈为空（执行出栈操作后），就必须从栈数组中移除这个栈。
Node.java
public class Node { public Node above; public Node below; public int value; public Node(int value) { this.value = value; }} Stack.java
public class Stack { private int capacity; public Node top; public Node bottom; public int size = 0; public Stack(int capacity) { this.capacity = capacity; } public boolean isFull() { return capacity == size; } public void join(Node above, Node below) { if (below != null) below.above = above; if (above != null) above.below = below; } public boolean push(int v) { if (size >= capacity) return false; size++; Node n = new Node(v); if (size == 1) bottom = n; join(n, top); top = n; return true; } public int pop() { Node t = top; top = top.below; size--; return t.value; } public boolean isEmpty() { return size == 0; } public int removeBottom() { Node b = bottom; bottom = bottom.above; if (bottom != null) bottom.below = null; size--; return b.value; }} SetOfStacks.java
import java.util.*;public class SetOfStacks { ArrayList stacks = new ArrayList (); public int capacity; public SetOfStacks(int capacity) { this.capacity = capacity; } public Stack getLastStack() { if (stacks.size() == 0) { return null; } return stacks.get(stacks.size() - 1); } //push要对栈数组的最后一个栈操作。若最后一个栈被填满，就需新建一个栈。 public void push(int v) { Stack last = getLastStack(); if (last != null && !last.isFull()) { last.push(v); } else { //新建一个栈 Stack stack = new Stack(capacity); stack.push(v); stacks.add(stack); } } //pop也应该操作栈数组中的最后一个栈。若最后一个栈为空（执行出栈操作后），从栈数组中移除这个栈。 public int pop() { Stack last = getLastStack(); int v = last.pop(); if (last.size == 0) { stacks.remove(stacks.size() - 1); } return v; } //进阶代码 /*public int popAt(int index) { return leftShift(index, true); } public int leftShift(int index, boolean removeTop) { Stack stack = stacks.get(index); int removed_item; if (removeTop) removed_item = stack.pop(); else removed_item = stack.removeBottom(); if (stack.isEmpty()) { stacks.remove(index); } else if (stacks.size() > index + 1) { int v = leftShift(index + 1, false); stack.push(v); } return removed_item; } public boolean isEmpty() { Stack last = getLastStack(); return last == null || last.isEmpty(); }*/} 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
思路：设想一个"推入"操作。从栈1弹出元素时，需要移出栈2的栈底元素，并将其推到栈1中。随后，将栈3的栈底元素推入栈2，将栈4的栈底元素推入栈3，等等。
4.在经典问题汉诺塔中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自底向上从大到小依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时有以下限制：
（1）每次只能移动一个盘子；
（2）盘子只能从柱子顶端滑出移到下一根柱子；
（3）盘子只能叠在比它大的盘子上。
请运用栈，编写程序将所有盘子从第一根柱子移到最后一根柱子。
思路：
（1）将顶端n-1个盘子从origin移至buffer，将destination用作缓冲区；
（2）将origin顶端的盘子移至destination；
（3）将顶部n-1个盘子从buffer移至destination，将origin用作缓冲区。
import java.util.Stack;class Tower { private Stack disks; private int index; public Tower(int i) { disks = new Stack (); index = i; } public int index() { return index; } public void add(int d) { //错误检查：要放入的盘子比当前顶端的盘子大 if (!disks.isEmpty() && disks.peek() <= d) { System.out.println("Error placing disk " + d); } else { disks.push(d); } } public void moveTopTo(Tower t) { int top = disks.pop(); t.add(top); System.out.println("Move disk " + top +" from " + index() + " to " + t.index()); } public void moveDisks(int n, Tower destination, Tower buffer) { if (n > 0) { //将顶端n-1个盘子从origin移至buffer，将destination用作缓冲区 moveDisks(n - 1, buffer, destination); //将origin顶端的盘子移至destination moveTopTo(destination); //将顶部n-1个盘子从buffer移至destination，将origin用作缓冲区 buffer.moveDisks(n - 1, destination, this); } }}public class TowerOfHanoi { public static void main(String[] args) { // TODO Auto-generated method stub //N个盘子 int n = 5; //初始化三根柱子 Tower[] towers = new Tower[3]; for (int i = 0; i < 3; i++) { towers[i] = new Tower(i); } //n个盘子在origin柱子上 for (int i = n - 1; i >= 0; i--) { towers[0].add(i); } //总体任务：以towers[1]为缓冲区，将n个盘子从towers[0]移到towers[2] towers[0].moveDisks(n, towers[2], towers[1]); }} 5.实现一个MyQueue类，该类用两个栈来实现一个队列。
思路：队列：先进先出 栈：先进后出
使用stackNewest和stackOldest两个栈，stackNewest顶端为最新元素，stackOldest顶端为最旧元素。在将一个元素出列时，我们希望先移除最旧元素，因此先将元素从stackOldest出列。若stackOldest为空，则将stackNewest中的所有元素以相反的顺序转移到stackOlest中。如要插入元素，就将其压入stackNewest，因为最新元素位于它的顶端。
import java.util.Stack;public class MyQueue { Stack stackNewest = new Stack (); Stack stackOldest = new Stack (); public int size() { return stackNewest.size() + stackOldest.size(); } public void add(int value) { //压入stackNewest,最新元素始终位于它的顶端 stackNewest.push(value); } //将元素从stackNewest移至stackOldest，这么做通常是为了要在stackOldest上执行操作 public void shiftStacks() { if (stackOldest.isEmpty()) { while (!stackNewest.isEmpty()) { stackOldest.push(stackNewest.pop()); } } } public int peek() { shiftStacks();//确保stackOldest含有当前元素 return stackOldest.peek();//取回最旧元素 } public int remove() { shiftStacks();//确保stackOldest含有当前元素 return stackOldest.pop();//弹出最旧元素 }} 6.编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。
思路：若要对s1进行排序，可以从s1中逐一弹出元素，然后按顺序插入s2中。算法的时间复杂度为o(N的平方),空间复杂度为o(N)。
public static Stacksort(Stack s) { Stack r = new Stack (); while (!s.isEmpty()) { int tmp = s.pop(); while (!r.isEmpty() && r.peek() > tmp) { s.push(r.pop()); } r.push(tmp); } return r; }
进阶：如果允许使用的栈数量不限，可以实现修改版的quicksort或mergesort。
对于mergesort解法，可以再创建两个栈，并将这个栈分为两部分。递归排序每个栈，然后将它们归并到一起并排好序放回原来的栈中。注意，该解法要求每层递归都创建两个额外的栈。
对于quicksort解法，创建两个额外的栈，并根据基准元素将这个栈分为两个栈。这两个栈会进行递归排序，然后归并在一起放回原来的栈中。注意，该解法要求每层递归都创建两个额外的栈。
7.有家动物收容所只收容狗和猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”(根据进入收容所的时间长短）的动物，或者，可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat等。允许使用Java内置的LinkedList数据结构。
思路：为猫和狗各自创建一个队列，然后将两者放进名为AnimalQueue的包裹类，并且存储某种形式的时戳，以标记每只动物进入队列的时间。当调用dequeueAny时，查看狗队列和猫队列的首部，并返回“最老”的那一只。
Animal.java
//一旦类中包含了abstract方法，那该类必须声明为abstract类。public abstract class Animal { private int order; protected String name; public Animal(String n) { name = n; } //定义成抽象方法，来解决父类方法的不确定性。抽象方法在父类中不能实现，所以没有函数体。但在后续继承时，要具体实现此方法。 public abstract String name(); public void setOrder(int ord) { order = ord; } public int getOrder() { return order; } public boolean isOlderThan(Animal a) { return this.order < a.getOrder(); }} AnimalQueue.java
import java.util.LinkedList;// 抽象类可以被继承，当继承的父类是抽象类时，需要将抽象类中的所有抽象方法(本题中为name())全部实现class Dog extends Animal { public Dog(String n) { super(n);//super()调用父类中有相同形参的构造方法 } public String name() { return "Dog: " + name; }}class Cat extends Animal { public Cat(String n) { super(n); } public String name() { return "Cat: " + name; }}public class AnimalQueue { LinkedList dogs = new LinkedList (); LinkedList cats = new LinkedList (); private int order = 0;//用作时戳 public void enqueue(Animal a) { //order用作某种形式的时间戳，以便比较狗或猫插入队列的先后顺序 a.setOrder(order); order++; if (a instanceof Dog) { dogs.addLast((Dog) a); } else if (a instanceof Cat) { cats.addLast((Cat) a); } } public Animal dequeueAny() { //查看猫和狗的队列首部，弹出最旧的值 if (dogs.size() == 0) { return dequeueCats(); } else if (cats.size() == 0) { return dequeueDogs(); } Dog dog = dogs.peek(); Cat cat = cats.peek(); if (dog.isOlderThan(cat)) { return dogs.poll(); } else { return cats.poll(); } } public Animal peek() { if (dogs.size() == 0) { return cats.peek(); } else if (cats.size() == 0) { return dogs.peek(); } Dog dog = dogs.peek(); Cat cat = cats.peek(); if (dog.isOlderThan(cat)) { return dog; } else { return cat; } } public int size() { return dogs.size() + cats.size(); } public Dog dequeueDogs() { return dogs.poll(); } public Dog peekDogs() { return dogs.peek(); } public Cat dequeueCats() { return cats.poll(); } public Cat peekCats() { return cats.peek(); }} 8.请实现一种数据结构SetOfStacks，由多个栈组成，其中每个栈的大小为size，当前一个栈填满时，新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。 给定一个操作序列int[][2] ope(C++为vector<vector<int>>)，每个操作的第一个数代表操作类型，若为1，则为push操作，后一个数为应push的数字；若为2，则为pop操作，后一个数无意义。请返回一个int[][](C++为vector<vector<int>>)，为完成所有操作后的SetOfStacks，顺序应为从下到上，默认初始的SetOfStacks为空。保证数据合法。
import java.util.*;public class SetOfStacks { public static ArrayList > setOfStacks(int[][] ope, int size) { // write code here ArrayList > res = new ArrayList >(); ArrayList list = new ArrayList (); res.add(list);//初始的SetOfStacks(也即res)为空 if(ope.length == 0) return res; for(int i = 0; i < ope.length; i++){ ArrayList tmp = null; if (ope[i][0] == 1) { //push操作 if(res.get(res.size() - 1).size() == size){ //要操作的最后一个栈满，新建一个栈 tmp = new ArrayList (); } else { tmp = res.get(res.size() - 1); res.remove(res.size() - 1);//先从集合中移除旧栈 } tmp.add(ope[i][1]); res.add(tmp);//再加入执行push操作后的新栈 } else { //pop操作 if(res.get(res.size() -1).size() != 0){ tmp = res.get(res.size() - 1); res.remove(res.size() - 1); tmp.remove(tmp.size() - 1); if (tmp.size() != 0) { res.add(tmp); } } else { //最后一个栈为空，移除这个栈 res.remove(res.size() - 1); } } } return res; }}