程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 數據結構（C實現）------- 鏈棧

數據結構（C實現）------- 鏈棧

編輯：關於C語言

數據結構（C實現）------- 鏈棧

描述：

鏈棧，即棧的鏈式存儲結構，鏈棧通常使用不帶頭結點的單鏈表來表示，因此其結點的結構和單鏈表的結點結構相同。

在一個鏈棧中，棧底就是鏈表的最後一個結點，而棧頂總是鏈表的第一個結點。因此，新入棧的元素即為鏈表中采用頭插法新加入的結點，一個鏈棧可以由棧頂指針唯一確定，當top為NULL時，則表示該棧是一個空的鏈棧。

實現：

鏈棧結點的類型描述：

typedef int ElemType;
typedef struct node{
	ElemType data;
	struct node *next;
}LinkNode,*LinkStack;

基本操作

1. 初始化鏈棧Init_LinkStack()

鏈棧的初始化操作就是創建一個不帶頭結點的空的單鏈表，如下：

//初始化鏈棧
LinkStack Init_LinkStack(){
	LinkStack S;
	S = NULL;
	return S;
}

2. 判斷鏈棧空IsEmpty_LinkStack(LinkStack top)

根據定義，當棧頂指針top為NULL時，表示該結點為一個空棧，返回1，否則，則返回0 。

//判斷鏈棧空
int IsEmpty_LinkStack(LinkStack top){
	if(top == NULL)
		return 1;
	else
		return 0;
}

3. 入鏈棧Push_SqStack(SqStack* S,ElemType x)

入棧，即向棧中插入一個元素作為新的棧頂元素，首先要動態申請一個結點作為新元素的存儲空間，然後將新數據元素寫入申請的存儲空間中，並將棧頂指針top的值寫入新結點中的指針域，最後將棧頂指針指向新插入的結點，代碼如下：

//入棧操作
void Push_SqStack(SqStack* S,ElemType x){
	//棧滿，則退出
	if(isFull_SqStack(S)){
		printf("棧滿!\n");
		exit(0);
	}
	else{
		S->data[++(S->top)] = x;
	}
}

4. 出鏈棧Pop_SqStack(SqStack* S,ElemType* x)
出棧，即從棧中輸出一個元素，並將其刪除，具體過程為：當棧頂元素出棧時，先判斷棧頂指針是否為空，如果空，則輸出提示信息並退出，否則，取出棧頂元素的值返回，然後，將棧頂指針向後移動，並且釋放掉被刪除棧頂元素的存儲空間。

//出棧
void Pop_SqStack(SqStack* S,ElemType* x){
	//如果棧空，則輸出提示信息，並退出
	if(isEmpty_SqStack(S)){
		printf("棧空!\n");
		exit(0);
	}
	else
		*x =  S->data[S->top--];
}

5. 讀取鏈棧頂元素Top_SqStack(SqStack* S,ElemType* x)

讀取鏈棧頂元素與出棧不同，二者的區別在於：讀取棧頂元素時，棧頂指針不發生變化，僅取得棧頂元素的值；而出棧則還要將棧頂元素刪除，在此時棧頂指針也要發生變化；但二者都要判斷棧是否為空。

//讀取棧頂元素
void Top_SqStack(SqStack* S,ElemType* x){
	if(isEmpty_SqStack(S)){
		printf("棧空!\n");
		exit(0);
	}
	else 
		*x = S->data[S->top];
}

6. 輸出棧中所有的元素Print_SqStack(SqStack* S)

從棧頂開始遍歷整個鏈棧，輸出所有的元素，同樣，需要判斷鏈棧是否為空。

//輸出整個棧
void Print_SqStack(SqStack* S){
	if(isEmpty_SqStack(S)){
		printf("棧空!\n");
		exit(0);
	}
	int length = S->top;
	while(length > -1)
		printf("%d\t",S->data[length--]);
	printf("\n");
}