重点
栈（出入栈的过程、出栈序列的合法性）和队列的操作及其特征是重中之重。均是线性表的应用和推广
1.栈的定义
栈只允许一端进行插入或删除操作的线性表。栈是一种线性表。但是限定这种线性表只能在某一端进行插入和删除操作。
栈顶（Top）:线性表允许进行插入和删除的那一端。
栈底（Bottom）:固定的，不允许进行插入和删除的那一端。
空栈：不含任何元素的空表
LIFO
2.栈的基本操作
InitStack(&S): 初始化一个栈
StackEmpty(S): 判断一个栈是否为空，若栈S为空返回True，否则返回false
Push(&S,x): 进栈，若栈S未满，将x加入使之成为新栈顶
Pop(&S,&x): 弹出栈，返回x
GetTop(S,&x): 读栈顶元素，若栈S非空，用x返回栈顶元素
ClearStack(&S): 销毁栈， 并释放S占用的存储空间
符号“&”是C++所特有的，表示引用（别名），在c语言中可以用*代替
3.栈的顺序存储结构
1）顺序栈的实现
栈的顺序存储
//栈的顺序存储结构 #define MaxSize 50 //定义栈中最大元素 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; //存放栈中元素 int top; //栈顶指针 }SqStack;
进栈指针：S.top,初始时设置S.top=-1;栈顶元素:S.dada[S.top].
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作： 栈非空时，先取栈顶元素值，再将栈顶指针减1
栈空条件：S.top = -1;栈满条件：S.top==MaxSize-1;栈长：S.top+1;
由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢。
2） 顺序栈的基本运算
#include <cstdlib> #include <cstdio> using namespace std; //栈的顺序存储结构 #define MaxSize 50 //定义栈中最大元素 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; //存放栈中元素 int top; //栈顶指针 }SqStack; void InitStack(SqStack &S) { S.top = -1; } bool StackEmpty(SqStack S) { return S.top == -1; } bool Push(SqStack &S, ElemType x) { if (S.top == MaxSize - 1) return false; S.data[++S.top] = x; return true; } bool Pop(SqStack &S, ElemType &x) { if (!(StackEmpty(S))) { x = S.data[S.top--]; return true; } return false; } bool Gertop(SqStack S, ElemType &x) { if (S.top == -1) return false; x = S.data[S.top]; return true; } bool ClearStack(SqStack &S) { if (S.top == -1) return false; S.top = -1; //清空栈 return true; } void prinStack(SqStack S) { ElemType x; while (!StackEmpty(S)) { Pop(S, x); printf("%d ", x); } } int main() { int i = 10; SqStack s; InitStack(s); while (i--) { ElemType e; scanf("%d", &e); Push(s, e); } prinStack(s); return 0; }
3）共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
4.栈的链式存储结构
不存在栈满上溢的情况，通常用单链表实现，规定所有的操作都是在单链表的表头进行的
//栈的链式存储结构,头插法 typedef struct Linknode{ ElemType data; struct Linknode *next; //指针域 }*LinkStack; //栈类型定义
5.试题精选
1）基本操作是指该结构最核心、最基本的运算，其他较复杂的操作可以通过基本操作来实现。
2）栈和队列都是限制存取点的线性结构
3）对于n个不同元素出栈，出栈序列的个数为：
此公式为卡特兰数，
4）设单链表的表头指针为h，节点结构由data和next两个域组成，其中data欲为字符型，试设计算法判断该链表前n个字符是否中心对称
bool dc( LinkedList L, int n) { if (n <= 1) //n的值不合法，n必须大于会等于2才考虑对称性 return false; LNode *p = L->next; char arr[MaxSize]; //字符栈 int top = -1; //栈顶指针 while (p != NULL && top < (n / 2 - 1)) { arr[++top] = p->data; p = p->next; } if (p == NULL) //链表总长度<=n/2,不满足条件 return false; if (n & 1) //n为奇数 p = p->next; //忽略中间数 while (p != NULL && top > -1) { if (p->data != arr[top--]) return false; p = p->next; } if (top > -1) //栈未被清空，说明字符总数不到n个 return false; else return true; }