【数据结构】进阶线性表【栈】

定义

栈：栈是一种只能在一端进行插入或删除操作的线性表

栈顶、栈底：表中允许进行插入、删除操作的一端称为栈顶。另一端则为栈底

特点

先进先出

顺序存储结构

采用顺序存储结构的栈称为顺序栈

普通栈

算法要素

• 栈空条件：s->top == -1
• 栈满条件：s->top == Maxsize-1
• 进栈操作：先将栈顶指针top增1，然后将元素e放在栈顶指针处
• 出栈操作：先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1

共享栈

使用一个数组来实现两个栈，称为共享栈

算法要素

• 栈空条件：栈1空为top1 == -1; 栈2空为top2 == Maxsize
• 栈满条件：top1 == top2-1
• 进栈操作：进栈1操作为top1++; data[top1] = x 进栈2操作为top2--; data[top2] = x;
• 出栈操作：出栈1操作为 x = data[top1]; top1-- 出栈2操作为 x = data[top2]; top2++ ;

链式存储结构

采用链式存储结构的栈称为链栈

算法要素

• 栈空条件：s->next == NULL
• 栈满条件：不存在栈满的情况，除非内存溢出
• 进栈操作：新建一个结点存放元素e（由p指向它），将结点p插入到头结点之后
• 出栈操作：取出首结点的值并将它删除