栈是限定只在线性表的一端进行插入和删除的结构，允许插入删除的一段叫做栈顶，另一端叫做栈底，不含任何元素的叫做空栈，栈又称为后进先出（LIFO）的线性表。
栈有两种实现方法：1. 顺序储存 顺序栈 2. 链式储存 链栈
顺序栈也有两种方法：
数组法 这种方法实现的时候top指针初始化为-1，而且每次压栈都是top先移动到下一位，再赋值。 判断栈满：S->top==STACKSIZE-1 这种方法创建的顺序栈无法扩大栈的空间，因此暂时不实现。 数组实现的定义： typedef int SElemType; typedef struct{ SElemType data[STACKSIZE]; int top; } 2. 动态分配内存，栈大小可变 具体代码如下: #include<stdio.h> #include<stdlib.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define FALSE 0 #define TRUE 1 #define ERROR -1 #define OVERFLOW -1 #define OK 1 typedef int SElemType; typedef int Status; typedef struct SqStack{ SElemType *base; SElemType *top; int stacksize; }SqStack; //------基本操作---------- Status InitStack(SqStack*S); //构造空栈S Status DestroyStack(SqStack*S); //销毁栈S，S不再存在 Status ClearStack(SqStack *S); //把S置为空栈 Status StackEmpty(SqStack S); //判断栈是否为空，是的话返回TRUE，否则返回FALSE int StackLength(SqStack S); //返回栈的长度 Status GetTop(SqStack S,SElemType *e); //通过e返回栈顶元素，如果空栈返回ERROR Status Push(SqStack*S,SElemType e); //插入元素e为新的栈顶元素 Status Pop(SqStack *S,SElemType*e); //若栈为空，返回ERROR,否则删除栈顶元素，用e返回其值 //--------基本操作的实现 Status InitStack(SqStack* S) { S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK; } Status DestroyStack(SqStack*S) { free(S->base); S->base=S->top=NULL; S->stacksize=0; return OK; } Status ClearStack(SqStack *S) { S->top=S->base; return OK; } Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; } int StackLength(SqStack S) { int i=0,*p=S.base; while(p!=S.top) {i++;p++;} return i; } Status GetTop(SqStack S,SElemType *e) { if(S.base=S.top) return ERROR; *e=*(S.top-1); return OK; } Status Push(SqStack*S,SElemType e) { if(S->top-S->base>=S->stacksize) S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S->base) return OVERFLOW; S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; return OK; } Status Pop(SqStack *S,SElemType*e) { if(S->base==S->top) return ERROR; *e=*(--S->top); return OK; } 栈的大小不被限制，只需判断是否是空栈即可 链栈： 链栈就是一个用空间换时间的结果，更适合插入，删除。 链栈的定义如下： typedef int SElemType; typedef struct StackNode{ SElemType data; struct StackNode* next; }StackNode,*LinkStackPtr; typedef struct LinkStack{ LinkStackPtr top; int count; }LinkStack;链栈的实现过程比较简单，对照它的储存结构进行操作即可。