栈
定义
- 线性表是具有相同数据类型的n个数据元素的有限序列，其中n是表长，当n=0时线性表是空表。若用L明明线性表，则一般表示为
L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n ) L = (a_1,a_2,...,a_i,a_{i+1},...,a_n) L=(a1,a2,...,ai,ai+1,...,an) - 栈（Stack）是一种只允许在一端进行插入或删除操作的线性表。
- 特点：后进先出
Last In First Out(LIFO)
重要术语
- 栈顶：允许插入和删除的一端 -栈顶元素
- 栈底：不允许插入和删除的一端 -栈底元素
- 空栈
基本操作
线性表
- InitList(&L)
- DestroyList(&L)
- ListInsert(&L,i,e)
- ListDelete(&L,i,&e)
- LocateElem(L,e)
- GetEle(L,i)
- Length(L)
- PrintList(L)
- Empty(L)
栈
- InitStack(&S)：初始化栈。构造一个空栈，分配内存空间
- DestoryStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间
- Push(&S,x)：入栈。若栈s未满，则将x加入栈并使之称为新栈顶。
- Pop(&S,&x)：出栈。若栈s非空，则弹出栈顶元素，并用x返回。
- GetTop(S,&x)：读取栈顶元素。若栈S非空，则用x返回栈顶元素。
- StackEmpty(S)：判断栈S是否为空，若为空则返回true，否则false。
合法的出栈顺序
组合数学结论
n个不同元素入栈，合法的出栈顺序数为
1
n
+
1
=
(
n
2
n
)
\frac{1}{n+1}={ n \choose {2n} }
n+11=(2nn)
合法性模拟法判判断
（例）设栈的入栈序列是 1 2 3 4，则下列不可能是其出栈序列的是（ ）。
A. 1 2 4 3
B. 2 1 3 4
C. 1 4 3 2
D. 4 3 1 2
E. 3 2 1 4
模拟法：
入栈
1234
出栈
- 1234
[ i 1 , o 1 , i 2 , o 2 , i 3 , o 3 , i 4 , o 4 ] [i_1,o_1,i_2,o_2,i_3,o_3,i_4,o_4] [i1,o1,i2,o2,i3,o3,i4,o4] - 1243
[ i 1 , i 2 , i 3 , i 4 , o 4 , o 3 , o 2 , o 1 ] [i_1,i_2,i_3,i_4,o_4,o_3,o_2,o_1] [i1,i2,i3,i4,o4,o3,o2,o1] - 4312
[ i 1 , i 2 , i 3 , i 4 , o 4 , o 3 ] [i_1,i_2,i_3,i_4,o_4,o_3] [i1,i2,i3,i4,o4,o3]
此时栈顶是2，无法实现o_1，所以选D
入栈
12345
出栈
- 53124
[ i 1 , i 2 , i 3 , i 4 , i 5 , o 5 ] [i1,i2,i3,i4,i5,o5] [i1,i2,i3,i4,i5,o5]
此时栈顶为4，无法实行o_3
顺序栈的实现
顺序栈的定义
#define MaxSize 10 //定义栈中最大元素个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack; //SquenceStack
顺序栈的操作
- 初始化
- 进栈
- 出栈
- 读取栈顶元素
初始化
#define MaxSize 10
typedef struct{
Elemtype data[MaxSize];
int top;
}SqStack;
//初始化栈
void InitStack(SqStack *S){
S -> top = -1;
}
//判空
bool Empty(SqStack *S){
if(S -> top == -1)return true;
return false;
}
void testStack(){
SqStack S;
InitStack(&S);
}
进栈
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
//新元素进栈