一、棧的相關知識

• 棧是一種只允許在一端進行插入或刪除操作的線性表，它是一種特殊的線性表，其遵循的原則是先進后出（FILO），即后進的元素先被取出來。由于它是一種線性表，所以有兩種方式：順序存儲結構和鏈式存儲結構表示，即順序棧和鏈式棧。

其中，棧的插入操作稱為進棧，棧的刪除操作稱為出棧。

二、順序棧的定義

通過一組數組地址的連續的存儲單元來存放從棧底開始至棧頂的數據元素，同時設置一個棧頂指針top，用于指示當前棧頂元素的位置，代碼如下：

#define MaxSize 20//可自行設置
typedef struct {
	int data[MaxSize];//存放棧中元素 ，使用數組
	int top;//棧頂指針 ，記錄棧頂元素的位置 
} SqStack;//順序棧的類型定義 

我們可以得到，由于c語言中數組的下標是從0開始的，所以棧的總長度為S.top+1，即要加1。

三、順序棧的初始化

初始化一個順序棧，這里的參數SqStack &S，帶有“&”，表示引用調用，即對參數的修改結果進行帶回，棧頂指針為S.top，棧頂元素的值為S.data[S.top]，初始化時定義S.top=-1表示順序棧為空，而當S.top=0時，表示棧中只存在一個元素，代碼如下：

/*順序棧的初始化，初始化一個空棧*/
void InitStack(SqStack &S) {
	S.top=-1;//順序棧為空
}

四、判斷順序棧是否為空棧

可以得到，判斷順序棧是否為空棧的條件是S.top==-1，表示此時順序棧中為空棧，無任何元素，代碼如下：

/*判斷順序棧是否為空*/
bool StackEmpty(SqStack S) {
	if(S.top==-1)//當top=-1時，棧為空，而并不是S.top=0（它表示的是棧中有一個元素）.
		return true;
	else
		return false;
}

五、判斷順序棧是否為滿棧

判斷順序棧是否為空棧的條件是S.top==MaxSize-1，由于c語言數組下標從0開始的，棧中元素最大個數MaxSize要減1，即當top=MaxSize-1時，表示此時順序棧中已滿，無法再存入元素，代碼如下：

/*判斷順序棧是否為滿棧*/
bool StackFull(SqStack S) {
	if(S.top==MaxSize-1)//由于c語言數組下標從0開始的，即當top=MaxSize-1時，此時棧滿。
		return true;
	else
		return false;
}

六、進棧（插入操作）

將一個元素插入順序棧中，即進棧，由于進棧后元素個數有變化，所以要用引用“&”，即SqStack &S，首先判斷順序棧是否已滿，然后在新的元素進棧前，所以棧頂指針要先加1，即++S.top，然后將進棧元素的值傳入并將其入棧，如下：

++S.top;//top指針始終指向棧頂，新的元素進棧，所以指針先加1
S.data[S.top]=x;//將進棧元素的值傳入并入棧

這兩行代碼也可以使用一行代碼：S.data[++S.top]=x直接替換。
進棧操作的完整代碼如下：

/*進棧操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若棧已滿，則報錯
		return false;
	++S.top;//top指針始終指向棧頂，新的元素進棧，所以指針先加1
	S.data[S.top]=x;//將進棧元素的值傳入并入棧
	//S.data[++S.top]=x;
	return true;
}

七、出棧（刪除操作）

將一個元素從順序棧中刪除，即出棧，由于棧的特性，只能先進后出，即從棧頂進行刪除操作然后依次，同樣出棧后元素個數有變化，所以要用引用“&”，即SqStack &S，首先判斷順序棧是否為空，元素出棧后（將棧頂元素賦給x），然后棧頂指針要減1，如下：

x=S.data[S.top];//出棧
S.top--;//指針減1

這兩行代碼也可以使用一行代碼：x=S.data[S.top--]直接替換。
出棧操作的完整代碼如下：

/*出棧操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若棧為空，則報錯
		return false;
	x=S.data[S.top];//出棧
	S.top--;//指針減1
	//x=S.data[S.top--];
	return true;
}

八、讀取順序棧頂元素

讀取順序棧頂元素，這里并沒有將棧頂元素取出（無出棧操作），首先判斷當前順序棧是否為空，然后通過x來記錄棧頂元素，如下：

/*讀取棧頂元素*/
bool StackGetTop(SqStack S,int &x) {
	if(S.top==-1)//若棧為空，則報錯
		return false;
	x=S.data[S.top];//x記錄棧頂元素
	return true;
}

九、順序棧的建立

順序棧的建立中輸入一個值代表要創建的棧的元素個數，然后通過一個for循環建立順序棧，其中使用到棧的進棧操作，每次向棧中插入元素，代碼如下：

/*棧的建立*/
void CreateStack(SqStack &S,int x){
	int number;
	printf("請輸入要建立棧的元素個數：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("輸入第%d個入棧的元素：\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	}
}

一個簡單的順序棧的基本實現例子

例如，創建一個順序棧，棧中元素從棧底到棧頂依次為1,2,3,4,5，第一步首先輸出當前棧頂元素；第二步通過用戶輸入一個要進棧的元素“6”，并輸出進棧后此時的棧頂元素；第三步通過執行一次出棧操作后，然后再輸出此時的棧頂元素。
實現代碼如下：

#include
#define MaxSize 20//可自行設置
typedef struct {
	int data[MaxSize];//存放棧中元素 ，使用數組
	int top;//棧頂指針 ，記錄棧頂元素的位置
} SqStack;//順序棧的類型定義

/*順序棧的初始化，初始化一個空棧*/
void InitStack(SqStack &S) {
	S.top=-1;//順序棧為空
}

/*判斷順序棧是否為空*/
bool StackEmpty(SqStack S) {
	if(S.top==-1)//當top=-1時，棧為空，而并不是S.top=0（它表示的是棧中有一個元素）.
		return true;
	else
		return false;
}

/*判斷順序棧是否為滿棧*/
bool StackFull(SqStack S) {
	if(S.top==MaxSize-1)//由于c語言數組下標從0開始的，即當top=MaxSize-1時，此時棧滿。
		return true;
	else
		return false;
}

/*進棧操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若棧已滿，則報錯
		return false;
	++S.top;//top指針始終指向棧頂，新的元素進棧，所以指針先加1
	S.data[S.top]=x;//將進棧元素的值傳入并入棧
	//S.data[++S.top]=x;
	return true;
}

/*出棧操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若棧為空，則報錯
		return false;
	x=S.data[S.top];//出棧
	S.top--;//指針減1
	//x=S.data[S.top--];
	return true;
}

/*讀取棧頂元素*/
bool StackGetTop(SqStack S,int &x) {
	if(S.top==-1)//若棧為空，則報錯
		return false;
	x=S.data[S.top];//x記錄棧頂元素
	return true;
}

/*棧的建立*/
void CreateStack(SqStack &S,int x) {
	int number;
	printf("請輸入要建立棧的元素個數：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("輸入第%d個入棧的元素：\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	}
}

/*主函數*/
int main() {
	SqStack S;
	int x,e;
	InitStack(S);//初始化
	CreateStack(S,x);//創建順序棧
	StackGetTop(S,x);//讀取棧頂元素
	printf("讀取棧頂元素,當前棧頂元素為：%d\n",x);
	printf("輸入一個要進棧的元素：");
	scanf("%d",&e);
	StackPush(S,e);//進棧
	StackGetTop(S,x);
	printf("讀取棧頂元素,當前棧頂元素為：%d\n",x);
	StackPop(S,x);//出棧
	StackGetTop(S,x);
	printf("執行一次出棧操作后,當前棧頂元素為：%d",x);
}

運行結果如下：

十、棧的遍歷輸出

首先判斷順序棧是否為空，然后通過while循環，當S.top!=-1時一直執行下去，每次輸出棧頂的元素，然后再減1，如下代碼：

/*棧的遍歷輸出*/
bool PrintStack(SqStack S,int x){
	if(S.top==-1)//若棧為空，則報錯
		return false;
	while(S.top!=-1){
		x=S.data[S.top--];
		printf("%d ",x);
	}
	return true;
} 

例如，下列代碼：

#include
#define MaxSize 20//可自行設置
typedef struct {
	int data[MaxSize];//存放棧中元素 ，使用數組
	int top;//棧頂指針 ，記錄棧頂元素的位置
} SqStack;//順序棧的類型定義

/*順序棧的初始化，初始化一個空棧*/
void InitStack(SqStack &S) {
	S.top=-1;//順序棧為空
}

/*判斷順序棧是否為空*/
bool StackEmpty(SqStack S) {
	if(S.top==-1)//當top=-1時，棧為空，而并不是S.top=0（它表示的是棧中有一個元素）.
		return true;
	else
		return false;
}

/*判斷順序棧是否為滿棧*/
bool StackFull(SqStack S) {
	if(S.top==MaxSize-1)//由于c語言數組下標從0開始的，即當top=MaxSize-1時，此時棧滿。
		return true;
	else
		return false;
}

/*進棧操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若棧已滿，則報錯
		return false;
	++S.top;//top指針始終指向棧頂，新的元素進棧，所以指針先加1
	S.data[S.top]=x;//將進棧元素的值傳入并入棧
	//S.data[++S.top]=x;
	return true;
}

/*出棧操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若棧為空，則報錯
		return false;
	x=S.data[S.top];//出棧
	S.top--;//指針減1
	//x=S.data[S.top--];
	return true;
}

/*讀取棧頂元素*/
bool StackGetTop(SqStack S,int &x) {
	if(S.top==-1)//若棧為空，則報錯
		return false;
	x=S.data[S.top];//x記錄棧頂元素
	return true;
}

/*棧的建立*/
void CreateStack(SqStack &S,int x) {
	int number;
	printf("請輸入要建立棧的元素個數：\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) {
		printf("輸入第%d個入棧的元素：\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	}
}

/*棧的遍歷輸出*/
bool PrintStack(SqStack S,int x){
	if(S.top==-1)//若棧為空，則報錯
		return false;
	while(S.top!=-1){
		x=S.data[S.top--];
		printf("%d ",x);
	}
	return true;
} 

/*主函數*/
int main() {
	SqStack S;
	int x;
	InitStack(S);//初始化
	CreateStack(S,x);//創建順序棧
	StackGetTop(S,x);//讀取棧頂元素
	printf("讀取棧頂元素,當前棧頂元素為：%d\n",x);
	printf("從棧頂到棧底的元素（出棧順序）依次為：");
	PrintStack(S,x); //遍歷輸出棧中元素
}

運行結果如下：