数据结构_知识点_栈

1. 栈的定义

只允许在一段进行插入和删除操作的线性表。
可以理解为只有一个口的窄瓶子，出入都只能通过一个口。同时，瓶内elem按线性排列。
由特性可知，其输入与输出顺序可以有多种不同的变化。因而，栈多用于需要输出顺序特殊的临时存放。

顺序栈

typedef struct
{
    elemType data[maxSize];
    int top;
} SqStack;

顺序栈，是基于顺序线性表实现的，在c语言中通过创建数组，以及定义栈顶的指针（栈底的指针就默认为数组的为0的下标）。通过移动栈顶指针top，进行压栈，出栈的操作。
当栈为空时，top 为 -1。

链栈

typedef struct Node
{
    elemType data;
    Node *next; 
};

typedef Node *stack;

链栈一般使用没有头结点的栈表实现。
没有使用头结点的好处是，把链栈的第一个结点作为栈顶，stack作为结点指针直接执行第一个结点，就能进行所有操作，而不用通过stack找到指向第一个结点的指针。

共享栈

两个栈使用同一个顺序栈
一个把0为下标的元素作为栈底，压栈时栈顶指针 + 1
一个把maxSiza为下标的元素作为栈底，压栈时栈顶指针 - 1
当栈满时，两个栈顶指针相差1

typedef struct
{
    elemType data[maxSize];
    int top1,top2;
}stack;

定义一个数组，两个指针。

2. 栈的操作

就是基本的线性表的插入与删除操作，结合栈的特性使用即可