天天看點
傳回

棧(Stack)的鍊式實作詳解----線性結構

前面已經學習了線性存儲的線性表操作，即元素之間的1對1之間的關系，如線性表的順序、鍊式的存儲和表示，就是資料元素之間的線性的一個表現。

除了線性表，以線性存儲的資料結構還有棧和隊列、串、數組和廣義表等。

今天主要為大家分享資料結構之中的很重要的一個資料結構，就是------>棧

怎樣了解 “棧” 呢？

棧在我們的生活中應用的非常廣泛，如平時我們炒菜做菜用的碟子，一般需要放的時候需要一個一個将盤子從下到上給放上去，而用的時候又需要從上到下一個一個給拿出使用。

又如我們所見的手槍的彈夾，我們對彈夾進行裝子彈的時候需要一顆顆地将子彈從上到下地摁下去，子彈射出時又會從下到上一個個将子彈彈出去等等，藝術來源于生活嘛，哈哈，生活中有太多棧的應用的執行個體，大家了解即可。

總結起來棧的特征就是後進先出(LIFO)。

與之對應是隊列的特征先進先出(FIFO)。

我們把從下往上進行增加元素的操作稱為---->壓棧操作

我們又把從上往下往外邊減少元素稱作為---->出棧操作

因為棧隻能從棧頂操作，即增加删除隻能從頂部操作，我們也把棧成為操作受限的線性表。

由于教材上已經有棧的順序實作，雖然是僞代碼(看着實在不習慣，哈哈)，然後我實作了棧的鍊式實作，提供給大家參考。

最後自己添加的以棧頂至棧底輸出所有元素(采用輔助棧)實作的，如果有其它小夥伴有其它想法，歡迎評論留言讨論~

文章目錄

          • 鍊式棧結構體的定義
          • 所有方法聲明
          • 初始化棧操作
          • push壓棧操作
          • pop出棧操作
          • 自頂向底列印所有元素
          • 自底向頂列印所有元素
          • 擷取棧頂元素
          • 擷取鍊式棧的長度
          • 銷毀棧、清空棧、判斷棧空操作
鍊式棧結構體的定義

簡單的棧内元素定義和鍊式棧定義

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

//定義棧記憶體儲的元素Student 
struct Student{	
	int id;				//學生id 
	int age;			//學生年齡 
	Student *next;		//指向下一進制素的指針 
};


//定義以鍊式存儲的資料棧 
typedef struct Node{	
	Student *base;		//定義棧底指針，用于指向棧底元素 
	Student *top;		//定義棧頂指針，用于指向棧頂元素, 它們初始化均為NULL 
}*Stack;
所有方法聲明 
int initStack(Stack &stack);						//初始化連結清單棧 
int clearStack(Stack &stack);						//清空棧内的所有資料 
int destroyStack(Stack &stack);						//銷毀連結清單資料棧 
int stackEmpty(Stack &stack);						//判斷連結清單棧是否為NULL 
int stackLength(Stack &stack);						//擷取棧長的函數 
int getStackTop(Stack &stack, Student &student);		//擷取棧頂元素 
int pushStack(Stack &stack, Student student);			//壓棧操作，将一個元素壓入棧中 
int popStack(Stack &stack, Student &student);			//出棧操作，将一個元素彈出棧，并以參數student傳回 
void printStack(Stack &stack);						//以棧頂到棧底的形式輸出棧内所有元素 
void stackTraverse(Stack &stack);					//以棧底到棧頂的形式輸出棧内所有元素
初始化棧操作

棧的初始化操作

//資料結構----初始化鍊式資料棧操作 
int initStack(Stack &stack)
{
	stack = (Node *)malloc(sizeof(Node));			//使用malloc函數動态為資料棧開辟空間 
	stack->base = NULL;					//棧底指針指向NULL 
	stack->top = NULL;					//棧頂指針指向NULL 
	
	return OK;					//傳回建棧成功資訊 
}
push壓棧操作

push壓棧操作，根據函數傳遞的參數将一個資料元素壓入棧中

//資料結構----push壓棧操作，将一個資料元素壓入棧中 
int pushStack(Stack &stack, Student student)
{
	Student *student1 = (Student *)malloc(sizeof(Student));		//動态開辟一個元素空間 
	
	student1->id = student.id;				//資訊收集，擷取将壓棧元素的id 
	student1->age = student.age;			//擷取将壓棧元素的age 
	
	if(stack->base == NULL)					//若棧底為NULL時，說明棧内還沒有元素 
	{
		stack->base = student1;			//棧底指向該元素student1 
		stack->top = student1;			//棧頂指向該元素student1 
	}
	else									//否則 
	{
		stack->top->next = student1; 		//将元素student1壓入棧中 
		stack->top = student1;				//棧頂指針指向新元素student1 
	}
	
	stack->top->next = NULL;		//設定下次待壓入元素的位址暫為NULL(與鍊式線性表的增加元素有些許類似) 
	
	return OK;
}
pop出棧操作

出棧操作，将棧頂元素進行彈出 ，并通過函數參數的方式儲存彈出的資訊供傳回

//資料結構----出棧操作，将棧頂元素進行彈出 
int popStack(Stack &stack, Student &student)
{
	Student *p = stack->base, *q;		//定義p指針暫時指向棧底元素 
	
	if(stackEmpty(stack)) return ERROR;		//若棧空則傳回失敗資訊 
	
	if(stack->top == stack->base)		//若棧頂指針和棧底指針指向同一進制素，表示棧内僅有一個元素 
	{
		student = *stack->top;			//以參數的形式儲存棧頂元素并傳回 
		free(stack->top);			//釋放棧頂元素，進行出棧删除 
		stack->base = NULL;				 
		stack->top = NULL;			//棧底、頂指針再次指向NULL，代表暫無任何元素 
		return OK;					//傳回成功資訊 
	}
	
	while(p->next != stack->top)		//若棧内的元素 >= 2
	p = p->next;					//p指針從棧底循環上挪 ，直到p指向指向棧頂元素之下的元素 
	
	q = stack->top;					//q指針指向棧頂元素					
	student = *q;					//将棧頂元素指派給參數student待傳回 
	stack->top = p;						//棧頂指針下挪 
	stack->top->next = NULL;			//設定下次待壓入元素的位址暫為NULL
	
	free(q);						//釋放原棧頂指針 
	return OK;							//傳回成功資訊 
	
}
自頂向底列印所有元素

采用輔助棧的方式自棧頂至棧底的方式輸出所有元素

//資料結構----自棧頂至棧底的方式輸出所有元素 
void printStack(Stack &stack)
{
	int i = 0;
	Stack new_stack; 
	initStack(new_stack);		//定義一個新的棧，并且進行初始化 
	
	Student student;			//定義元素變量student 
	printf("自棧頂到棧底的資料元素排列:\n");
	
	
	//stack出棧順序：			A、B、C、D、E	---->  結果：stack棧空 
	//同時new_stack壓棧順序： 	A、B、C、D、E	---->  結果：new_stack已儲存原stack棧 
	 
	while(!(stackEmpty(stack)))		//若原棧不為NULL，重複循環 
	{
		popStack(stack, student);  				 //出棧操作 
		printf("id = %d, age = %d.\n", student.id, student.age);	//資訊輸出 
		pushStack(new_stack, student);			 //壓棧操作 
		i++;							// 計數器累加 
	}
	printf("共有資料 %d 條.\n\n", i);		   	//輸出結果的個數 
	stack = new_stack;							//進行棧複制，原棧已恢複！ 
	return;						//傳回 
}
自底向頂列印所有元素 
//資料結構----自棧底至棧頂的方式輸出所有元素 
void stackTraverse(Stack &stack)
{
	int i = 0;
	Student *student = stack->base;					//定義随機變量指針student指向棧底元素 
	printf("自棧底到棧頂的資料元素排列:\n");
	while(student != NULL)							//循環周遊輸出 
	{
		printf("id = %d, age = %d.\n", student->id, student->age);
		student = student->next;				//指針随棧進行上挪輸出下一進制素 
		i++;								//計數器累加 
	}
	printf("共有資料 %d 條.\n\n", i);		//輸出累加資料 
	return;
}
擷取棧頂元素

擷取鍊式棧的棧頂元素

//資料結構----擷取棧頂元素 
int getStackTop(Stack &stack, Student &student)
{
	if(stack->top != NULL)					//若棧頂元素不為NULL 
	{
		student = *stack->top;				//将棧頂元素傳遞給參數變量 
		return OK;				//傳回成功資訊 
	}
	else return ERROR;			//否則傳回失敗資訊 
}
擷取鍊式棧的長度 
//資料結構----測試棧長函數 
int stackLength(Stack &stack)
{
	Student *student = stack->base;			//定義随機變量元素指向棧底元素 
	int i = 0;
	while(student != NULL)					//循環周遊統計 
	{
		student = student->next;			//不斷指向棧上層元素 
		i++;					//計數器累加 
	}
	
	return i;					//傳回長度 
}
銷毀棧、清空棧、判斷棧空操作 
//資料結構----銷毀鍊式資料棧操作 
int destroyStack(Stack &stack)
{
	clearStack(stack);			//清空資料棧内的所有元素 
	free(stack);				//釋放棧的位址空間記憶體 
	stack = NULL;				//設定棧指針為NULL，即銷毀
	return OK;					//傳回成功資訊 
}


//資料結構----清理鍊式資料棧 
int clearStack(Stack &stack)
{
	Student student;						//定義臨時元素變量Student 
	while(stack->base != NULL)				//當棧底指針不為NULL時，循環進行出棧操作 
	popStack(stack,student);			//元素出棧 
	
	if(stack->base == NULL) return OK;		//若棧底已為NULL，傳回成功資訊 
	else return ERROR;					//否則傳回失敗資訊 
}



//資料結構----判斷棧空函數 
int stackEmpty(Stack &stack)
{
	if(stack->base == NULL && stack->top == NULL)
		return TRUE;						//若棧底指針和棧頂指針指向NULL，傳回true 
	else	
		return FALSE;						//否則傳回false 
}

在這就不再寫這些方法的測試代碼了，小夥伴們可以自行參考交流，共同進步，最近也在學習高數和其它課程，可能會更新有點慢，哈哈，下次準備鍊式隊列的實作，加油~

計算機綜合基礎(408) # 資料結構 棧 連結清單
上一篇: 彈幕穿人技術實踐 — AI 在視訊領域的運用
下一篇: java 第六次實驗_作業系統第六次實驗報告——使用信号量解決哲學家進餐問題...

繼續閱讀