定义

LIFO，仅在表尾进行插入删除操作的一种特殊线性表，是一种逻辑结构，故有多种实现方式。

实现

关键：指针和元素值的对应关系（有时指针指向当前元素——如在数组表示中初始指向-1，有时指向下一个元素——初始指向栈底，视具体情况而定）；指针如何移动（链表实现中）

顺序栈

结构体

#define Maxsize 100
typedef struct{
  ElemType data[Maxsize]; //存放栈中元素，可以是int等类型（int data[Maxsize])
  int top;
}SqStack;   //结构变量对结构成员的访问 : 结构变量.成员名

假设栈指针的初始值为-1（避免浪费一个元素空间的大小）

初始化顺序栈

//考虑空间问题，动态分配
void InitStack(SqStack &S){  
  S.top = (ElemType *)malloc(Maxsize * sizeof(ElemType));
  if (!S.top) exit (Overflow);
}
//静态分配
void InitStack(SqStack &S){
  S.top = -1;  //只须设置指针
}

判断栈空(判断指针位置，非引用型)

1
2
3

bool StackEmpty(S){
  (S.top == -1)?true:false;
}

进栈

  bool Push(SqStack &S，ElemType x){
   if (S.top == Maxsize-1)  //先判断是否还有空间
    return false;
   S.data[++S.top] = x; //先移动指针，再存数；如果初始值为0，则S.top++
   return true;
}

出栈（删除栈顶元素）

bool Pop(SqStack &S，ElemType &x){
  if (S.top == -1) //先判断是否还有元素
    return false;
  x = S.data[S.top--]; //先取数，再移动指针；如果初始值为0，则--S.top
  return true;
}

取栈顶元素（但不删除，非引用型）

bool GetTop(SqStack S，ElemType &x){
  if (S.top == -1) //先判断是否还有元素
    return false;
  x = S.data[S.top]; //不移动指针
  return true;
}

基本操作总结

int Stack[Maxsize];
int top = -1;
S.data[++S.top] = x;
x = S.data[S.top--];

链栈

结构体

typedef struct LNode{
  ElemType data;
  struct Linknode *next;
} *LiStack;  //使用结构指针对结构成员的访问: 结构指针名->结构成员

初始化链栈

void InitStack(Linknode &S){  
  S = (LNode *)malloc(sizeof(LNode)); //  假设有头结点，分配空间
  S -> next = NULL;  //栈空状态
}

判断栈空

1
2
3

bool StackEmpty(LNode S){
  (S -> next = NULL)?true:false;
}

进栈(离散存储，不用判满)

  viod Push(LNode &S，ElemType x){
   LNode *p;  //工作指针, 存储插入元素
   p = (LNode *)malloc(sizeof(LNode));  //为进栈元素申请结点空间
   p -> next = NULL;  //可以不写，但能避免一些错误
   //头插法，逆序
   p -> data = x; //先存值
   p -> next = S -> next; //先连后继指针
   S -> next = p;  //再连前驱指针
   //尾插法， R -> next = p; R = p  
}

出栈（要判空）

bool Pop(LNode &S，ElemType &x){
   LNode *p;  
   if (S -> next = NULL) return false;
   p = S -> next;  //暂存后继结点，防止断链
   x = p -> data; //取值
   S -> next = p -> next; //连上后继结点
   free(p);  //释放空间，C需要手动释放
   return true；
}

基本操作总结

1
2
3

S -> next = NULL;
p -> data = x;  p -> next = S -> next;   S -> next = p;
p = S -> next;  x = p -> data; S -> next = p -> next; free(p);

应用

括号匹配

原理：栈具有记忆的功能。如果再解决问题的过程中出现了一个子问题，但凭现有条件不能解决它，需要记下，等出现可以解决它的条件后再返回来解决。
思路：

用顺序栈实现
逐个扫描，左括号入栈，右括号与栈顶第一个左括号抵消，若栈已空，出错；
如果有多种括号，右括号与栈顶第一个左括号不一致时出错；
扫描完毕，栈空成功；不空失败
拓展：中心对称（回文），前一半元素进栈，匹配剩下的。由于涉及到n/2，要注意指针的位置，奇数时的处理（中间不用比较）

表达式求值

原理：根据算符优先级判断计算顺序，用栈记录顺序
注：此处是指中缀表达式
思路：

用两个工作栈，OPTR用于寄存运算符，OPND用于寄存操作数或运算结果，实现算符优先算法
置OPTR为空栈，OPND的栈底元素为起始运算符#
扫描表达式，操作数进OPTR;
第一个运算符进OPND,用precede比较，后续运算符大于栈顶符号优先级，压栈；相等（只可能是括号匹配）
去括号；小于，弹出OPND栈底运算符，再弹出两个操作数，用Operate计算结果，并将计算结果重新压栈
直到OPND栈底和当前扫描符号均为 #
细节：熟悉栈内外优先级的判断；运算时注意除数为0的情况
拓展：后缀求值的实现（操作数先入栈，每遇到一个运算符出栈两个数，计算后将结果压栈);由中缀表达式输入后缀表达式（去括号，通过改变运算符的顺序来表示机器执行时的顺序）

车辆调度

原理：Y型车道，需要排在前面的不进栈，排在后面的进栈，此时栈中部分起存储作用。前面的都调度完之后，将栈中部分出栈
拓展：此时栈相当于一个中转站，通过它来实现顺序的转换，有点类似Hanoi塔的中间那个柱子

数制转换

原理：N = (N div d) * d + N mod d 从低位到高位的余数，故需要用栈实现输出的逆序。
思路：

做取余运算，将余数进栈
做整除运算，用结果替换N
直到N为0，弹出所有元素
拓展：相比于数组实现的好处——利用栈的LIFO特性，不用再去考虑下标增减等细节问题

行编辑

原理：用户输入时可能出错，退格符#删一个，退行符@删一行，输入缓冲区接受一行字符后再存入到用户数据区。

接受的字符不是全文结束符EOF或换行符
/#，退栈一个
@ ClearStack 清空
其他情况，正常进栈
全文或每行结束，将栈内容送至调用过程的数据区，清空栈
拓展：注意该缓冲区与为解决主机和外设速度不匹配问题的打印数据缓冲区的区别，那个缓存区是用队列实现的，因打印要保证顺序不变；如果这里也要保证顺序不变，那就要加一个队列