数据结构基础—栈和队列

数据结构基础—栈和队列

数据结构基础—栈和队列

一、栈和队列的基本概念和性质

image

栈和队列都是特殊的线性表

对他们的操作有着规定和限制:在插入和删除时只能对某一端操作

  1. 栈:只能在一端进行(先进后出)
  2. 队列:只能在表尾插入,在表头删除(先进先出)

二、栈

表头为栈底,表尾为栈顶

1.栈的基本操作和规则

a.进栈和出栈

  • 进栈:栈顶则成为进栈的数据(插入)。如果是顺序表,则一定要进行判满
  • 出栈:将当前栈顶移出(删除),不管什么存储类型,一定要判空

b.进栈、出栈前后的次序

一个数的出栈可以在另一个数进栈前出,但不可以在另一个数进栈后,在这个数(另一个进栈的数)前出。

当一个数进栈后,若它前面有数,则在出栈时它前面的所有数的排列都是入栈的逆序


举个栗子:若进栈顺序为1 2 3,则,出栈时,不可能是那种排列?

答案:不可能是 3 1 2,为什么呢?

咱们一个一个分析,之前说过,一个数的出栈可以在另一个数入栈之前

  • 1进,2进前1出,2进,3进前2出,3进3出 : 1 2 3
  • 1进,2进前1出,2进,3进,3出2出 :1 3 2
  • 1进,2进,3进前2出,1出 ,3进3出 :2 1 3
  • 1进,2进,3进前2出,3进,3出1出 :2 3 1
  • 1进,2进,3进,3出2出1出 :3 2 1

所以不可能出现 3 1 2 的排列的,,若3前面有数,则出栈后3后的顺序一定是1 2 的逆序(和上面对应)

C.栈的类型

根据存储结构的不同分为顺序栈(顺序存储)和链栈(链式存储),在这里主要是研究顺序栈(链栈和链表差不多…)

d.顺序栈的一些基本操作

//是否为空
S.base == S.top;
//是否已满
S.top - S.base =>len;
//栈不存在
S.base = NULL;

/*类型自己转换吧*/
//栈的基本结构
typedef struct Stack{
	char *base;
	char *top;
	int Size;
}SqStack;

//创建空栈
void InitStack(SqStack &S){
	S.base = (char *)malloc(MaxSize*sizeof(char));//开辟空间 
	if(!S.base) cout << "创建失败
";
	S.top = S.base; //栈空的条件 
	S.Size = MaxSize;
	cout << "空栈创建成功
";
} 

//进栈
void Push(SqStack &S,char e){
	if((S.top-S.base) >=MaxSize){ //判满
		S.base = (char *)malloc(S.base,(MaxSize+ADD)*sizeof(char));
	    if(!S.base) cout << "创建失败
";
	    S.top = S.base+MaxSize; 
	    S.Size = S.Size+ADD;
	}else{
		*S.top++ = e;			
	}
}

//出栈,获取出栈元素
char Pop(SqStack &S){
	char e;
	if(S.top == S.base) cout << "栈空";
	e = *--S.top;
	return e;
} 

//输出栈的元素
void Get(SqStack &S){
	for(int i = 0;S.base != S.top-i;i++){
		cout << *(S.base+i);
	}	
} 

2.栈在计算机的多种实现形式

image

3.栈的案例分析

表达式的求值(表达式最后添加一个”#”)

相关知识:

  • 前缀式:+ * ab * – c / def
  • 中缀式:a * b+ (c – d / e) * f
  • 后缀式:ab * cde / – f * +
  • 后缀式

思路:将我们常见的中缀式先转化成后缀式,在根据后缀式来进行计算

  1. 中缀式->后缀式(利用运算符的优先级)
    • 先建立一个后缀式栈(1栈)来放最后生成的后缀式,在建立一个运算符栈(2栈),栈底为”#”来判断各个运算符之间的关系
    • 遍历输入的表达式
    • 若判断 1栈为空直接入1栈,否则判断是否是操作数(a,b,c…),是,则也直接入1栈
    • 若当前为运算符,则与2栈的的栈顶的运算符比较优先级,若有先级高与栈底,则入2栈;若低于或等于,则将栈顶的运算符出2栈,进1栈,再将当前栈顶与之比较直到优先级最高为止
    • 若遇到”()”,”(“直接如2栈,”)”将”(“前所有的运算符出2栈,进1栈。并将”(“出2栈
    • 最后遍历到 “#”时,运算符依次出2栈,直到2栈栈顶为”#”
    • 转换完成
  2. 后缀式求值
    • 再建立一个操作栈(3栈),用来暂时存放计算过程和最终显示结果
    • 遍历1栈
    • 若遍历到的1栈元素为数字,则,入3栈
    • 若若遍历到的1栈元素为运算符,则,将3栈中的后两个元素出栈,与该运算符进行正常运算,结果再入3栈
    • 如此反复,直到”#”位置
  3. 输出3栈的栈顶(也就这一个元素)即可完成计算

具体的代码有点多了,大家想看就看看吧…

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
#define MaxSize 100
#define ADD 10
#define M 20 
typedef struct Stack{
	char *base;
	char *top;
	int Size;
}SqStack;

typedef struct stack{
	int *base;
	int *top;
	int Size;
}intStack;


//创建一个空的栈1,2
void InitStack(SqStack &S){
	S.base = (char *)malloc(MaxSize*sizeof(char));//开辟空间 
	if(!S.base) cout << "创建失败
";
	S.top = S.base; //栈空的条件 
	S.Size = MaxSize;
	cout << "空栈创建成功
";
} 
//创建一个空的栈3
void Initstack(intStack &S){
	S.base = (int *)malloc(MaxSize*sizeof(int));//开辟空间 
	if(!S.base) cout << "创建失败
";
	S.top = S.base; //栈空的条件 
	S.Size = MaxSize;
	cout << "空栈创建成功
";
} 

//进栈 1,2
void Push(SqStack &S,char e){
	if((S.top-S.base) >=MaxSize){
		S.base = (char *)malloc((MaxSize+ADD)*sizeof(char));
	    if(!S.base) cout << "创建失败
";
	    S.top = S.base+MaxSize; 
	    S.Size = S.Size+ADD;
	}else{
		*S.top++ = e;			
	}
}

//进栈 3
void push(intStack &S,int e){
	if((S.top-S.base) >=MaxSize){
		S.base = (int *)malloc((MaxSize+ADD)*sizeof(int));
	    if(!S.base) cout << "创建失败
";
	    S.top = S.base+MaxSize; 
	    S.Size = S.Size+ADD;
	}else{
		*S.top++ = e;			
	}
}

//出栈1,2 
char Pop(SqStack &S){
	char e;
	if(S.top == S.base) cout << "栈空";
	e = *--S.top;
	return e;
} 

//出栈3
int pop(intStack &S){
	char e;
	if(S.top == S.base) cout << "栈空";
	e = *--S.top;
	return e;
} 

//判断优先级 
           //进栈  栈顶 
int judge(char a,char b){
	if(a == "*"||a == "/"){
		if(b == "*"||b == "/") return 1; 
		if(b == "+"||b == "-") return 2;     //>进 	
	}
	
	if(a == "+"||a == "-"){
		if(b == "*"||b == "/") return 3; 
		if(b == "+"||b == "-") return 1; 
	}
	
	if(a == "*"||a == "/"||a == "+"||a == "-"){
		if(b == "#") return 2;           //进 
		if(b == "(") return 2;           //进 
	} 
}


/*---------------------------------------------------------------------------------------------*/

//中缀转后缀的函数 
void zhuanhou(char *a,SqStack &S1,SqStack &S2){
	char b;
	int p = 0; 
	for(int i = 0;i < strlen(a);i++){//遍历 
		if(S1.base == S1.top){Push(S1,a[i]);} //S1空直接进 
		else{
			//()和操作数的操作 
			if(a[i] == "(") {Push(S2,a[i]); }  //(:直接进 
		    if(a[i]!= "*"&&a[i]!= "+"&&a[i]!= "-"&&a[i]!= "/"&&a[i]!= "("&&a[i]!= ")"&&a[i] != "#") {Push(S1,a[i]);} //操作数直接进 
			if(a[i] == ")"){           //):让(之前的运算符依次出2栈,进1栈 
				while(*(S2.top-1) !="("){
					b = Pop(S2);
					Push(S1,b);
				}
				Pop(S2); //2栈出(
			}
			
			//运算符的操作 
			if(a[i]== "*"||a[i]== "+"||a[i]== "-"||a[i]== "/"){  
				p = judge(a[i],*(S2.top-1));//判断操作数的关系 
				if(p == 2) {Push(S2,a[i]); } 
				else{
					while(p != 2){       //非进2栈的处理 
						b = Pop(S2);
						Push(S1,b);
						p = judge(a[i],*(S2.top-1));
					}
					Push(S2,a[i]);
				}
			} 
			//表达式遍历完成额操作 
			if(a[i] =="#"){          
				while((*(S2.top-1) != "#")){
					b = Pop(S2); 
					Push(S1,b);
			    } 	
			}
		
		}
		
//	cout << "S1:";                                 //判断流程 
//	cout << *(S1.top-1) << "
";
//	cout << "S2:";
//	cout << *(S2.top-1) << "
";
	}
}

/*---------------------------------------------------------------------------------------------*/
 
//计算后缀式
void jisuan(SqStack &S1,intStack &S3){
	char a;
	int b;
	int d;
	int  c;
	for(int i = 0;S1.base != S1.top-i;i++){//遍历1栈
		if(*(S1.base+i)!= "*"&&*(S1.base+i)!= "+"&&*(S1.base+i)!= "-"&&*(S1.base+i)!= "/") {
			a = *(S1.base+i);
		    push(S3,(int)a-48);
		}
		if(*(S1.base+i)== "*"||*(S1.base+i)== "+"||*(S1.base+i)== "-"||*(S1.base+i)== "/"){
			b = pop(S3);
			d = pop(S3);
			if(*(S1.base+i)== "*"){c = (d)*(b);}
			if(*(S1.base+i)== "+"){c = (d)+(b);}
			if(*(S1.base+i)== "-"){c = (d)-(b);}
			if(*(S1.base+i)== "/"){c = (d)/(b);}
			push(S3,c);
		}
	}
} 

//输出栈(栈底到栈顶)
void Get(SqStack &S){
	for(int i = 0;S.base != S.top-i;i++){
		cout << *(S.base+i);
	}	
} 

//输出栈3
void get(intStack &S){
	for(int i = 1;S.base != S.top-i+1;i++){
		cout << *(S.top-i);
	}	
} 

int main(){
	cout << "注:本程序只能计算最大位数为9的表达式,且,仅仅支持加减乘除以及小括号的的操作
"; 
	cout << "
"; 
	cout << "请输入要计算的表达式:";
	char a[M];
	gets(a);         //获取表达式 
	//建立3个栈 
	SqStack S1;
	cout <<"后缀式"; 
	InitStack(S1);

	SqStack S2;
	cout << "运算符";
	InitStack(S2);
	Push(S2,"#");
	 
	intStack S3;
	cout << "操作"; 
	Initstack(S3);
	cout << "
";
	//转换、计算和输出 
	zhuanhou(a,S1,S2);
	cout << "后缀式为:";
	Get(S1);    //获得后缀式 
	cout << "
";
	jisuan(S1,S3);
	cout << "您输入的表达式的结果为:";
	get(S3);  //输出结果 
	return 0;
} 

三、队列

1.队列的基本操作和规则

a.入队和出队

先进先出(和我们排队买票一样)

  • 入队:将要入队的元素添加到队尾,将其设置为新的队尾
  • 出队:将队头的元素移出,并将队头更新

b.队列的类型

  • 链队列:和之前的链表差不多,下面是出入链队的图解

image

  • 顺序队列(一般循环):因为不循环的话可能会出现假满的情况,使用循环就不会出现,只需要浪费一个单元存放队尾指针即可判断队列满的条件

假满:如图,在队头更新时,会余下队头之前的单位,让队列还有位置,但是显示已满

image

c.循环队列的一些基本操作

//是否为满
(Q.rear+1)%MaxSize == Q.front //循环要出一圈的数取余的

/*类型自己转换吧*/
//栈的基本结构    
typedef struct{
	int *base;
	int front;
	int rear;
}SqQueue;

//创建一个空循环队列
void InitQueue(SqQueue &Q){
	Q.base = (int*)malloc(MaxSize*sizeof(int));
	if(!Q.base) cout << "创建失败";
	Q.front = Q.rear = 0;//类似于数组
	cout << "创建成功
"; 
}

//插入队列(队尾插入)
void EnQueue(SqQueue &Q,int e){
	if((Q.rear+1)%MaxSize == Q.front%MaxSize) cout << "队列已满";
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%MaxSize;//要相对位置
}

//移出队列(队头移出)
int DeQueue(SqQueue &Q){
	int e;
	e = Q.base[Q.front];
	Q.front = (Q.front +1)%MaxSize;
	return e;
} 

//输出队列 
void Get(SqQueue &Q){
	for(int i = 0;Q.front+i < Q.rear;i++){
		cout << Q.base[Q.front+i];
	}
} 
    

2.队列的案例分析

打印杨辉三角(二项式系数)

思路:在每一行的首尾都虚出一个0用来计算和判断换行 ,从一行开始,每一行的值都是上一行该位值与其前一个值的相加

  1. 使用一个temp用来存放每行一开始的0和前一个值,使用front来存放已经出队的值和判读是否换行的0
  2. 现入队第一行 1 1 0
  3. 出队1次,与temp相加后再入队 101 ,让temp = front
  4. 判断front是否为0,为0换行,不为零输出front
  5. 出队一次,重复第3、4步 0 1 2 -> 1 2 1(第二行),此时的front = 0换行
  6. 再次重复第3 、4 、5补即可

代码

#include<iostream>
#include<cstdlib>
#define MaxSize 100
using namespace std;

typedef struct{
	int *base;
	int front;
	int rear;
}SqQueue;

//创建一个空循环队列
void InitQueue(SqQueue &Q){
	Q.base = (int*)malloc(MaxSize*sizeof(int));
	if(!Q.base) cout << "创建失败";
	Q.front = Q.rear = 0;
	cout << "创建成功
"; 
}

//插入队列(队尾插入)
void EnQueue(SqQueue &Q,int e){
	if((Q.rear+1)%MaxSize == Q.front%MaxSize) cout << "队列已满";
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%MaxSize;
}

//移出队列(队头移出)
int DeQueue(SqQueue &Q){
	int e;
	e = Q.base[Q.front];
	Q.front = (Q.front +1)%MaxSize;
	return e;
} 

int main(){
	int line ; 
	cout << "请输入打印杨辉三角的行数:";
	cin >> line;
	int front;
	int temp = 0;
	int jieshou;
	
	SqQueue Q;
	InitQueue(Q);
	//先入队第一行
	EnQueue(Q,1);
	EnQueue(Q,1);
	EnQueue(Q,0);
	for(int i = 1;i <= line;){
		 //第一行出队并与前一相加入队 
		 front = DeQueue(Q);
		 EnQueue(Q,temp+front);
		 //判断输出和换行的
		 if(front != 0) {cout << front << " ";}
		 else{
		 	cout <<endl;
		 	EnQueue(Q,0);
		 	i++;//换行 
		 }
		 temp = front;//让temp始终是要出队数的前一个数 
		 //cout << endl;
	}
	return 0;
}

四、小结

四个结构的指针存放位置

顺序栈

image

链栈

image

链队列

image

循环队列

image

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 数据结构基础—栈和队列