栈和队列（五）：与栈和队列相关的算法
2012-04-04 11:09:50这篇文章是一些与栈和队列相关的算法
1.栈的push、pop序列是否一致
2.如何用一个数组实现两个栈
3.用两个栈实现队列
4.如果用一个循环数组q[num]表示队列时，该队列只有一个头引用front，不设尾引用rear，而改置计数器count用以记录队列中节点的个数。请实现出该队列的基本运算并回答此队列中能容纳的元素个数是count-1吗
1.栈的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 SequenceIsPossible(int[] arr1, int[] arr2)
{
Stack stack = new Stack();
for(inti = 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;
}
2.如何用一个数组实现两个栈
网上流传着两种方法：
方法1 采用交叉索引的方法
一号栈所占数组索引为0, 2, 4, 6, 8......(K2)
二号栈所占数组索引为1，3，5，7，9 ......(K2 + 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("栈已满");
else
{
top1 += 2;
arr[top1] = element;
}
}
else //type==2
{
if (top2 + 2 >= arr.Length)
throw new Exception("栈已满");
else
{
top2 += 2;
arr[top2] = element;
}
}
}
public object Pop(int type)
{
object obj = null;
if (type == 1)
{
if (top1 == -1)
throw new Exception("栈为空");
else
{
obj = arr[top1];
arr[top1] = null;
top1 -= 2;
}
}
else //type == 2
{
if (top2 == -2)
throw new Exception("栈为空");
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("栈为空");
return arr[top1];
}
else //type == 2
{
if (top2 == -2)
throw new Exception("栈为空");
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("栈已满");
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("栈为空");
else
{
top1--;
obj = arr[top1];
arr[top1] = null;
}
}
else //type == 2
{
if (top2 == arr.Length)
throw new Exception("栈为空");
else
{
obj = arr[top2];
arr[top2] = null;
top2++;
}
}
return obj;
}
public object Peek(int type)
{
if (type == 1)
{
if (top1 == 0)
throw new Exception("栈为空");
return arr[top1 - 1];
}
else //type == 2
{
if (top2 == arr.Length)
throw new Exception("栈为空");
return arr[top2];
}
}
}
综合比较上述两种算法，我们发现，算法1实现的两个栈，每个都只有n/2个空间大小；而算法2实现的两个栈，如果其中一个很小，另一个则可以很大，它们的和为常数n。
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("队列为空");
else
while (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("队列为空");
else
while (stack1.Count > 0)
stack2.Push(stack1.Pop());
}
return (int)stack2.Peek();
}
}
4.如果用一个循环数组data[maxsize]表示队列时，该队列只有一个头引用front，不设尾引用rear，而改置计数器count用以记录队列中节点的个数。请实现出该队列的基本运算并回答此队列中能容纳的元素个数是count-1吗？
分析：依照题意，可以得出如下条件：
队列为空： count == 0；
队列为满： count == maxsize；
队列尾元素位置： (front + count) % maxsize；
队列首元素位置： (front + 1) % maxsize；
实现代码如下：
public class NewQueue<T>
{
private int maxsize;
private T[] data;
private int front;
private int count;
public T this[int index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}
public int Maxsize
{
get
{
return maxsize;
}
set
{
maxsize = value;
}
}
public int Front
{
get
{
return front;
}
set
{
front = value;
}
}
public NewQueue(int size)
{
data = new T[size];
maxsize = size;
front = -1;
count = 0;
}
public void EnQueue(T elem)
{
if (IsFull())
{
throw new Exception("队列已满，不能再插入了。");
}
data[(front + count) % maxsize] = elem;
count++;
}
public T DeQueue()
{
if (IsEmpty())
{
return default(T);
}
count--;
return data[(front + 1) % maxsize];
}
public T GetFront()
{
if (IsEmpty())
{
return default(T);
}
return data[(front + 1) % maxsize];
}
public int GetLength()
{
return count;
}
public void Clear()
{
front = -1;
count = 0;
}
public bool IsEmpty()
{
if (count == 0)
{
return true;
}
else
{
return false;
}
}
private bool IsFull()
{
if (count == maxsize)
{
return true;
}
else
{
return false;
}
}
}
注：本题队列可以容量最多的元素个数为maxsize，而不是maxsize - 1。
