栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
栈是一个线性表，栈具有线性关系，即前驱后继关系。只不过是一种特殊的线性表。定义中说在 表尾进行插入和删除操作，这里表尾是只栈顶而不是栈底。栈的特殊之处就在于限制了这个线性表的插入和删除位置，他始终在栈顶进行。这也使得栈底是固定的，最先进栈的只能在栈底。
栈的插入操作叫做进栈，也称压栈、入栈。
栈的删除操作，叫做出栈，也称弹栈。
ADT 栈(stack)Data 同线性表元素具有相同的类型，相邻元素具有前驱和后继关系Operation InitStack(*S):初始化操作，建立一个空栈S DestoryStacks(*S):若栈存在，则销毁它 ClearStack(*S):将栈清空 StackEmpty(S):若栈为空，返回ture,否则返回false GetTop(S,*e):若栈存在且非空，用e返回S的栈顶元素 Push(*S,e):若栈S存在，插入新元素e到栈S中并成为栈顶元素 POP(*S,*e):删除栈中栈顶元素，并用e返回其值 StackLength(S):返回栈S的元素个数endADt
栈的顺序储存结构及实现栈的顺序储存结构其实于是线性表顺序储存的简化，我们简称为顺序栈。可以使用数组来实现，我们可以使用数组下标为0的一端来作为栈底，我们定义一个top变量来指示栈顶变量在数组中的位置，若储栈的长度为StackSize，则栈顶位置必须小于StackSize，当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1.
下面为栈的结构定义：
typedef int SElemType;//SElemType类型视情况而定 //顺序栈结构 typedef struct{SElemType data[MAXSIZE];int top;//用于栈顶指针 }SqStack;
进栈操作Push：
//插入新元素e为新的栈顶元素 Status Push(SqStack *S,SElemType e){if(S->top == MAXSIZE-1)//栈满 {return ERROR;}S->top++;//栈顶指针增加1 S->data[S->top]=e;//将新插入元素赋值给栈顶空间 return OK; }
出栈操作Pop：
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR status Pop(SqStack *S,SElemType *e) {if(S->top == -1)return ERROR;*e=S->data[S->top];//将要删除的栈顶元素赋值给e S->top--;//栈顶指针减1 return OK;}
两栈共享空间如果有两个相同类型的栈，我们为他们各自开辟了一个数组空间，如果中一个栈满了，另一个栈还空着，这样就造成了空间的浪费。我们可以用一个数组来存放两个栈，充分利用数组的储存空间。
数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，就是的数组下标为0处，另一个栈的栈底为数组的末端，也就是下标为数组长度n-1处，如果增加元素就是向数组的中间位置延伸。
top1和top2是栈1和栈2的栈顶指针，如果栈1为空时，就是top1等于-1时，而当top2等于n时就是栈2为空时。如果两个指针之间按相差1时，即top1+1==top2时为栈满。
两栈共享空间的代码如下：
//两栈共享空间结构 typedef struct{SElemType data[MAXSIZE];int top1;//栈1栈顶指针 int top2;//栈2栈顶指针 }SqDoubleStack;
对于两栈共享空间的push方法，我们除了要插入元素值参数之外，还需要有一个判断为栈1还是栈2的栈号参数stackNumber。
插入元素的代码如下：
//插入元素e为新的栈顶元素 Status Push(SqDoubleStack *S,SElemtype e , int stackNumber){if(S->top1 +1==S->top2 )//栈已满，不能在push新元素 return ERROR;if(stackNumber==1)//栈1有元素入栈 S->data[++S->top1]=e;//若是栈1则先top1+1后给数组元素赋值 else if(stackNumber==2)//栈2有元素入栈 S->data[--S->top2]=e;//若是栈2则先top2-1后给数组元素赋值 return OK;}
对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR status Pop(SqDoubleStack *S,SElemType *e,int stackNumber){if(stackNumber==1){if(S->top1=-1)return ERROR;//说明栈1已是空栈，溢出 *e=S->data[S->top1--]//将栈1的栈顶元素出栈 }else if(stackNumber==2){if(S->top2==MAXSIZE)return ERROR;//说明栈2已是空栈，溢出 *e=S->data[S->top2++];//将栈2的栈顶元素出栈 }return OK;}
栈的链式储存存结构及实现栈的链式储存结构简称栈链。
一般来说栈顶放在单链表的头部，另外已经有栈顶在顶部，那么头节点就失去意义了，使用对于栈链来说一般是不需要头节点的。
栈链的结构代码如下：
//栈链结构 typedef struct StackNode{SElemType data;struct StackNode *next;}StackNode,*linkStackPtr;typedef struct{linkStackPtr top;int count;}linkStack;
对于栈链的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，代码如下：
//插入元素e为新的栈顶元素 Status Push(linkStack *S,SElemType e){linkStackPtr s=(linkStackPtr)malloc(sizeof(StackNode));s->data=e;s->next =S->top //把当前的栈顶元素赋值给新结点的后继 S->top =s//将新结点s赋值给栈顶指针 S->count++;return OK;}
对于链栈的出栈pop操作，先假设变量p用来储存要删除的结点，将栈顶指针下移一位，最后释放p即可，代码如下：
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status Pop(linkStack *S,SElemType e){linkStackPtr p;if(StackEmpty(*S))return ERROR;*e=S->top->data;p=S->top;//将栈顶结点赋值给p S->top =S->top->next;//使得栈顶指针下移一位，指向后一结点 free(p);//释放结点p S->count--;return OK;}
如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好用栈链，反之，它的变化在可控范围内，使用顺序栈更好一点。