1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。 算法思想：需要设计一个辅助栈，用来存储当前栈中元素的最小值。网上有人说存储当前栈中元素的最小值的所在位置，虽然能节省空间，这其实是不对的，因为我在调用Min函数的时候，只能得到位置，还要对存储元素的栈不断的pop，才能得到最小值——时间复杂度o(1)。 所以，还是在辅助栈中存储元素吧。 此外，还要额外注意Push操作，第一个元素不用比较，自动成为最小值入栈。其它元素每次都要和栈顶元素比较，小的那个放到栈顶。
public class NewStack{PRivate Stack dataStack;private Stack mindataStack;public NewStack(){dataStack = new Stack();mindataStack = new Stack();}public void Push(int element){dataStack.Push(element);if (mindataStack.Count == 0)mindataStack.Push(element);else if (element <= (int)mindataStack.Peek())mindataStack.Push(element);else //(element > mindataStack.Peek)mindataStack.Push(mindataStack.Peek());}public int Pop(){if (dataStack.Count == 0)throw new Exception(“The stack is empty”);mindataStack.Pop();return (int)dataStack.Pop();}public int Min(){if (dataStack.Count == 0)throw new Exception(“The stack is empty”);return (int)mindataStack.Peek();}}2.设计含min函数的栈的另解 话说，和青菜脸呆久了，就沾染了上海小市民意识，再加上原本我就很抠门儿，于是对于上一题目，我把一个栈当成两个用，就是说，每次push，先入站当前元素，然后入栈当前栈中最小元素；pop则每次弹出2个元素。 算法代码如下所示（这里最小元素位于当前元素之上，为了下次比较方便）：
public class NewStack{private Stack stack;public NewStack(){stack = new Stack();}public void Push(int element){if (stack.Count == 0){stack.Push(element);stack.Push(element);}else if (element <= (int)stack.Peek()){stack.Push(element);stack.Push(element);}else //(element > stack.Peek){object min = stack.Peek();stack.Push(element);stack.Push(min);}}public int Pop(){if (stack.Count == 0)throw new Exception(“The stack is empty”);stack.Pop();return (int)stack.Pop();}public int Min(){if (stack.Count == 0)throw new Exception(“The stack is empty”);return (int)stack.Peek();}}之所以说我这个算法比较叩门，是因为我只使用了一个栈，空间复杂度o(N)，节省了一半的空间（算法1的空间复杂度o(2N)）。 3.用两个栈实现队列 实现队列，就要实现它的3个方法：Enqueue（入队）、Dequeue（出队）和Peek（队头）。 1）stack1存的是每次进来的元素，所以Enqueue就是把进来的元素push到stack1中。 2）而对于Dequeue，一开始stack2是空的，所以我们把stack1中的元素全都pop到stack2中，这样stack2的栈顶就是队头。只要stack2不为空，那么每次出队，就相当于stack2的pop。 3）接下来，每入队一个元素，仍然push到stack1中。每出队一个元素，如果stack2不为空，就从stack2中pop一个元素；如果stack2为空，就重复上面的操作——把stack1中的元素全都pop到stack2中。 4）Peek操作，类似于Dequeue，只是不需要出队，所以我们调用stack2的Peek操作。当然，如果stack2为空，就把stack1中的元素全都pop到stack2中。 5）注意边界的处理，如果stack2和stack1都为空，才等于队列为空，此时不能进行Peek和Dequeue操作。 按照上述分析，算法实现如下：
public class NewQueue{private Stack stack1;private Stack stack2;public NewQueue(){stack1 = new Stack();stack2 = new Stack();}public void Enqueue(int element){stack1.Push(element);}public int Dequeue(){if (stack2.Count == 0){if (stack1.Count == 0)throw new Exception(“The queue is empty”);elsewhile (stack1.Count > 0)stack2.Push(stack1.Pop());}return (int)stack2.Pop();}public int Peek(){if (stack2.Count == 0){if (stack1.Count == 0)throw new Exception(“The queue is empty”);elsewhile (stack1.Count > 0)stack2.Push(stack1.Pop());}return (int)stack2.Peek();}}4.用两个队列实现栈 这个嘛，就要queue1和queue2轮流存储数据了。这个“轮流”发生在Pop和Peek的时候，假设此时我们把所有数据存在queue1中（此时queue2为空），我们把queue1的n-1个元素放到queue2中，queue中最后一个元素就是我们想要pop的元素，此时queue2存有n-1个元素（queue1为空）。 至于Peek，则是每次转移n个数据，再转移最后一个元素的时候，将其计下并返回。 那么Push的操作，则需要判断当前queue1和queue2哪个为空，将新元素放到不为空的队列中。
public class NewStack{private Queue queue1;private Queue queue2;public NewStack(){queue1 = new Queue();queue2 = new Queue();}public void Push(int element){if (queue1.Count == 0)queue2.Enqueue(element);elsequeue1.Enqueue(element);}public int Pop(){if (queue1.Count == 0 && queue2.Count == 0)throw new Exception(“The stack is empty”);if (queue1.Count > 0){while (queue1.Count > 1){queue2.Enqueue(queue1.Dequeue());}//还剩一个return (int)queue1.Dequeue();}else //queue2.Count > 0{while (queue2.Count > 1){queue1.Enqueue(queue2.Dequeue());}//还剩一个return (int)queue2.Dequeue();}}public int Peek(){if (queue1.Count == 0 && queue2.Count == 0)throw new Exception(“The stack is empty”);int result = 0;if (queue1.Count > 0){while (queue1.Count > 1){queue2.Enqueue(queue1.Dequeue());}//还剩一个result = (int)queue1.Dequeue();queue2.Enqueue(result);}else //queue2.Count > 0{while (queue2.Count > 1){queue1.Enqueue(queue2.Dequeue());}//还剩一个result = (int)queue2.Dequeue();queue1.Enqueue(result);}return result;}}5.栈的push、pop序列是否一致 输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。 比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。 网上的若干算法都太复杂了，现提出包氏算法如下： 先for循环把arr1中的元素入栈，并在每次遍历时，检索arr2中可以pop的元素。如果循环结束，而stack中还有元素，就说明arr2序列不是pop序列。
static boolJudgeSequenceIsPossible(int[] arr1,int[] arr2){Stack stack = new Stack();for (int i = 0, j = 0; i < arr1.Length; i++){stack.Push(arr1[i]);while(stack.Count > 0 && (int)stack.Peek() == arr2[j]){stack.Pop();j++;}}return stack.Count == 0;}6.递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度o(1) 算法思想：汉诺塔的思想，非常复杂，玩过九连环的人都想得通的.
static void ReverseStack(ref Stack stack){if (stack.Count == 0)return;object top = stack.Pop();ReverseStack(ref stack);if (stack.Count == 0){stack.Push(top);return;}object top2 = stack.Pop();ReverseStack(ref stack);stack.Push(top);ReverseStack(ref stack);stack.Push(top2);}7.给栈排个序 本题目是上一题目的延伸
static void Sort(ref Stack stack){if (stack.Count == 0)return;object top = stack.Pop();Sort(ref stack);if (stack.Count == 0){stack.Push(top);return;}object top2 = stack.Pop();if ((int)top > (int)top2){stack.Push(top);Sort(ref stack);stack.Push(top2);}else{stack.Push(top2);Sort(ref stack);stack.Push(top);}}8.如何用一个数组实现两个栈 继续我所提倡的抠门儿思想，也不枉我和青菜脸相交一场。 网上流传着两种方法： 方法1 采用交叉索引的方法 一号栈所占数组索引为0, 2, 4, 6, 8……(K*2) 二号栈所占数组索引为1，3，5，7，9 ……(K*2 + 1) 算法实现如下：
public class NewStack{object[] arr;int top1;int top2;public NewStack(int capticy){arr = new object[capticy];top1 = -1;top2 = -2;}public void Push(int type, object element){if (type == 1){if (top1 + 2 >= arr.Length)throw new Exception(“The stack is full”);else{top1 += 2;arr[top1] = element;}}else //type==2{if (top2 + 2 >= arr.Length)throw new Exception(“The stack is full”);else{top2 += 2;arr[top2] = element;}}}public object Pop(int type){object obj = null;if (type == 1){if (top1 == -1)throw new Exception(“The stack is empty”);else{obj = arr[top1];arr[top1] = null;top1 -= 2;}}else //type == 2{if (top2 == -2)throw new Exception(“The stack is empty”);else{obj = arr[top2];arr[top2] = null;top2 -= 2;}}return obj;}public object Peek(int type){if (type == 1){if (top1 == -1)throw new Exception(“The stack is empty”);return arr[top1];}else //type == 2{if (top2 == -2)throw new Exception(“The stack is empty”);return arr[top2];}}}方法2： 第一个栈A：从最左向右增长 第二个栈B：从最右向左增长
public class NewStack{object[] arr;int top1;int top2;public NewStack(int capticy){arr = new object[capticy];top1 = 0;top2 = capticy;}public void Push(int type, object element){if (top1 == top2)throw new Exception(“The stack is full”);if (type == 1){arr[top1] = element;top1++;}else //type==2{top2–;arr[top2] = element;}}public object Pop(int type){object obj = null;if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);else{top1–;obj = arr[top1];arr[top1] = null;}}else //type == 2{if (top2 == arr.Length)throw new Exception(“The stack is empty”);else{obj = arr[top2];arr[top2] = null;top2++;}}return obj;}public object Peek(int type){if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);return arr[top1 - 1];}else //type == 2{if (top2 == arr.Length)throw new Exception(“The stack is empty”);return arr[top2];}}}综合比较上述两种算法，我们发现，算法1实现的两个栈，每个都只有n/2个空间大小；而算法2实现的两个栈，如果其中一个很小，另一个则可以很大，它们的和为常数n。
9.如何用一个数组实现三个栈 最后，让我们把抠门儿进行到底，相信看完本文，你已经从物质和精神上都升级为一个抠门儿主义者。 如果还使用交叉索引的办法，每个栈都只有N/3个空间。 让我们只好使用上个题目的第2个方法，不过这只能容纳2个栈，我们还需要一个位置存放第3个栈，不如考虑数组中间的位置——第3个栈的增长规律可以如下： 第1个入栈C的元素进mid处 第2个入栈C的元素进mid+1处 第3个入栈C的元素进mid-1处 第4个入栈C的元素进mid+2处 这个方法的好处是， 每个栈都有接近N/3个空间。
public class NewStack{object[] arr;int top1;int top2;int top3_left;int top3_right;bool isLeft;public NewStack(int capticy){arr = new object[capticy];top1 = 0;top2 = capticy;isLeft = true;top3_left = capticy / 2;top3_right = top3_left + 1;}public void Push(int type, object element){if (type == 1){if (top1 == top3_left + 1)throw new Exception(“The stack is full”);arr[top1] = element;top1++;}else if (type == 2){if (top2 == top3_right)throw new Exception(“The stack is full”);top2–;arr[top2] = element;}else //type==3{if (isLeft){if (top1 == top3_left + 1)throw new Exception(“The stack is full”);arr[top3_left] = element;top3_left–;}else{if (top2 == top3_right)throw new Exception(“The stack is full”);arr[top3_right] = element;top3_right++;}isLeft = !isLeft;}}public object Pop(int type){object obj = null;if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);else{top1–;obj = arr[top1];arr[top1] = null;}}else if (type == 2){if (top2 == arr.Length)throw new Exception(“The stack is empty”);else{obj = arr[top2];arr[top2] = null;top2++;}}else //type==3{if (top3_right == top3_left + 1)throw new Exception(“The stack is empty”);if (isLeft){top3_left++;obj = arr[top3_left];arr[top3_left] = null;}else{top3_right–;obj = arr[top3_right];arr[top3_right] = null;}isLeft = !isLeft;}return obj;}public object Peek(int type){if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);return arr[top1 - 1];}else if (type == 2){if (top2 == arr.Length)throw new Exception(“The stack is empty”);return arr[top2];}else //type==3{if (top3_right == top3_left + 1)throw new Exception(“The stack is empty”);if (isLeft)return arr[top3_left + 1];elsereturn arr[top3_right - 1];}}}新闻热点
疑难解答
