一.棧的定義

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

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

二.棧的特點(diǎn)

后進(jìn)先出

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

三.棧的理解

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

四.鏈棧引入

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

五.鏈棧定義

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

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

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

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

代碼如下：

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

七.鏈棧的基本操作

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

7.1鏈棧的初始化

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

代碼如下：

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

7.2鏈棧判空

判斷鏈棧是否為空，只需要判斷棧頂?shù)闹羔樣蚴欠裰赶蚩眨绻赶蚩談t?？眨喾匆嗳?。

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用來存儲(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ì)比順序棧和鏈棧，如果棧的使用過程中元素變化不可預(yù)料，有時(shí)小，有時(shí)大，那么最好用鏈棧；反之，如果他的變化在可控范圍之內(nèi)建議使用順序棧會(huì)更好點(diǎn)。

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

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

最新評(píng)論