网上的若干算法都太复杂了，现提出包氏算法如下：

先for循环把arr1中的元素入栈，并在每次遍历时，检索arr2中可以pop的元素。如果循环结束，而stack中还有元素，就说明arr2序列不是pop序列。

static bool JudgeSequenceIsPossible(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