C语言数据结构之栈(链表实现)

深碍√TFBOYSˉ_ 2022-11-26 09:51 251阅读 0赞

## 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;
    }

实现结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70]  
栈的操作到目前来说已经实现，希望对大家学习有所帮助，加油！

--------------------

tips：瞄准天上的星星，或许你永远也射不到，但却比你瞄准树梢射得高远。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70]: /images/20221124/d2c9b938e7d7422cb6bd5b0766db61aa.png