算法大全-面试题-数据结构

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; }