数据结构基础—栈和队列

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

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

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

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 << "创建失败\n";
	S.top = S.base; //栈空的条件 
	S.Size = MaxSize;
	cout << "空栈创建成功\n";
} 

//进栈
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 << "创建失败\n";
	    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.栈在计算机的多种实现形式

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 << "创建失败\n";
	S.top = S.base; //栈空的条件 
	S.Size = MaxSize;
	cout << "空栈创建成功\n";
} 
//创建一个空的栈3
void Initstack(intStack &S){
	S.base = (int *)malloc(MaxSize*sizeof(int));//开辟空间 
	if(!S.base) cout << "创建失败\n";
	S.top = S.base; //栈空的条件 
	S.Size = MaxSize;
	cout << "空栈创建成功\n";
} 

//进栈 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 << "创建失败\n";
	    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 << "创建失败\n";
	    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) << "\n";
//	cout << "S2:";
//	cout << *(S2.top-1) << "\n";
	}
}

/*---------------------------------------------------------------------------------------------*/
 
//计算后缀式
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的表达式，且，仅仅支持加减乘除以及小括号的的操作\n"; 
	cout << "\n"; 
	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 << "\n";
	//转换、计算和输出 
	zhuanhou(a,S1,S2);
	cout << "后缀式为：";
	Get(S1);    //获得后缀式 
	cout << "\n";
	jisuan(S1,S3);
	cout << "您输入的表达式的结果为：";
	get(S3);  //输出结果 
	return 0;
} 

三、队列

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

a.入队和出队

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

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

b.队列的类型

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

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

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

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 << "创建成功\n"; 
}

//插入队列(队尾插入)
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 << "创建成功\n"; 
}

//插入队列(队尾插入)
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;
}

四、小结

四个结构的指针存放位置

顺序栈

链栈

链队列

循环队列