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。
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(\arr[top1] = element; top1++; }
else if (type == 2) {
if (top2 == top3_right)
throw new Exception(\top2--;
arr[top2] = element; }
else //type==3 {
if (isLeft) {
if (top1 == top3_left + 1)
throw new Exception(\arr[top3_left] = element;
top3_left--; } else {
if (top2 == top3_right)
throw new Exception(\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(\ else {
top1--;
obj = arr[top1]; arr[top1] = null; } }
else if (type == 2) {
if (top2 == arr.Length)
throw new Exception(\ else {
obj = arr[top2]; arr[top2] = null; top2++; } }
else //type==3 {
if (top3_right == top3_left + 1)
throw new Exception(\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; }
算法大全-面试题-数据结构
