从最左向右增长
第二个栈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];
else
return arr[top3_right - 1];
}
}
}