只允许在一端进行插入或删除操作的线性表

后进先出LIFO

image-20200316102101311

进栈顺序:a1->a2->a3->a4->a5

出栈顺序:a5->a4->a3->a2->a1

基本操作

InitStack(&S):初始化栈。构造一个空栈S，分配内存空间。创建

DestroyStack(&L):销毁栈。销毁并释放栈S所占用的内存空间。销毁

Push(&S,x):进栈，若栈S未满，则将x加入使之成为新栈顶。增

Pop(&S,&x):出栈，若栈S非空，则弹出栈项元素，并用x返回。删

GetTop(S, &x):读栈顶元素。若栈S非空，则用x返回栈顶元素。查
查栈的使用场景中大
多只访问栈顶元素

其他常用操作

StackEmpty(S):判断-一个栈S是否为空。若S为空，则返回true，否则返回false。

规律

n个不同元素进栈，出栈元素不同排列的个数为

$$ \frac{1}{n+1}\sideset{}{^n_2n}C $$

1/n+1乘Cn 2n

上述公式称为卡特兰(Catalan) 数，可采用数学归纳法证
明(不要求掌握)

5个进栈有42种方式

顺序栈

定义

1
2
3
4
5
6
7
8
#define MaxSize 10
//定义栈中元素的最大个数
typedef struct{
	ElemType data [MaxSize];
	//静态数组存放栈中元素
	int top;
	//栈顶指针
} SqStack;

顺序存储:给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

初始化

1
2
3
4
5
//初始化栈
void InitStack(SqStack &S){
S.top=-1;
//初始化栈顶指针
}

判断是否为空

1
2
3
4
5
//判断栈空
bool StackEmpty(SqStack S){
	return S.top==-1?true:false;
    //S.top==-1为空栈
}

进栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define MaxSize 10//定义栈中元素的最大个数
typedef struct{
ElemType data [MaxSize];//静态数组存放栈中元素
int top;//栈顶指针
} SqStack;

//新元素入栈
bool Push(SqStack &S , ElemType x){
if(S.top==MaxSize-1) //栈满，报错
	return false;
S.top = S.top + 1;//指针先加1
S.data[S.top]=x;//新元素入栈
//相当于S.data[++S.top]=x;
return true;
}

出栈

1
2
3
4
5
6
7
8
9
//出栈操作
bool Pop(SqStack &S, ElemType &x){
if(S.top==-1)//栈空，报错
return false;
x=S.data [S.top];//栈顶元素先出栈
S.top = S.top-1; //指针再减1
//相当于x=S.data[S.top--];
return true;
}

读栈顶元素

1
2
3
4
5
6
7
//读栈项元素
bool GetTop(SqStack S, ElemType &x){
if(S.top==-1)//栈空，报错
	return false;
x=S.data[S.top];//x记录栈顶元素
return true;
}

销毁

清空：top=-1

回收：系统自动回收

栈顶指针的另一种设计方式

在初始化栈的时候 S.top=-1改为S.top=0

即设定top指向下一个元素

出栈和入栈等操作相应的改变

S.data[++S.top]=x->S.data[S.top++]=x

x=S.data[S.top--]->x=S.data[--S.top]

缺点

栈的大小不可变

共享栈

两个栈共享一片空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//定义
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data [MaxSize]; //静态数组存放栈中元素
int top0; //0号栈钱顶指针
int top1; //1号栈浅顶指针
} ShStack;

//初始化栈
void InitStack(ShStack &S){
S.top0=-1; //初始化栈顶指针
S.top1=MaxSize;
}
//判满
top0+1==top1

链栈

相当于一个规定只能从头节点一侧进行操作的单链表

定义

1
2
3
4
typedef struct Linknode{
ElemType data;//数据域
struct Linknode *next;//指针域
}*LiStack;//栈类型定义