数据结构 – 栈的顺序存储

栈是一种特殊的线性表。栈遵循后入先出的原则，也就是说，栈只允许在栈顶一段对数据进行操作。

栈的顺序存储

同线性表的顺序存储类似，不过有一个游标去控制数据的插入和删除。先看看定义

typedef struct stack{
    elemType e;
    int top;
 }stack;

顺序栈的插入

Status SLinkListPush(SLinkList *s, SElemType e) {
	if(s->top > MAXSIZE - 1) return ERROR
	s->top++;
	s->data[s->top] = e;
	return OK;
}

顺序栈的弹出

Status SLinkListPop(SLinkList *s, SElemType *e) {
	if(s->top == -1) return ERROR;
	*e = s->data[s->top];
	s->top--;     
	return OK;                                                
}

由代码看，时间复杂度都是O（1）,因为只能对栈顶操作，所以栈相对于线性表，还是要简单点。

两栈共享空间

因为顺序栈是由数组实现。所以在长度上就有限制，如果长度分配不当就会出现溢出的现象，就得重新分配新的内存空间。如果两个栈公用一段内存空间呢？

即用一个数组去表示两个栈，假如数组长度为n，那么栈1为空时，top1 = -1，栈2为空，top2 = n,当top1 +1 == top2就表示栈满了，即数组的空间已经用完了。

定义

typedef struct stack{
    elemType e;
    int top1; 
    int top2; // 多了一个控制栈2的游标
 }stack;

具体：顺序栈即两栈共享空间-php代码模拟