3.1 定义
- 栈是限定仅在表尾进行插入和删除操作的线性表
3.2 基本操作
操作 | 描述 |
---|---|
InitStack(&S) | 初始化栈S,构造一个空栈 |
DestroyStack(&S) | 若栈存在,则销毁它 |
Push(&S,x) | 若栈S存在,插入新元素x到栈S中并成为栈顶元素 |
Pop(&S,&x) | 删除栈S中栈顶元素,并用x返回其值 |
GetTop(S,&x) | 返回栈S中栈顶元素,不修改栈顶指针 |
StackEmpty(S) | 若栈为空,返回true,否则返回false |
- (常考:给你一个出栈序列,问你能不能通过入栈操作得到这个出栈序列)共有卡特兰数种出栈序列:$C_n=\frac{1}{n+1}\binom{2n}{n}$
3.3 顺序栈
顺序栈的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
typedef struct{
int data[MAXSIZE];
int top;
} SqStack;
//初始化
void InitStack(SqStack *S){
S->top=-1;
}
//判空
int StackEmpty(SqStack S){
if(S.top==-1)
return 1;
else
return 0;
}
//入栈
int Push(SqStack *S, int x){
if(S->top==MAXSIZE-1)
return 0;
S->top++;
S->data[S->top]=x;
return 1;
}
//出栈
int Pop(SqStack *S, int *x){
if(S->top==-1)
return 0;
*x=S->data[S->top];
S->top--;
return 1;
}
//取栈顶元素
int GetTop(SqStack S, int *x){
if(S.top==-1)
return 0;
*x=S.data[S.top];
return 1;
}共享栈
3.4 链栈
- 链栈的实现
1