數據結構基礎—棧和隊列

来源:https://www.cnblogs.com/wht-de-bk/archive/2022/10/09/16774069.html
-Advertisement-
Play Games

數據結構基礎—棧和隊列 一、棧和隊列的基本概念和性質 棧和隊列都是特殊的線性表 對他們的操作有著規定和限制：在插入和刪除時只能對某一端操作 棧：只能在一端進行(先進後出) 隊列：只能在表尾插入，在表頭刪除(先進先出） 二、棧 表頭為棧底，表尾為棧頂 1.棧的基本操作和規則 a.進棧和出棧 進棧：棧頂 ...


數據結構基礎—棧和隊列

一、棧和隊列的基本概念和性質

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 << "創建失敗\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.棧在電腦的多種實現形式

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 << "創建失敗\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.隊列的類型

  • 鏈隊列：和之前的鏈表差不多,下麵是出入鏈隊的圖解

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

四、小結

四個結構的指針存放位置

順序棧

image

鏈棧

image

鏈隊列

image

迴圈隊列

image


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 帶你認識什麼是“迴流重繪”
    摘要：要想減少迴流和重繪的次數，首先要瞭解迴流和重繪是如何觸發的。 本文分享自華為雲社區《前端頁面之“迴流重繪”》，作者：CoderBin。 “迴流重繪”是什麼？ 在HTML中，每個元素都可以理解成一個盒子，在瀏覽器解析過程中，會涉及到迴流與重繪： 迴流：佈局引擎會根據各種樣式計算每個盒子在頁面上的 ...
  • 關於架構師：角色、能力和挑戰
    導讀：成為一名架構師可能是很多開發者的技術追求之一。那麼如何理解架構？架構師是一個什麼樣的角色，需要具備什麼樣的能力？在架構師的道路上，會面臨哪些挑戰？本文作者道延分享他對架構以及架構師的思考和相關實踐，希望對同學們有所啟發。 ...
  • 設計模式-行為型模式之模板方法
    定義抽象基類，規範介面內部方法執行順序 在進階篇中，沒專門提過抽象基類，在這裡順便就提一下 抽象基類的核心特征：不能被直接實例化 相反，抽象基類和元類一樣，一般都被當做頂層基類使用，派生類必須實現抽象類中指定的方法，且方法名也必須保持一致 抽象基類的主要用途：從一種高層次上規範編程介面 話不多說，直 ...
  • 近40年銀行核心系統變遷歷程及新建設模式
    本文詳細介紹了我國銀行核心系統的定義、位置與邊界，發展歷程、更換核心系統的原因，以及新核心建設的五大模式與其特點對比。希望內容能夠幫助銀行科技從業者建立起對銀行核心系統的整體認知，提供一定積極的指導作用與借鑒意義，從而引發思考並促進行業交流與探討，共同為我國的銀行科技蓬勃發展貢獻自己的智慧與經驗。 ... ...
  • OnionArch - 採用DDD+CQRS+.Net 7.0實現的洋蔥架構
    外觀模式是最常用的結構型設計模式，也是一種非常容易理解的設計模式，其核心就是為多個子系統提供一個統一的介面，將這個介面看作是這些子系統的門面。 ...
  • golang開發:go併發的建議(完)
    上次說了一下Go語言佈道師 Dave Cheney對Go併發的建議，個人覺得最重要的一條，這次主要想說一下這個。 8.3. Never start a goroutine without knowning when it will stop(永遠不要在不知道何時停止的情況下啟動 goroutine) ...
  • Future詳解
    Future模式 【1】Future模式是多線程開發中常見的設計模式，它的核心思想是非同步調用。對於Future模式來說，它無法立即返回你需要的數據，但是它會返回一個契約，將來你可以憑藉這個契約去獲取你需要的信息。 【2】通俗一點就是生產者-消費者模型的擴展。經典“生產者-消費者”模型中消息的生產者不 ...
  • 【Java8新特性】- Stream流
    stream是java8新出的抽象概念，他可以讓你根據你期望的方式來處理集合數據，能夠輕鬆的執行複雜的查找、過濾和映射數據等操作。Stream 使用一種類似用 SQL 語句從資料庫查詢數據的直觀方式來提供一種對 Java 集合運算和表達的高階抽象。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類