数据结构-栈(3)
< 返回列表时间: 2020-07-23来源:OSCHINA
两栈共享空间
可以用一个数组来存储两个相同类型的栈。
数组有两个端点,两个栈有两个栈底,
让一个栈的栈底作为数组的开始端,下标为0处,
让另外一个栈的栈底作为数组的结束端,下标为n-1出。
两个栈如果增加元素,就是两个端点向中间延伸。
两个栈的栈底在数组两端, 新增元素,向中间考虑,即两个栈底的栈顶top1和 top2向中间靠拢, 只要top1和top2 不见面, 两个栈就可以一直使用。
当栈1为空时 top1 = -1
当栈2为空时 top2 = n
若栈2 是空栈, 栈1的top1 等于 n-1时, 就是栈1满了。
若栈1 是空栈, 栈2的的top2等于0时, 就是栈2满了。
两个栈见面时,也就是top1 和 top2之间差1时 , 即top1+1 = top2 是栈满。
//两栈共享空间结构 typedef struct{ SElemType data[MAXSIZE]; //栈1栈顶指针 int top1; //栈2栈顶指针 int top2; } //两栈push方法 Status Push(SqDoubleStack *S, SElemType *e, int stackNumber){ //栈已满, 不能再push新元素 if(S->top1+1 == S->top2){ return ERROR; } //栈1有新元素进栈, 则先top1+1给数组元素赋值 if(stackNumber == 1){ S->data[++s->top1] = e; }else if(stackNumber == 2){ //栈2有新元素进栈, 则先top2-1给数组元素赋值 S->data[--S->top2] = e; } return ok; } //两栈pop方法 若栈不为空,则删除S的栈顶元素,用e返回其值, 并返回OK; 否则返回ERROR Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber){ if(stackNumber == 1){ //栈1已经是空栈 if(S->top1 == -1){ return ERROR; } //栈1的栈顶元素出栈 *e = S->data[S->top1--]; }else if(stackNumber == 2){ //栈2已经是空栈 if(S->top2 == MAXSIZE){ return ERROR; } //栈2的栈顶元素出栈 *e = S->data[S->top2++]; } return OK; }
已经在push入口侧判断过栈满情况,后面的top+1 或top2-1不用担心溢出的问题。
使用这样的数据结构, 通常都是当两个栈的空间需求有相反的关系时,也就是一个栈增长时另外一个栈在缩短的情况。
这样使用两栈共享空间存储才有比较大的意义。否则两个栈都在不停地增长,很快会引栈满而溢出。
两栈共享空间针对的是相同数据类型的栈。
热门排行