一.棧的定義

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

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

二.棧的特點

后進(jìn)先出

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

三.棧的理解

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

四.鏈棧引入

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

五.鏈棧定義

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

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

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

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

代碼如下：

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

七.鏈棧的基本操作

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

7.1鏈棧的初始化

鏈棧的初始化可以理解為構(gòu)造一個空棧，將棧頂指針top所指頭結(jié)點的指針域置為NULL，因為此時棧中還沒有數(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鏈棧入棧

入棧就是：

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

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

代碼如下：

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

7.4鏈棧出棧

出棧就是：

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

代碼如下：

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

7.5取棧頂元素

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

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

八.總結(jié)

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

（小白一位，如有錯誤歡迎指正）

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

最新評論