快捷導(dǎo)航

C語(yǔ)言深入刨析數(shù)據(jù)結(jié)構(gòu)之棧與鏈棧的設(shè)計(jì)與應(yīng)用

更新時(shí)間：2022年05月23日 09:58:24 作者：Mi ronin

棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom）。棧的最主要特點(diǎn)就是“先進(jìn)后出”（FILO），或“后進(jìn)先出”（LIFO）。用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱為“鏈棧”，鏈棧對(duì)應(yīng)于鏈表

一.棧的定義

棧是限定僅在表尾進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)（受到限制的線性表）。

我們把允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何元素為空棧。

二.棧的特點(diǎn)

后進(jìn)先出

比如word，瀏覽器網(wǎng)頁(yè)等一系列軟件中，都有撤銷的操作，就是利用棧的這種方式來(lái)實(shí)現(xiàn)的，可能不同軟件的代碼不同，但是他們的原理是一樣的均為：后進(jìn)先出。

三.棧的理解

棧是一個(gè)線性表，有前驅(qū)后繼關(guān)系，只不過(guò)這里的表尾指的是棧頂。
棧限制了線性表的插入和刪除位置，這也導(dǎo)致棧底是固定的。
棧的插入操作，叫做進(jìn)棧；可以理解為子彈入彈夾。
棧的刪除操作，叫做出棧；可以理解為子彈出彈夾。

四.鏈棧引入

既然棧是屬于線性表的一種，那么存儲(chǔ)結(jié)構(gòu)也就分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，這里我們著重講解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

五.鏈棧定義

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱鏈棧。

對(duì)于棧來(lái)說(shuō)，只在棧頂做插入和刪除操作，由于單鏈表有頭指針，棧頂指針也是必須的，那我們干脆就將頭指針和棧頂指針合二為一，將棧頂放在單鏈表的頭部。通常對(duì)于鏈棧是不需要頭結(jié)點(diǎn)的。

對(duì)于鏈棧來(lái)說(shuō)，一般不會(huì)存在棧滿的情況，如果這種事情真的發(fā)生，那么此時(shí)的計(jì)算機(jī)操作系統(tǒng)也將會(huì)面臨死機(jī)崩潰的情況，那就不單單是這個(gè)鏈棧是否溢出的問(wèn)題了。對(duì)于鏈表來(lái)說(shuō)，鏈表為空的表示是頭結(jié)點(diǎn)指向空，那么對(duì)于鏈棧來(lái)講，鏈棧為空就是棧頂指針指向空（top = NULL）。

六.鏈棧的結(jié)構(gòu)體設(shè)計(jì)

代碼如下：

// 鏈棧的存儲(chǔ)結(jié)構(gòu)
typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode,*LinkStack;

七.鏈棧的基本操作

對(duì)于鏈棧來(lái)說(shuō)作為線性表的一種，操作也就那么幾種，這里我們對(duì)以下幾種操作進(jìn)行詳解：初始化，判斷是否為空，入棧，出棧，取棧頂元素等。

7.1鏈棧的初始化

鏈棧的初始化可以理解為構(gòu)造一個(gè)空棧，將棧頂指針top所指頭結(jié)點(diǎn)的指針域置為NULL，因?yàn)榇藭r(shí)棧中還沒(méi)有數(shù)據(jù)元素。

代碼如下：

LinkedStack Init_LinkedStack()
{
	LinkedStack top = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));  
	                              //棧頂指針變量
	if(top != NULL)
	{
		top->next = NULL;
	}
	return top;
}

7.2鏈棧判空

判斷鏈棧是否為空，只需要判斷棧頂?shù)闹羔樣蚴欠裰赶蚩?，如果指向空則棧空，相反亦然。

bool LinkedStack_Empty(LinkedStack top)
{
	if(top->next == NULL)//如果棧頂?shù)闹羔樣蛑赶蚩?，則?？?
	{
		return True;
	}
	else
	{
		return False;
	}

7.3鏈棧入棧

入棧就是：

先對(duì)數(shù)據(jù)域進(jìn)行賦值；
然后讓新結(jié)點(diǎn)指向棧頂指針；
最后將棧頂指針交給新節(jié)點(diǎn)。

假設(shè)元素值為e的新節(jié)點(diǎn)是s，top為棧頂指針：

代碼如下：

int Push(LinkedStack *s  ,elemtype e)
{
	LinkedStackNode s= (LinkedStackNode )malloc(sizeof(LinkedStackNode));
 s->data=e;
 s->next=s->top;//把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼.
 s->top=s;//把新節(jié)點(diǎn)s賦值給棧頂指針
 s->cout++;
 return 1;
}

7.4鏈棧出棧

出棧就是：

將要?jiǎng)h除的元素的值交給臨時(shí)變量，將棧頂指針交給臨時(shí)節(jié)點(diǎn)；
將棧頂指針下移；最后釋放臨時(shí)節(jié)點(diǎn)（即完成刪除）。
假設(shè)變量p用來(lái)存儲(chǔ)要?jiǎng)h除的棧頂結(jié)點(diǎn)，將棧頂指針向下移一位，最后釋放p即可：

代碼如下：

int Pop_LinkedStack(LinkedStack *s,elemtype *e)
{
	LinkedStackNode *p;
	if(stackempty(*s))
		return error;
	*e=s->top->data;
	p=s->top;   //將棧頂結(jié)點(diǎn)賦值給p
	s->top=s->top->next;//使得棧頂結(jié)點(diǎn)指針下移一位，指向后一結(jié)點(diǎn)
	free(p);//釋放結(jié)點(diǎn)
	s->count--;	
	return 1;
	}
}

7.5取棧頂元素

讀取棧頂元素，并返回其值，該操作與出棧的區(qū)別是棧頂元素并不刪除，所以不用修改頭結(jié)點(diǎn)的指針域即可。

int Get_LinkedStack(LinkedStack top,elemtype *x)
{
	if(top->next == NULL)
	{
		return 0;
	}
	else
	{
		*x = top->next->data;
		return 1;
	}
}

八.總結(jié)

對(duì)比順序棧和鏈棧，如果棧的使用過(guò)程中元素變化不可預(yù)料，有時(shí)小，有時(shí)大，那么最好用鏈棧；反之，如果他的變化在可控范圍之內(nèi)建議使用順序棧會(huì)更好點(diǎn)。

（小白一位，如有錯(cuò)誤歡迎指正）

到此這篇關(guān)于C語(yǔ)言深入刨析數(shù)據(jù)結(jié)構(gòu)之棧與鏈棧的設(shè)計(jì)與應(yīng)用的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧與鏈棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: