e queue2;
public NewStack()
{
queue1 = new Queue();
queue2 = new Queue();
}
public void Push(int element)
{
if (queue1.Count == 0)
queue2.Enqueue(element);
else
queue1.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 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：