資料結構基礎—堆疊和佇列

一、堆疊和佇列的基本概念和性質

堆疊和佇列都是特殊的線性表

對他們的操作有著規定和限制：在插入和洗掉時只能對某一端操作

堆疊：只能在一端進行(先進后出)
佇列：只能在表尾插入，在表頭洗掉(先進先出）

二、堆疊

表頭為堆疊底，表尾為堆疊頂

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堆疊)來放最后生成的后綴式，在建立一個運算子堆疊(2堆疊)，堆疊底為"#"來判斷各個運算子之間的關系
- 遍歷輸入的運算式
- 若判斷 1堆疊為空直接入1堆疊，否則判斷是否是運算元(a,b,c...)，是，則也直接入1堆疊
- 若當前為運算子，則與2堆疊的的堆疊頂的運算子比較優先級，若有先級高與堆疊底，則入2堆疊；若低于或等于，則將堆疊頂的運算子出2堆疊，進1堆疊，再將當前堆疊頂與之比較直到優先級最高為止
- 若遇到"()","("直接如2堆疊，")"將"("前所有的運算子出2堆疊，進1堆疊，并將"("出2堆疊
- 最后遍歷到 "#"時，運算子依次出2堆疊，直到2堆疊堆疊頂為"#"
- 轉換完成
后綴式求值
- 再建立一個操作堆疊(3堆疊)，用來暫時存放計算程序和最終顯示結果
- 遍歷1堆疊
- 若遍歷到的1堆疊元素為數字，則，入3堆疊
- 若若遍歷到的1堆疊元素為運算子，則，將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用來計算和判斷換行，從一行開始，每一行的值都是上一行該位值與其前一個值的相加

使用一個temp用來存放每行一開始的0和前一個值，使用front來存放已經出隊的值和判讀是否換行的0
現入隊第一行 1 1 0
出隊1次，與temp相加后再入隊 101 ，讓temp = front
判斷front是否為0，為0換行，不為零輸出front
出隊一次，重復第3、4步 0 1 2 -> 1 2 1（第二行），此時的front = 0換行
再次重復第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;
}

四、小結

四個結構的指標存放位置

順序堆疊

鏈堆疊

鏈佇列

回圈佇列

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/511884.html

標籤：C

上一篇：c++ container容器(string,vector,map,queue,stack等等)

下一篇：微軟全力擁抱 Java！