两栈共享存储空间
两栈共享空间就是指,当其中一个栈的空间用光时,可以借用另外一个栈的空间,这样就大大提高了空间的利用率。
站在用户的角度思考问题,与客户深入沟通,找到兴城网站设计与兴城网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:网站设计制作、成都网站设计、企业官网、英文网站、手机端网站、网站推广、域名注册、虚拟空间、企业邮箱。业务覆盖兴城地区。
一个数组有两个端点,一个起始端点,另一个是数组末尾。而两个栈有两个栈底,我们就将其中一个栈底作为数组的起始端点,另一个栈底作为数组的末端。两个栈如果增加元素,就向中间延伸。
那么,我们该如何操作这个共享空间的栈呢?其中一个栈的top指针指向数组0处,另一个栈的top指针指向数组(n-1)处,n为数组长度。当top1 = -1, top2 = n时,意味着栈1和栈2都为空栈。当有数据存放在栈1中时,那么top1++,如果有元素存放在栈2中,则top2--。那么如何开辟两栈共享空间这样的结构呢?很明显需要一个数组,还需要两个指针,一个指向数组的顶端作为栈1的栈顶指针,另一个指向数组的底端作为栈2的栈顶指针。代码如下:
typedef struct{ SElemType data[MAXSIZE]; int top1; //栈1的栈顶指针 int top2; //栈2的栈顶指针 }SqDoubleStack;
那么如何实现元素的插入呢?首先你得确定插入的是栈1还是栈2,所以需要一个判断栈1还是栈2的变量stackNumber。当实现元素的插入时,首先得判断栈是否为满栈,如果满栈,则插入失败,因为已经没有空间放入新的元素了。什么时候是满栈呢?当指针top1和指针top2相差为1时,也就是两个指针见面时,此时为满栈。代码如下:
top1 + 1 == top2;
如果不是满栈,则可以继续插入元素,此时,就是判断是放入栈1还是栈2。如果是放入栈1,则
s->data[++s->top1] = e;
如果是放入栈2,则
s->data[--S->top2] = e;
完整代码如下:
Status Push ( SqDoubleStack *S, ElemType e, int stackNumber ) { if ( top1 + 1 == top2 ) return ERROR; if ( stackNumber == 1 ) S->data[++S->top1] = e; if ( stackNumber == 2 ) S->data[--S->top2] = e; return OK; }
同样的,元素的删除也就是元素的弹出(POP)操作,跟元素的弹入(PUSH)类似。想要删除元素,首先要判断是栈1的元素还是栈2的元素,如果是栈1的元素,接着要判断栈1是否为空栈,如果为空栈,则删除失败,如果不为空栈,则
--S->top1;
如果是栈2的元素,要判断栈2是否为空栈,如果不为空栈,则
++S->top2;
完整代码如下:
Status ( SqDoubleStack *S, ElemType *e, int stackNumber ) { if ( stackNumber == 1 ){ if ( S->top1 == -1 ) return ERROR; *e = S->data[S->top1--]; } if ( stackNumber == 2 ){ if ( S->top2 == MAXSIZE ) return ERROR; *e = S->data[S->top2++]; } return OK; }
网页标题:两栈共享存储空间
文章网址:http://scyanting.com/article/ihegjd.html