[考研数据结构]第3章之栈的基本知识与操作

文章目录

栈的基本概念

栈的实现

顺序栈

共享栈

链栈

栈的基本概念

栈的定义

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

相关术语

栈顶（Top）线性表允许进行插入或删除的那一端称之为栈顶
栈底（Bottom）是固定的，不允许插入或者删除的另一端
空栈（Null Stack）不含任何数据元素的空表

重要特性

后进先出（Last In First Out）：即先入栈的元素后出栈
如入栈顺序为a1，a2，a3，a4 ，则出栈顺序为a4，a3，a2，a1

栈的实现

顺序栈

定义

采用顺序存储的栈称之为顺序栈，它利用一组地址连续的存储单元存放自栈底至栈顶的数据元素，同时附设一个指针top，指向当前栈顶的位置。

基本操作

顺序存储类型

//栈的存储类型定义
typedef struct Stack{
	int data[MaxSize];//存放栈中元素
	int top;//指向当前栈顶元素 
}SqStack;

初始化

//初始化
void InitStack(SqStack &S){
	S.top=-1;//初始化栈顶指针，指向当前的栈顶位置 
}

判空

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

判满

//判满
bool IsFull(SqStack &S){
	if(S.top==MaxSize-1)
		return true;
	else 
		return false;
}

入栈（进栈）

//入栈（进栈）
bool Push(SqStack &S,int x){
	//栈满则报错，无法入栈 
	if(S.top==MaxSize-1)
		return false;
	S.data[++S.top]=x;//因为栈顶指针初始化为-1指向当前位置，故增加元素时应先令top加一再入栈 
	return true;
}

出栈

//出栈
bool Pop(SqStack &S,int &x){
	//栈空则报错，无法出栈 
	if(S.top==-1)
		return false;
	x=S.data[S.top--];//先出栈，指针再减一
	return true; 
}

读取栈顶元素

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

测试

#include"stdio.h"
#include"stdlib.h"
#define MaxSize 10
//栈的存储类型定义
typedef struct Stack{
	int data[MaxSize];//存放栈中元素
	int top;//指向当前栈顶元素 
}SqStack;

//初始化
void InitStack(SqStack &S){
	S.top=-1;//初始化栈顶指针，指向当前的栈顶位置 
} 
//判空
bool IsEmpty(SqStack &S){
	if(S.top==-1)
		return true;
	else 
		return false;
} 
//判满
bool IsFull(SqStack &S){
	if(S.top==MaxSize-1)
		return true;
	else 
		return false;
} 
//求栈长
int StackLength(SqStack &S){
	return S.top+1;
} 
//入栈（进栈）
bool Push(SqStack &S,int x){
	//栈满则报错，无法入栈 
	if(S.top==MaxSize-1)
		return false;
	S.data[++S.top]=x;//因为栈顶指针初始化为-1指向当前位置，故增加元素时应先令top加一再入栈 
	return true;
} 
//出栈
bool Pop(SqStack &S,int &x){
	//栈空则报错，无法出栈 
	if(S.top==-1)
		return false;
	x=S.data[S.top--];//先出栈，指针再减一
	return true; 
} 
//读取栈顶元素
bool GetTop(SqStack &S,int &x){
	//栈空则报错，无法读取 
	if(S.top==-1)
		return false;
	x=S.data[S.top];
	return true;
} 
//打印栈中所有元素
void PrintStack(SqStack &S){
	printf("\n当前栈中元素如下：\n");
	for(int i=S.top;i>=0;i--){
		printf("%d ",S.data[i]);
	}
	printf("\n");
} 
//测试 
int main(){
	SqStack S;
	//1.初始化栈
	InitStack(S);
	//2.入栈
	printf("请输入10个整数进行入栈：\n");
	int n;
	for(int i=0;i<10;i++){
		scanf("%d",&n);
		Push(S,n);
	} 
	PrintStack(S);
	//3.出栈 
	 printf("请输入你要出栈的次数：\n");
	 int x,times;//x带回被删除的栈顶元素 ，times为出栈次数 
	 scanf("%d",&times);
	 if(times>StackLength(S)){
	 	printf("出栈次数不合法！");
	 }else{
	 	printf("依次出栈的元素如下：\n");
	 	for(int i=0;i<times;i++){
	 		Pop(S,x);
	 		printf("%d ",x);
	 	}
	 } 
	 PrintStack(S);
	return 0;
} 

/*
测试数据：
1 2 3 4 5 6 7 8 9 10 
*/

共享栈

概念

利用栈底位置不变的特性，可以让两个顺序栈共享一个一维数组的空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

性质

以上图所示的共享栈为例：

当top1= -1，1号栈为空；当top2=MaxSize=10时，2号栈为空
当 top2-top1=1 时，即两个栈顶指针相邻时，则栈满
当1号栈入栈时，top1先加1再赋值；当2号栈入栈时，top2先减1再赋值
出栈时与入栈时相反

代码实现

存储类型

//共享栈的存储结构类型
typedef struct CommonStack{
	int data[MaxSize];
	int top1;
	int top2;
}ComStack;

初始化

//初始化共享栈
void InitComStack(ComStack &S){
	S.top1=-1;
	S.top2=MaxSize;
}

入栈

//共享栈的入栈
bool Push(ComStack &S,int StackType,int x){
	//判满 
	if(S.top2-S.top1==1)
	   return false;
	//说明是1号栈入栈 
	if(StackType==1){
		S.data[++S.top1]=x;
	}else if(StackType==2){//说明是2号栈入栈 
		S.data[--S.top2]=x;
	}
	return true;
}

出栈

// 共享栈的出栈
bool Pop(ComStack &S,int StackType,int &y){
	//判空
	if(S.top1==-1&&S.top2==MaxSize)
		return false;
    //说明是1号栈出栈 
	if(StackType==1){
		y=S.data[S.top1--];
	}else if(StackType==2){//说明是2号栈出栈 
		y=S.data[S.top2++];
	}
	return true;
}

测试

#include"stdio.h"
#include"stdlib.h"
#define MaxSize 10
//共享栈的存储结构类型
typedef struct CommonStack{
	int data[MaxSize];
	int top1;
	int top2;
}ComStack; 

//初始化共享栈
void InitComStack(ComStack &S){
	S.top1=-1;
	S.top2=MaxSize;
} 
//共享栈的入栈
bool Push(ComStack &S,int StackType,int x){
	//判满 
	if(S.top2-S.top1==1)
	   return false;
	//说明是1号栈入栈 
	if(StackType==1){
		S.data[++S.top1]=x;
	}else if(StackType==2){//说明是2号栈入栈 
		S.data[--S.top2]=x;
	}
	return true;
} 
// 共享栈的出栈
bool Pop(ComStack &S,int StackType,int &y){
	//判空
	if(S.top1==-1&&S.top2==MaxSize)
		return false;
    //说明是1号栈出栈 
	if(StackType==1){
		y=S.data[S.top1--];
	}else if(StackType==2){//说明是2号栈出栈 
		y=S.data[S.top2++];
	}
	return true;
} 
int main(){
	ComStack S;
	//初始化共享栈
	InitComStack(S);
	//入栈
	int a1,a2;
	printf("请输入5个整数进入1号栈：\n");
	for(int i=0;i<5;i++){
		scanf("%d",&a1);
		Push(S,1,a1);
	} 
	printf("请再输入5个整数进入2号栈：\n");
	for(int i=0;i<5;i++){
		scanf("%d",&a2);
		Push(S,2,a2);
	} 
	printf("共享栈内元素如下：\n");
	for(int i=0;i<10;i++){
		printf("%d ",S.data[i]);
	} 
	printf("\n");
	int y,type;
	printf("请输入你要执行出栈操作的栈号：");
	scanf("%d",&type);
	Pop(S,type,y);
	printf("已成功将%d号栈的栈顶元素：%d 弹出栈！\n",type,y);
	printf("此时共享栈内的元素如下：\n");
	//打印1号栈 
	for(int i=0;i<=S.top1;i++){
		printf("%d ",S.data[i]);
	}
	//打印2号栈 
	for(int j=S.top2;j<10;j++){
		printf("%d ",S.data[j]);
	}
	return 0;
}