一.棧的定義

棧是限定僅在表尾進行插入和刪除操作的數據結構（受到限制的線性表）。

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

二.棧的特點

后進先出

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

三.棧的理解

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

四.鏈棧引入

既然棧是屬于線性表的一種，那么存儲結構也就分為順序存儲和鏈式存儲，這里我們著重講解鏈式存儲結構。

五.鏈棧定義

棧的鏈式存儲結構，簡稱鏈棧。

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

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

六.鏈棧的結構體設計

代碼如下：

// 鏈棧的存儲結構
typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode,*LinkStack;

七.鏈棧的基本操作

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

7.1鏈棧的初始化

鏈棧的初始化可以理解為構造一個空棧，將棧頂指針top所指頭結點的指針域置為NULL，因為此時棧中還沒有數據元素。

代碼如下：

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

7.2鏈棧判空

判斷鏈棧是否為空，只需要判斷棧頂的指針域是否指向空，如果指向空則棧空，相反亦然。

bool LinkedStack_Empty(LinkedStack top)
{
	if(top->next == NULL)//如果棧頂的指針域指向空，則棧空
	{
		return True;
	}
	else
	{
		return False;
	}

7.3鏈棧入棧

入棧就是：

• 先對數據域進行賦值；
• 然后讓新結點指向棧頂指針；
• 最后將棧頂指針交給新節點。

假設元素值為e的新節點是s，top為棧頂指針：

代碼如下：

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

7.4鏈棧出棧

出棧就是：

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

代碼如下：

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

7.5取棧頂元素

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

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

八.總結

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

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