面试题3.1：描述如何只用一个数组来实现三个栈。
方法1：固定分割
方法2：弹性分割（较难）
package cc150;
public class ArrayStack {
public static void main(String[] args) throws Exception {
// TODO 自动生成的方法存根
ArrayStack theStack = new ArrayStack();
theStack.push(0, 1);
theStack.push(0, 2);
theStack.push(1, 10);
theStack.push(1, 11);
theStack.push(2, 20);
theStack.push(2, 21);
System.out.println(theStack.peek(1));
}
int stackSize = 100;
int[] buffer = new int[stackSize * 3];
int[] stackPointer = {-1,-1,-1}; //用于记录每个栈的栈顶在数组的位置，开始是0,100,200
//返回不是的栈的栈顶在数组中的当前位置
int absTopOfStack(int stackNum){
return stackNum * stackSize + stackPointer[stackNum];
}
//入栈
void push(int stackNum,int value) throws Exception{
if(stackPointer[stackNum] + 1 >= stackSize){
throw new Exception("超出范围");
}
//栈顶指针自增，并把值放进对应的栈
stackPointer[stackNum]++;
buffer[absTopOfStack(stackNum)] = value;
}
//出栈
int pop(int stackNum)throws Exception{
if(stackPointer[stackNum] == -1){
throw new Exception("当前栈为空");
}
int value = buffer[absTopOfStack(stackNum)];
buffer[absTopOfStack(stackNum)] = 0; //清零指定的数组
stackPointer[stackNum]--; //指针自减
return value;
}
//返回栈顶元素
int peek(int stackNum){
int index = absTopOfStack(stackNum);
return buffer[index];
}
//判断栈是否为空
boolean isEmpty(int staqckNum){
return (stackPointer[staqckNum] == -1);
}
}
面试题3.2：请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O（1）。——《Leetcode》155. Min Stack
思路：利用额外的栈来记录每一个状态的最小值，注意当所有小于栈底的元素都弹出后，最小的就是栈底元素
public class MinStack {
Stack<Integer> theStack;
Stack<Integer> theStack_temp; //最小的元素
/** initialize your data structure here. */
public MinStack() {
theStack = new Stack<Integer>();
theStack_temp = new Stack<Integer>(); //最小的元素
}
public void push(int x) {
if(theStack.empty() || x<=theStack_temp.peek())
theStack_temp.push(x);
theStack.push(x);//这句放在前会空栈
}
public void pop() {
int temp = theStack.pop();
if(temp == theStack_temp.peek())
theStack_temp.pop();
}
public int top() {
return theStack.peek();
}
public int getMin() {
return theStack_temp.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
面试题3.3：设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
package cc150;
import java.util.ArrayList;
public class SetOfStacks {
public static void main(String[] args) {
// TODO 自动生成的方法存根
}
ArrayList<ArrayList<Integer>> stacks = null;
ArrayList<Integer> curStack = null;
public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {//第一个表示push或者pop，第二个为待处理的元素
// write code here
stacks = new ArrayList<ArrayList<Integer>>(size);
curStack = new ArrayList<Integer>(size);
stacks.add(curStack);
for(int i=0;i<ope.length;i++){
if(ope[i][0] == 1)
push(ope[i][1],size);
else if(ope[i][0] == 2)
pop(size);
}
return stacks;
}
public void push(int v,int size){
if(curStack.size() != size){//数组未满
curStack.add(v);
}else{
curStack = new ArrayList<Integer>(size);
curStack.add(v);
stacks.add(curStack);
}
}
public void pop(int size){
int temp=0;
if(curStack.size() != 0){//数组未满
temp = curStack.get(curStack.size()-1);
curStack.remove(curStack.size()-1);
}else{
stacks.remove(stacks.size()-1);
curStack = stacks.get(stacks.size()-1);
temp = curStack.get(size-1);
curStack.remove(curStack.size()-1);
}
//return temp;
}
}
面试题3.4：汉诺塔问题——部分参考 Java递归算法——汉诺塔问题
面试题3.5：实现一个MyQueue类，该类用两个栈实现一个队列。——《Leetcode》232 Implement Queue using Stacks
面试题3.6：编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得讲数据复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。
面试题3.7：猫狗收容所