Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

数据结构七：线性表之链式栈的设计

作者：Cpp五条 | 2024-04-28 08:10:04

踩

数据结构七：线性表之链式栈的设计

在上篇博客，学习了用数组实现链的顺序存储结构，那是否存在用单链表实现栈的链式存储结构，答案是当然的，相比于顺序栈，用数组实现的栈效率很高，但若同时使用多个栈，顺序栈将浪费很多空间。用单链表来实现栈可避免这个问题，其代价是要为每个栈元素分配一个额外的指针空间（存放指针域），本篇博客详细总结用链表实现栈的链式存储结构，我们称之为链式栈。

一、链式栈的接口函数实现

1.0 链式栈的概念和结构

1.0.0 链式栈的概念

链式栈，即用链表实现栈式存储结构。为保证栈的数据元素的后进先出的高效性，那么我们将栈顶应该设计在数组的哪一端呢？学过单链表，我们可以知道，单链表的头插和头删的效率非常高，时间复杂度为O(1)，因此，参考单链表，我们可以将栈顶设计为第一个有效结点，这样入栈和出栈的时间复杂度都可以达到O(1)。

1.0.1 链式栈结构体设计

经过上面的分析，我们知道，链式栈就是将栈顶设计为第一个有效结点的单链表，本质上就是只能进行头插和头删的单链表，本质和单链表的设计差不多，主要为2个成员，数据域和指针域。在之前的单链表中，我们把头结点和有效结点设计为一样的结构，浪费掉头结点的数据域，因此只设计成一个结构体类型，在链式栈这里，为了巩固练习，我们将头结点和有效结点分开设计，并且使用头结点的数据域，用来存放链式栈的有效元素个数，因此结构如下：


typedef int ELEM_TYPE;
 
//有效结点的设计：数据域和指针域
typedef struct Stack_Node
{
	ELEM_TYPE data;
	struct Stack_Node *next;
}Stack_Node, *PStack_Node;
 
 
//头结点的设计：存放有效结点个数的数据域和指针域
typedef struct Link_Stack
{
	int count;
	struct Stack_Node *top;
}Link_Stack, *PLink_Stack;

1.1 链式栈的接口函数

链式栈的基本操作有：初始化，头插，尾插，按位置插，头删，尾删，按位置删，查找，按值删，获取有效值个数，判空，清空，销毁，打印。这里详细展示这些基本操作的实现思想和画图分析以及代码实现和算法效率分析，

注意：链式栈与单链表相同，由于它是按需索取，因此，不需要进行判满和扩容操作；


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "stack_list.h"
 
 
//初始化
void Init_stack_list(struct Link_Stack* lst);
 
//入栈
void Push_list(struct Link_Stack* lst, ELEM_TYPE val);
 
//出栈
void Pop_list(struct Link_Stack* lst);
 
//获取栈顶元素值
ELEM_TYPE Top_list(struct Link_Stack* lst);
 
//获取有效元素个数
int Get_length_list(struct Link_Stack* lst);
 
//判空
bool IsEmpty_list(struct Link_Stack* lst);
 
 
//打印
void Show_list(struct Link_Stack* lst);
 
//清空
void Clear_list(struct Link_Stack* lst);
 
//销毁
void Destroy_list(struct Link_Stack* lst);

1.2 链式栈的初始化

链式栈在创建以后必须要进行初始化，否则内部为随机值，无法使用。链式栈的初始化主要是对结构体成员赋初值。


//初始化
void Init_stack_list(struct Link_Stack* lst)
{
    第0步：传入的指针参数检测
	assert(lst!=NULL);
 
    第1步：对指针域赋初值，数据域赋初值
	lst->top = NULL;
    lst->count = 0;   //头结点的数据域使用，最开始没有有效结点，赋初值为0
 
}

1.3 入栈（相当于单链表的头插）

入栈相当于是单链表的头插，基本思路如下：

第0步：assert对传入的指针检测；

第1步：购买新节点（购买好节点之后，记得将val值赋值进去）；

第2步：找到合适的插入位置；

第3步：插入，注意核心代码，先牵右手，再牵左手！！！否则会发生内存泄漏。


//入栈
void Push_list(struct Link_Stack* lst, ELEM_TYPE val)
{
	第0步：传入的指针参数检测
	assert(lst!=NULL);
 
	//1.购买新节点
	struct Stack_Node* pnewnode = (struct Stack_Node *)malloc(1*sizeof(struct Stack_Node));
	pnewnode->data = val;
 
	//2.找到合适的插入位置 头插不用管
	
	//3.插入
	pnewnode->next = lst->top;
	lst->top = pnewnode;
	lst->count++;
}

1.4 出栈（相当于单链表的头删）

出栈相当于单链表的头删操作，对于删除操作，则需要对链表进行判空操作！并且删除操作遵循基本同样的4个步骤，需要理解加记忆。删除操作的基本思路如下：

①:用指针q指向待删除节点；
②:用指针p指向待删除节点的前驱节点；(头删的话，这里p可以被plist代替)
③:跨越指向；
④:释放待删除节点。


//出栈
void Pop_list(struct Link_Stack* lst)
{
	第0步：传入的指针参数检测
	assert(lst!=NULL);
 
	//1.判空
	if(IsEmpty_list(lst))
	{
		return;
	}
 
	//2.用q指向待删除节点， 用p指向待删除节点的上一个节点
	struct Stack_Node *q = lst->top;
 
	//3.跨越指向+释放 count--
	lst->top = q->next;
	free(q);
	q = NULL;
	lst->count--;
 
}

1.5 获取栈顶元素值

链式栈中，栈顶就是第一个有效结点，因此只需要返回第一个有效结点的数据域即可。


 
//获取栈顶元素值
ELEM_TYPE Top_list(struct Link_Stack* lst)
{
    第0步：传入的指针参数检测
	assert(lst!=NULL);
    
    第1步：判空
	if(IsEmpty_list(lst))
	{
		exit(1);
	}
 
    第2步：直接返回第一个有效结点的数据域
	return lst->top->data;
}

1.6 获取有效元素个数

头结点的数据域就是用来记录有效结点个数的，直接返回即可


//获取有效元素个数
int Get_length_list(struct Link_Stack* lst)
{
     第0步：传入的指针参数检测
	 assert(lst!=NULL);
    
     第1步：头结点的数据域就是用来记录有效结点个数的，直接返回即可
	 return lst->count;
}

1.7 判空

直接判断头结点的指针域是否为空即可！


//判空
bool IsEmpty_list(struct Link_Stack* lst)
{
     第0步：传入的指针参数检测
	 assert(lst!=NULL);
   
    第1步：没有有效结点时，头结点的指针域为空
	return lst->top == NULL;
}

1.8 打印

直接从第一个有效节点开始，从前往后遍历，打印有效结点的数据域即可


//打印
void Show_list(struct Link_Stack* lst)
{
    第0步：传入的指针参数检测
	assert(lst!=NULL);
    
    第1步：直接从第一个有效节点开始，从前往后遍历，打印有效结点的数据域即可
	struct Stack_Node *p = lst->top;
	for(; p!=NULL; p=p->next)
	{
		printf("%d ", p->data);
	}
 
	printf("\n");
}

1.9 清空

链式栈和单链表一样，清空和销毁完全一样


//清空
void Clear_list(struct Link_Stack* lst)
{
	Destroy_list(lst);
}

1.10 销毁

链式栈的销毁同样有两种方式，这里只写第2种即可。


//销毁
void Destroy_list(struct Link_Stack* lst)
{
    第0步：传入的指针参数检测
	assert(lst!=NULL);
 
    第1步：利用双指针，依次从前往后删除
	struct Stack_Node *q = lst->top;
	struct Stack_Node *p = NULL;
 
	lst->count = 0;
	lst->top = NULL;
 
	while(q != NULL)
	{
		p = q->next;
		free(q);
        q=NULL;
		q = p;
	}
}

二、总结

从以上分析，我们可以知道链式栈只是单链表的一种特殊情况，限定了数据元素的插入和删除位置，链式栈是一种基于单链表实现的栈，在空间复杂度上，顺序栈在创建时就申请了数组空间，若栈经常处于不满状态将造成存储空间的浪费；链式栈所需空间是根据需要随时申请的，比之顺序栈仅仅是其每个结点需要额外的空间以存储其next指针域。在时间复杂度上，对于针对栈顶的基本操作（压入、弹出和栈顶元素存取），容易看出，顺序栈和链式栈的时间复杂性均为O(1) 。

它具有一些优点：

动态性能好： 链式栈采用链式存储结构，可以动态地分配内存空间，而顺序栈则需要预先分配一定大小的连续内存空间。因此，链式栈能够根据实际需求动态扩展或缩减内存，不会受到固定大小的限制。

灵活性强： 由于链式栈的内存空间是动态分配的，因此在入栈和出栈操作时不需要移动元素，而是通过修改指针来实现。这使得链式栈的操作效率更高，并且不会出现栈满的情况，避免了顺序栈可能出现的溢出问题。

以上便是我为大家带来的链式栈设计内容，若有不足，望各位大佬在评论区指出，谢谢大家！下一节继续进行链式栈的内容，感兴趣的你可以留下你们的点赞、收藏和关注，这是对我极大的鼓励，我也会更加努力创作更优质的作品。再次感谢大家！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/501226