25考研数据结构复习·3.1栈·顺序栈·链栈

栈（Stack）基本概念

数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构）

• 定义

  栈（Stack）是只允许在一端进行插入或删除操作的线性表

  逻辑结构：与普通线性表相同

  数据的运算：插入、删除操作有区别

• 重要术语

  • 栈顶

    允许插入和删除的一端

  • 栈底

    不允许插入和删除的一端

  • 空栈

• 基本操作

  • 创、销

    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

• 常考题型

  进栈顺序： a → b → c → d → e

  有哪些合法的出栈顺序？

  • 结论

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

顺序栈的实现

• 用顺序存储方式实现的栈

  • 定义

#define MaxSize 10       //定义栈中元素的最大个数
typedef struct{
	ElemType data[MaxSize] //静态数组存放栈中元素
	int top;               //栈顶指针
}SqStack;                //Sq:sequence——顺序

void testStack(){
		SqStack S;  //声明一个顺序栈（分配空间）
		//……后续操作……
}

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

• 基本操作

  • 创（初始化）

#define MaxSize 10       //定义栈中元素的最大个数
typedef struct{
	ElemType data[MaxSize] //静态数组存放栈中元素
	int top;               //栈顶指针
}SqStack;                //Sq:sequence——顺序

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

void testStack(){
		SqStack S;  //声明一个顺序栈（分配空间）
		//……后续操作……
}

//判断栈空
bool StackEmpty(SqStack S){
		if(S.top == -1)      //栈空
				return true;
		else
				return false;
}

 增（进栈）

#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.data[++S.top] = x;
		return true;
}

 删（出栈）

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

//出栈操作
bool Pop(SqStack &S,ElemType &x){
		if(S.top == MaxSize-1)  //栈空，报错
				return false;
		x = S.data[S.top];   //栈顶元素先出栈
		S.top = S.top -1;   //指针再减1，数据还残留在内存中，只是逻辑上被删除了
		return true;
}

 查（获取栈顶元素）

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

//出栈操作
bool Pop(SqStack &S,ElemType &x){
		if(S.top == MaxSize-1)  //栈空，报错
				return false;
		x = S.data[S.top--]
		return true;
}

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

另一种方式： 

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

//初始化栈
void InitStack(SqStack &S){
		S.top = 0;   //初始化栈顶指针（初始指向0）
}
void testStack(){
		SqStack S;  //声明一个顺序栈（分配空间）
		InitStack(S);
		//……后续操作……
}

//判断栈空
bool StackEmpty(SqStack S){
		if(S.top ==0)  //栈空
				return true;
		else
				return false;
}

//进栈
S.data[S.top++]=x;
//出栈
x=S.data[--S.top];

栈满条件：top == MaxSize

缺点：栈的大小不可变

 共享栈（两个栈共享同一片空间）

#define MaxSize 10       //定义栈中元素的最大个数
typedef struct{
	ElemType data[MaxSize] //静态数组存放栈中元素
	int top0;               //0号栈栈顶指针
	int top1;               //1号栈栈顶指针
}SqStack;                

//初始化栈
void InitStack(SqStack &S){
		S.top0 = -1;   //初始化栈顶指针
		S.top1 = MaxSize;
}
满栈的条件：top0 + 1 = top1  

 总结

链栈的实现

• 用链式存储方式实现的栈

  （头插法建立单链表）对头结点的后插操作 → 进栈

  （单链表的删除操作）对头结点的后删操作 → 出栈

  • 定义

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

 基本操作参考单链表（创：初始化；增：进栈；删：出栈；查：获取栈顶元素）