日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁(yè) 編程語言 正文

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記——順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧

作者：晚風(fēng)(●?σ ) 更新時(shí)間： 2022-05-13 編程語言

目錄

  • 一、棧的相關(guān)知識(shí)
  • 二、順序棧的定義
  • 三、順序棧的初始化
  • 四、判斷順序棧是否為空棧
  • 五、判斷順序棧是否為滿棧
  • 六、進(jìn)棧（插入操作）
  • 七、出棧（刪除操作）
  • 八、讀取順序棧頂元素
  • 九、順序棧的建立
    • 一個(gè)簡(jiǎn)單的順序棧的基本實(shí)現(xiàn)例子
  • 十、棧的遍歷輸出

一、棧的相關(guān)知識(shí)

  • 棧是一種只允許在一端進(jìn)行插入或刪除操作的線性表，它是一種特殊的線性表，其遵循的原則是先進(jìn)后出（FILO），即后進(jìn)的元素先被取出來。由于它是一種線性表，所以有兩種方式：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示，即順序棧和鏈?zhǔn)綏?/code>。

在這里插入圖片描述
其中，棧的插入操作稱為進(jìn)棧，棧的刪除操作稱為出棧。

二、順序棧的定義

通過一組數(shù)組地址的連續(xù)的存儲(chǔ)單元來存放從棧底開始至棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)置一個(gè)棧頂指針top，用于指示當(dāng)前棧頂元素的位置，代碼如下：

#define MaxSize 20//可自行設(shè)置
typedef struct {
	int data[MaxSize];//存放棧中元素 ，使用數(shù)組
	int top;//棧頂指針 ，記錄棧頂元素的位置 
} SqStack;//順序棧的類型定義

我們可以得到，由于c語言中數(shù)組的下標(biāo)是從0開始的，所以棧的總長(zhǎng)度為S.top+1，即要加1。

三、順序棧的初始化

初始化一個(gè)順序棧，這里的參數(shù)SqStack &S，帶有“&”，表示引用調(diào)用，即對(duì)參數(shù)的修改結(jié)果進(jìn)行帶回，棧頂指針為S.top，棧頂元素的值為S.data[S.top]，初始化時(shí)定義S.top=-1表示順序棧為空，而當(dāng)S.top=0時(shí)，表示棧中只存在一個(gè)元素，代碼如下：

/*順序棧的初始化，初始化一個(gè)空棧*/
void InitStack(SqStack &S) {
	S.top=-1;//順序棧為空
}

四、判斷順序棧是否為空棧

可以得到，判斷順序棧是否為空棧的條件是S.top==-1，表示此時(shí)順序棧中為空棧，無任何元素，代碼如下：

/*判斷順序棧是否為空*/
bool StackEmpty(SqStack S) {
	if(S.top==-1)//當(dāng)top=-1時(shí)，棧為空，而并不是S.top=0（它表示的是棧中有一個(gè)元素）.
		return true;
	else
		return false;
}

五、判斷順序棧是否為滿棧

判斷順序棧是否為空棧的條件是S.top==MaxSize-1，由于c語言數(shù)組下標(biāo)從0開始的，棧中元素最大個(gè)數(shù)MaxSize要減1，即當(dāng)top=MaxSize-1時(shí)，表示此時(shí)順序棧中已滿，無法再存入元素，代碼如下：

/*判斷順序棧是否為滿棧*/
bool StackFull(SqStack S) {
	if(S.top==MaxSize-1)//由于c語言數(shù)組下標(biāo)從0開始的，即當(dāng)top=MaxSize-1時(shí)，此時(shí)棧滿。
		return true;
	else
		return false;
}

六、進(jìn)棧（插入操作）

將一個(gè)元素插入順序棧中，即進(jìn)棧，由于進(jìn)棧后元素個(gè)數(shù)有變化，所以要用引用“&”，即SqStack &S，首先判斷順序棧是否已滿，然后在新的元素進(jìn)棧前，所以棧頂指針要先加1，即++S.top，然后將進(jìn)棧元素的值傳入并將其入棧，如下：

++S.top;//top指針始終指向棧頂，新的元素進(jìn)棧，所以指針先加1
S.data[S.top]=x;//將進(jìn)棧元素的值傳入并入棧

這兩行代碼也可以使用一行代碼：S.data[++S.top]=x直接替換。
進(jìn)棧操作的完整代碼如下：

/*進(jìn)棧操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若棧已滿，則報(bào)錯(cuò)
		return false;
	++S.top;//top指針始終指向棧頂，新的元素進(jìn)棧，所以指針先加1
	S.data[S.top]=x;//將進(jìn)棧元素的值傳入并入棧
	//S.data[++S.top]=x;
	return true;
}

七、出棧（刪除操作）

將一個(gè)元素從順序棧中刪除，即出棧，由于棧的特性，只能先進(jìn)后出，即從棧頂進(jìn)行刪除操作然后依次，同樣出棧后元素個(gè)數(shù)有變化，所以要用引用“&”，即SqStack &S，首先判斷順序棧是否為空，元素出棧后（將棧頂元素賦給x），然后棧頂指針要減1，如下：

x=S.data[S.top];//出棧
S.top--;//指針減1

這兩行代碼也可以使用一行代碼：x=S.data[S.top--]直接替換。
出棧操作的完整代碼如下：

/*出棧操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	x=S.data[S.top];//出棧
	S.top--;//指針減1
	//x=S.data[S.top--];
	return true;
}

八、讀取順序棧頂元素

讀取順序棧頂元素，這里并沒有將棧頂元素取出（無出棧操作），首先判斷當(dāng)前順序棧是否為空，然后通過x來記錄棧頂元素，如下：

/*讀取棧頂元素*/
bool StackGetTop(SqStack S,int &x) {
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	x=S.data[S.top];//x記錄棧頂元素
	return true;
}

九、順序棧的建立

順序棧的建立中輸入一個(gè)值代表要?jiǎng)?chuàng)建的棧的元素個(gè)數(shù)，然后通過一個(gè)for循環(huán)建立順序棧，其中使用到棧的進(jìn)棧操作，每次向棧中插入元素，代碼如下：

/*棧的建立*/
void CreateStack(SqStack &S,int x){
	int number;
	printf("請(qǐng)輸入要建立棧的元素個(gè)數(shù)：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("輸入第%d個(gè)入棧的元素：\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	}
}

一個(gè)簡(jiǎn)單的順序棧的基本實(shí)現(xiàn)例子

例如，創(chuàng)建一個(gè)順序棧，棧中元素從棧底到棧頂依次為1,2,3,4,5，第一步首先輸出當(dāng)前棧頂元素；第二步通過用戶輸入一個(gè)要進(jìn)棧的元素“6”，并輸出進(jìn)棧后此時(shí)的棧頂元素；第三步通過執(zhí)行一次出棧操作后，然后再輸出此時(shí)的棧頂元素。
實(shí)現(xiàn)代碼如下：

#include
#define MaxSize 20//可自行設(shè)置
typedef struct {
	int data[MaxSize];//存放棧中元素 ，使用數(shù)組
	int top;//棧頂指針 ，記錄棧頂元素的位置
} SqStack;//順序棧的類型定義

/*順序棧的初始化，初始化一個(gè)空棧*/
void InitStack(SqStack &S) {
	S.top=-1;//順序棧為空
}

/*判斷順序棧是否為空*/
bool StackEmpty(SqStack S) {
	if(S.top==-1)//當(dāng)top=-1時(shí)，棧為空，而并不是S.top=0（它表示的是棧中有一個(gè)元素）.
		return true;
	else
		return false;
}

/*判斷順序棧是否為滿棧*/
bool StackFull(SqStack S) {
	if(S.top==MaxSize-1)//由于c語言數(shù)組下標(biāo)從0開始的，即當(dāng)top=MaxSize-1時(shí)，此時(shí)棧滿。
		return true;
	else
		return false;
}

/*進(jìn)棧操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若棧已滿，則報(bào)錯(cuò)
		return false;
	++S.top;//top指針始終指向棧頂，新的元素進(jìn)棧，所以指針先加1
	S.data[S.top]=x;//將進(jìn)棧元素的值傳入并入棧
	//S.data[++S.top]=x;
	return true;
}

/*出棧操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	x=S.data[S.top];//出棧
	S.top--;//指針減1
	//x=S.data[S.top--];
	return true;
}

/*讀取棧頂元素*/
bool StackGetTop(SqStack S,int &x) {
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	x=S.data[S.top];//x記錄棧頂元素
	return true;
}

/*棧的建立*/
void CreateStack(SqStack &S,int x) {
	int number;
	printf("請(qǐng)輸入要建立棧的元素個(gè)數(shù)：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("輸入第%d個(gè)入棧的元素：\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	}
}

/*主函數(shù)*/
int main() {
	SqStack S;
	int x,e;
	InitStack(S);//初始化
	CreateStack(S,x);//創(chuàng)建順序棧
	StackGetTop(S,x);//讀取棧頂元素
	printf("讀取棧頂元素,當(dāng)前棧頂元素為：%d\n",x);
	printf("輸入一個(gè)要進(jìn)棧的元素：");
	scanf("%d",&e);
	StackPush(S,e);//進(jìn)棧
	StackGetTop(S,x);
	printf("讀取棧頂元素,當(dāng)前棧頂元素為：%d\n",x);
	StackPop(S,x);//出棧
	StackGetTop(S,x);
	printf("執(zhí)行一次出棧操作后,當(dāng)前棧頂元素為：%d",x);
}

運(yùn)行結(jié)果如下：
在這里插入圖片描述

十、棧的遍歷輸出

首先判斷順序棧是否為空，然后通過while循環(huán)，當(dāng)S.top!=-1時(shí)一直執(zhí)行下去，每次輸出棧頂?shù)脑兀缓笤贉p1，如下代碼：

/*棧的遍歷輸出*/
bool PrintStack(SqStack S,int x){
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	while(S.top!=-1){
		x=S.data[S.top--];
		printf("%d ",x);
	}
	return true;
}

例如，下列代碼：

#include
#define MaxSize 20//可自行設(shè)置
typedef struct {
	int data[MaxSize];//存放棧中元素 ，使用數(shù)組
	int top;//棧頂指針 ，記錄棧頂元素的位置
} SqStack;//順序棧的類型定義

/*順序棧的初始化，初始化一個(gè)空棧*/
void InitStack(SqStack &S) {
	S.top=-1;//順序棧為空
}

/*判斷順序棧是否為空*/
bool StackEmpty(SqStack S) {
	if(S.top==-1)//當(dāng)top=-1時(shí)，棧為空，而并不是S.top=0（它表示的是棧中有一個(gè)元素）.
		return true;
	else
		return false;
}

/*判斷順序棧是否為滿棧*/
bool StackFull(SqStack S) {
	if(S.top==MaxSize-1)//由于c語言數(shù)組下標(biāo)從0開始的，即當(dāng)top=MaxSize-1時(shí)，此時(shí)棧滿。
		return true;
	else
		return false;
}

/*進(jìn)棧操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若棧已滿，則報(bào)錯(cuò)
		return false;
	++S.top;//top指針始終指向棧頂，新的元素進(jìn)棧，所以指針先加1
	S.data[S.top]=x;//將進(jìn)棧元素的值傳入并入棧
	//S.data[++S.top]=x;
	return true;
}

/*出棧操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	x=S.data[S.top];//出棧
	S.top--;//指針減1
	//x=S.data[S.top--];
	return true;
}

/*讀取棧頂元素*/
bool StackGetTop(SqStack S,int &x) {
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	x=S.data[S.top];//x記錄棧頂元素
	return true;
}

/*棧的建立*/
void CreateStack(SqStack &S,int x) {
	int number;
	printf("請(qǐng)輸入要建立棧的元素個(gè)數(shù)：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("輸入第%d個(gè)入棧的元素：\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	}
}

/*棧的遍歷輸出*/
bool PrintStack(SqStack S,int x){
	if(S.top==-1)//若棧為空，則報(bào)錯(cuò)
		return false;
	while(S.top!=-1){
		x=S.data[S.top--];
		printf("%d ",x);
	}
	return true;
} 

/*主函數(shù)*/
int main() {
	SqStack S;
	int x;
	InitStack(S);//初始化
	CreateStack(S,x);//創(chuàng)建順序棧
	StackGetTop(S,x);//讀取棧頂元素
	printf("讀取棧頂元素,當(dāng)前棧頂元素為：%d\n",x);
	printf("從棧頂?shù)綏５椎脑兀ǔ鰲ｍ樞颍┮来螢椋?);
	PrintStack(S,x); //遍歷輸出棧中元素
}

運(yùn)行結(jié)果如下：
在這里插入圖片描述

原文鏈接：https://blog.csdn.net/qq_43085848/article/details/124575864