数据结构 – 栈的顺序存储

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

栈的顺序存储

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

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代码模拟

发表评论

电子邮件地址不会被公开。 必填项已用*标注