C語言數據結構之棧(鏈表實現)

tips:前些天學習了單鏈表的增刪改查，對於雙向鏈表和回圈鏈表而言，無非就是對單鏈表的指針進行稍微的變換。今天來看看c語言數據結構之棧的實現以及棧的各種操作。

棧的特點是先進後出，後進先出，因此我們很容易聯想到去使用單鏈表的頭插法，和頭部刪除法去實現入棧和出棧的操作。

首先我們來看一下棧的各種操作的實現思路以及具體實現過程
準備工作：

建立棧中元素的結構體

typedef struct tag 
{
	int val;//棧(鏈表)的值，即數據域部分
	struct  tag *pNext;//後繼指針
}Node,*pNode;

建立棧的結構體

typedef struct tagStack
{
	pNode phead;//鏈表(tag)的頭指針
	int size;//棧的大小（棧中元素個數）
}Stack,*pStack;

準備列印輸出函數

//列印棧元素
void print_stack(pStack p)
{
	pNode pcur = p->phead;//工具人儲存當前結點資訊
	while (pcur!=NULL)
	{
		printf("%d\n",pcur->val);
		pcur = pcur->pNext;
	}

	printf("---------------------------------\n");
}

1、入棧(push)
思路：

爲鏈表建立新結點，並將其初始化；
採用頭插法爲鏈表新增新結點入棧；
入棧操作完成後，將棧的size+1；

具體實現：

//入棧
void push(pStack p, int val)
{
	pNode pnew = (pNode)malloc(sizeof(Node));//申請新結點空間(申請的是tag)

	//新結點初始化
	pnew->val = val;
	pnew->pNext = NULL;

	//入棧，頭插法
	if (p->phead == NULL)//判斷鏈表是否爲空,爲空，頭指針指向新結點
	{
		p->phead = pnew;
	}
	else //不爲空，則頭插法
	{
		//新結點變成新的頭結點
		pnew->pNext = p->phead;
		p->phead = pnew;
	}
	p->size++;
}

2、出棧(pop)
思路：

採用頭部刪除法，刪除鏈表第一個結點（即棧頂元素），完成出棧；
出棧操作完成後，將棧的size-1；

具體實現：

//出棧,頭部刪除法
void pop(pStack p)
{
	pNode pcur = p->phead;//工具人儲存當前結點資訊
	//判斷鏈表是否爲空
	if (p->phead == NULL)
	{
		printf("該鏈表爲空!\n");
	}
	else
	{
		//頭部刪除法
		p->phead = pcur->pNext;
		free(pcur);
		p->size--;
	}
}

3、返回棧頂元素(top)
思路：

當棧爲空時直接返回EOF；
當棧不爲空時，直接返回鏈表頭結點的val（即棧頂元素的值）；

具體實現：

//返回棧頂元素
int top(pStack p)
{
	//判斷鏈表是否爲空
	if (p->phead == NULL)
	{
		return EOF;
	}
	else
	{
		//返回棧頂元素
		return p->phead->val;
	}

}

4、判斷棧是否爲空(empty)
思路：

當鏈表頭指針爲空時，棧即爲空；
（或者）當棧的size==0時，棧爲空；

總之判斷方法很多，大家可以盡情發揮。

具體實現：

//判斷棧是否爲空
int empty(pStack p)
{
	//判斷鏈表是否爲空
	if (p->phead == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

5、返回棧中元素個數(size)
思路：

當鏈表爲空時，返回0；
當鏈表不爲空時，返回棧的size；

這個實現方法很多，大家可以盡情發揮。

具體實現：

//返回棧中元素個數
int size(pStack p)
{
	//判斷鏈表是否爲空
	if (p->phead == NULL)
	{
		return 0;
	}
	else
	{
		return p->size;
	}
}

至此棧的基本操作我們已經全部實現了，接下來我們在main()函數中測試一下：

int main()
{
	//棧的操作，鏈表實現棧stack
	
	Stack s;//定義一個棧
	int i;//入棧的值
	char panduan;//用來判斷是否彈棧

	//使用memset初始化結點（棧）
	memset(&s, 0, sizeof(Stack));//棧的初始化,初始化爲0

	while (scanf("%d", &i) != EOF)
	{
		//入棧
		push(&s, i);		
	}
	//列印棧元素
	printf("棧裏面元素爲：\n");
	print_stack(&s);

	//列印棧頂元素
	printf("棧頂元素爲：%d\n", top(&s));

	//判斷棧是否爲空
	if (empty(&s))
	{
		printf("棧不爲空！\n");
	}
	else
	{
		printf("棧爲空！\n");
	}
	//棧中元素個數
	printf("棧中元素個數爲：%d\n", size(&s));

	printf("---------------------------------\n");

	while (printf("是否彈棧？y/n："),scanf("%c", &panduan) != NULL)
	{
		if (panduan == 'y')
		{
			//出棧
			pop(&s);

			//列印棧元素
			print_stack(&s);


			//列印棧頂元素
			printf("棧頂元素爲：%d\n", top(&s));

			//判斷棧是否爲空
			if (empty(&s))
			{
				printf("棧不爲空！\n");
			}
			else
			{
				printf("棧爲空！\n");
			}
			//棧中元素個數
			printf("棧中元素個數爲：%d\n", size(&s));

			printf("---------------------------------\n");
		}
		else if(panduan == 'n')
		{
			break;
		}
	
	}

	return 0;
}

實現結果：

在这里插入图片描述
棧的操作到目前來說已經實現，希望對大家學習有所幫助，加油！

tips：瞄準天上的星星，或許你永遠也射不到，但卻比你瞄準樹梢射得高遠。