栈的基本概念
- 栈的定义：栈是一种只能在一端进行插入或删除操作的线性表。其中允许进行插入或删除的一端称为栈顶（top）。栈顶是由一个称为栈顶指针的位置指示器（其实就是一个变量，对于顺序栈，就是数组索引，对于链式栈，就是节点地址的指针）来指示。栈的插入和删除操作一般称为入栈和出栈。
- 栈的特点：先进后出（FILO）。
栈的本质
栈依照存储结构可分为顺序栈和链式栈。由栈的定义可知，栈是一种在操作上稍加限制的线性表，即栈的本质是线性表，而线性表恰好有两种主要的存储结构——顺序表和链表。
顺序栈的实现
#define MaxSize = 100; /*顺序栈的定义*/ typedef struct { int data[MaxSize]; int top; }Stack; /*初始化*/ void initStack(Stack &st) { st.top = -1; } /*判断栈是否为空*/ bool isEmpty(Stack st) { return st.top == -1 ? true : false; } /*进栈，返回：成功true，失败false*/ bool push(Stack &st, int x) { if(st.top == MaxSize-1) return false; st.data[++st.top] = x; return true; } /*出栈，返回：成功true,失败false*/ bool pop(Stack &st, int &x) { if(st.top == -1) return false; x = st.data[st.top--]; return true; }
说明：在考试中，栈常常作为一个工具来解决其他问题，因此一般情况下，栈的定义以及操作可以写得很简单，不必调用以上函数。上述函数只作为标准操作来参考，使用价值并不高。在考题中比较实用的栈操作写法如下：
- 定义一个栈并初始化（假设元素是int型）
/*两句话连定义和初始化都有了*/ int stack[MaxSize]; int top = -1;
-
元素x进栈
stack[++top] = x;
- 元素x出栈
x = stack[top--];
链栈的实现
/*链栈的定义*/ typedef struct { int data; Stack *next; }Stack; /*链栈的初始化*/ void initStack(Stack *&st) { st = (Stack*)malloc(sizeof(Stack)); //制造一个头结点 st->next = NULL; } /*判断是否为空*/ bool isEmpty(Stack *st) { return st->next == NULL ? true : false; } /*进栈代码*/ void push(Stack *st, int x) { Stack *p = (Stack*)malloc(sizeof(Stack)); p->data = x; /*以下头插法进栈*/ p->next = st->next; st->next = p; } /*出栈，返回：成功true，失败false*/ bool pop(Stack *st, int &x) { if(st->next == NULL) return false; Stack *p = st->next; x = p->data; /*以下是单链表删除操作*/ st->next = p->next; free(p); return true; }
说明：对于链栈，和顺序栈一样，在应对考试的时候，不必像以上那样严格地写出其操作的函数，只需摘取其中必要的语句组合在自己的题目代码中即可，类似思路类似顺序栈的讲解。特别注意，在考研中考察链栈的频率要比顺序栈的频率少得多，因为顺序栈定义和操作都简单得多。因此，对程序设计题，七分精力放在顺序栈中。
后续补上顺序栈的应用