栈
栈的基本概念
栈是一种只允许在一段进行插入或者删除操作的线性表；因此，栈有着后进先出的特性

栈是一种线性表
这种线性表只允许在一端进行插入、删除操作
后进先出的操作特性

栈的基本操作
栈的基本操作主要有初始化一个空栈initstack(&s)、判断一个栈是否为空stackempty(s)、进栈push(&s,x)、出栈pop(&s,x)、读栈顶元素gettop(s,&x)、销毁栈clearstack(&s)

栈的顺序存储结构
采用顺序存储结构的栈叫做顺序栈，它利用一组地址上连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前栈顶的位置

#define maxsize 50 //定义栈中元素的最大个数
typedef struct{
elemtype data[maxsize];
int top; //栈顶指针
}sqstack;

栈顶指针：s.top，初始时设置s.top = -1，栈顶元素s.data[s.top]

进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素

出栈操作：栈非空时，先取栈顶元素值，栈顶指针再减一
栈空条件：s.top = -1，栈满条件：s.top = maxsize – 1，栈长s.top + 1

顺序栈的入栈操作上界maxsize的约束，因此当对栈的最大使用空间估计不足时，有可能发生栈上溢

顺序栈的基本运算

初始化

void initstack(&s){
s.top = -1; //初始化栈顶指针为-1
}


判断栈是否为空

bool stackempty(s){
if (s.top = -1)
return true;
else
return false;
}


进栈操作

bool push(&s,x){
if (s.top == maxsize - 1)
return false; //判断栈是

否已满
s.data[++s.top] = x; //指针先自加一，然后元素入栈
return true;
}


出栈操作

bool pop(&s,&x)(
if (s.top == -1)
return false;
x = s.data[s.top--]; //先出栈，指针再减一
return true;
)

需要注意的是，这里的指针指向的是栈顶元素，因此进栈的操作是s.data[++s.top] = x,出栈的操作为x = s.data[s.top--]；如果指针初始化为0（原来为-1），即指针指向的是栈顶元素的下一个位置，则入栈操作变为s.data[s.top++] = x，出栈操作变为x = s.data[--s.top]，相应的栈空、栈满条件也会变化

共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间；两个栈的栈底分别设置在共享空间的两端，两个栈向共享空间中间延伸

共享栈是为了更好利用存储空间，只有当整个存储空间被占满时才发生上溢，其存取数据的时间复杂度均为o(1)

栈的链式存储结构
采用链式存储的栈称为链栈；链栈的优点是便于多个栈共享存储空间以及提高其效率，且不存在栈满上溢的情况

链栈通常采用单链表实现，规定所有操作都在单链表的表头进行；规定链栈没有头结点，头指针lhead指向栈顶元素

栈的链式存储可表示为

typedef struct linknode{
elemtype data;
struct linknode *next;
}*listack;

采用链式存储，便于结点的插入与删除；对于带头结点和不带头结点的链栈，在具体实现上有所不同