数组、链表、队列和栈----链表实现栈，C语言实现

秒速五厘米 2023-03-01 05:56 22阅读 0赞

下面我们用链表实现栈：

声明结点的结构体

struct Node{
        
    	int num; //具体数据 
    	struct Node * next; //指向下一个结点的指针 
    };
    
    struct Node head; //普通的结构体变量：头结点

结构体的指针变量：指向链表的尾结点。

struct Node *top = &head; //初始值为head的地址

需要实现几个方法：

0、依次显示所有数据
    void show() //遍历，其实栈不需要这个功能 
    {
        
    	struct Node *currentNode; //当前结点的指针
    	currentNode = head.next; //当前结点的指针指向head结点的下一个结点 
    	
    	while(currentNode != NULL) //遍历 
    	{
        
    		printf("%d, ", currentNode->num); //输出结点信息 
    		currentNode = currentNode->next; //跳转到下一个结点 
    	}
    	printf("\r\n");
    }
    
    1、读取栈顶元素，(不出栈)
    void peek()
    {
        
    	if(head.next == NULL)
    	{
        
    		printf("栈为空\r\n");
    		return;
    	}
    	
    	printf("栈顶元素: %d\r\n", top->num);
    } 
    
    2、入栈：在栈的top插入一个数，时间复杂度为O(1)
    void push(int n) //在链表的指定位置插入新节点
    {
        
    	//向操作系统申请一段内存空间，并强制转化成node的指针 
    	struct Node * node = (struct Node *)(malloc(sizeof(struct Node)));
    	node->num = n; //为node结点赋值 
    	node->next = NULL; //为node结点赋值 
    
    	top->next = node; //更换currentNode的next结点。也就是插入操作 
    	top = node;
    	head.num++;//head结点的num表示这个链表一共有几个结点
    }
    
    2.1、在栈的top插入一个数，时间复杂度为O(N) 
    void push2(int n) //在链表的指定位置插入新节点
    {
        
    	//向操作系统申请一段内存空间，并强制转化成node的指针 
    	struct Node * node = (struct Node *)(malloc(sizeof(struct Node)));
    	node->num = n; //为node结点赋值 
    	node->next = NULL; //为node结点赋值 
    	
    	struct Node * currentNode; //当前结点的指针 
    	currentNode = &head; //当前结点的指针指向head结点 
    	struct Node * temp; //临时结点的指针
    	
    	while(currentNode->next != NULL) //遍历到最后一个节点 
    	{
        
    		currentNode = currentNode->next;
    	}
    	
    	currentNode->next = node; //更换currentNode的next结点。也就是插入操作 
    	head.num++;//head结点的num表示这个链表一共有几个结点
    }
    
    3、出栈：时间复杂度为O(N) 
    int pop() //删除链表的顶元素 (不是head结点)
    {
        
    	struct Node * currentNode; //当前结点的指针 
    	currentNode = &head; //当前结点的指针指向head结点 
    	struct Node * temp; //临时结点的指针
    	
    	//遍历到倒数第二个节点
    	while(currentNode->next != NULL && currentNode->next->next != NULL)  
    	{
        
    		currentNode = currentNode->next;
    	}
    	
    	temp = currentNode->next; //temp记录最后一个结点 
    	int num = temp->num; //num记录最后一个结点的数据 
    	
    	currentNode->next = NULL; //不能出现野指针 
    	free(temp);//回收内存 
    	head.num--;//head结点的num表示这个链表一共有几个结点
    	
    	top = currentNode; //更新top指针 
    	return num; //返回最后一个结点的数据 
    }
    
    int getSize() //获得链表中的结点个数 
    {
        
    	return head.num;
    } 
    
    void release() //释放内存 
    {
        
    	struct Node * temp; //结点的临时指针
    	
    	while(head.next != NULL) //当head结点的next不为NULL时循环 
    	{
        
    		temp = head.next; //用temp记录head结点的子节点
    		head.next = head.next->next; //删除head结点的子节点
    		free(temp); //回收内存 
    	}
    }

总的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    //声明结点的结构体 
    struct Node{
        
    	int num; //具体数据 
    	struct Node * next; //指向下一个结点的指针 
    };
    
    struct Node head; //普通的结构体变量：头结点
    
    //结构体的指针变量：指向链表的尾结点。 
    struct Node *top = &head; //初始值为head的地址 
    
    //0、依次显示所有数据
    void show() //遍历，其实栈不需要这个功能 
    {
        
    	struct Node *currentNode; //当前结点的指针
    	currentNode = head.next; //当前结点的指针指向head结点的下一个结点 
    	
    	while(currentNode != NULL) //遍历 
    	{
        
    		printf("%d, ", currentNode->num); //输出结点信息 
    		currentNode = currentNode->next; //跳转到下一个结点 
    	}
    	printf("\r\n");
    }
    
    //1、读取栈顶元素，(不出栈)
    void peek()
    {
        
    	if(head.next == NULL)
    	{
        
    		printf("栈为空\r\n");
    		return;
    	}
    	
    	printf("栈顶元素: %d\r\n", top->num);
    } 
    
    //2、入栈：在栈的top插入一个数，时间复杂度为O(1)
    void push(int n) //在链表的指定位置插入新节点
    {
        
    	//向操作系统申请一段内存空间，并强制转化成node的指针 
    	struct Node * node = (struct Node *)(malloc(sizeof(struct Node)));
    	node->num = n; //为node结点赋值 
    	node->next = NULL; //为node结点赋值 
    
    	top->next = node; //更换currentNode的next结点。也就是插入操作 
    	top = node;
    	head.num++;//head结点的num表示这个链表一共有几个结点
    }
    
    //2.1、在栈的top插入一个数，时间复杂度为O(N) 
    void push2(int n) //在链表的指定位置插入新节点
    {
        
    	//向操作系统申请一段内存空间，并强制转化成node的指针 
    	struct Node * node = (struct Node *)(malloc(sizeof(struct Node)));
    	node->num = n; //为node结点赋值 
    	node->next = NULL; //为node结点赋值 
    	
    	struct Node * currentNode; //当前结点的指针 
    	currentNode = &head; //当前结点的指针指向head结点 
    	struct Node * temp; //临时结点的指针
    	
    	while(currentNode->next != NULL) //遍历到最后一个节点 
    	{
        
    		currentNode = currentNode->next;
    	}
    	
    	currentNode->next = node; //更换currentNode的next结点。也就是插入操作 
    	head.num++;//head结点的num表示这个链表一共有几个结点
    }
    
    //3、出栈：时间复杂度为O(N) 
    int pop() //删除链表的顶元素 (不是head结点)
    {
        
    	struct Node * currentNode; //当前结点的指针 
    	currentNode = &head; //当前结点的指针指向head结点 
    	struct Node * temp; //临时结点的指针
    	
    	//遍历到倒数第二个节点
    	while(currentNode->next != NULL && currentNode->next->next != NULL)  
    	{
        
    		currentNode = currentNode->next;
    	}
    	
    	temp = currentNode->next; //temp记录最后一个结点 
    	int num = temp->num; //num记录最后一个结点的数据 
    	
    	currentNode->next = NULL; //不能出现野指针 
    	free(temp);//回收内存 
    	head.num--;//head结点的num表示这个链表一共有几个结点
    	
    	top = currentNode; //更新top指针 
    	return num; //返回最后一个结点的数据 
    }
    
    int getSize() //获得链表中的结点个数 
    {
        
    	return head.num;
    } 
    
    void release() //释放内存 
    {
        
    	struct Node * temp; //结点的临时指针
    	
    	while(head.next != NULL) //当head结点的next不为NULL时循环 
    	{
        
    		temp = head.next; //用temp记录head结点的子节点
    		head.next = head.next->next; //删除head结点的子节点
    		free(temp); //回收内存 
    	}
    }
    
    int main()
    {
        
    	printf("入栈1~5\r\n");
    	for(int i = 1; i <= 5; i++)
    	{
        
    		push(i); //入栈
    	}
    	
    	printf("显示所有数据：");
    	show(); //依次显示所有数据
    		
    	printf("出栈: %d\r\n", pop());
    	printf("出栈: %d\r\n", pop());
    	peek(); //查看当前栈顶元素 
    	
    	push(6); //入栈
    	printf("入栈6, 显示所有数据：");
    	show(); 
    	
    	printf("一共有几个元素: %d\r\n", getSize());
    	
    	printf("显示所有数据: ");
    	show(); //依次显示所有数据
    	
    	release(); //释放内存 
    	return 0;
    }

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
如果一次性入栈15个元素，结果会是怎么样？跟预料的一样，没有任何问题。不出现满栈的情况。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]出栈时，我们需要从head开始遍历，找到倒数第二个结点，然后才能删除最后一个结点。这样做的时间复杂度为O(N)。如果我们能把栈做成双向链表，可以根据最后一个结点直接得到倒数第二个结点，出栈的时间复杂度可以降低为O(1)。这个双向链表就请读者自己实现吧。

下面我们总结一下用数组和链表实现的栈的性能和问题：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 2]

## 4 本章总结 ##

数组和链表是两种最基本的数据结构，所有的算法都需要在一定的数据结构上才能实现。队列和栈就是两个例子。队列和栈的对比如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 3]本章实现的链表、队列和栈都是最基本的形式，有更多高级形式希望读者能自己实现。另外，在扩展篇中，我们还将学习“优先级队列”，这种数据结构的入列方式跟普通队列一样，但是它是按照优先级高低出列的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/dfabf54bf74c48d5ba402767c6ba1454.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200722153058440.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200722153132869.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200722153210129.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70