首页 > 其他分享 >栈的学习

栈的学习

时间：2024-04-25 21:23:03浏览次数：23  
标签：Head SeqStack return Next 学习 Manager 顺序

栈的学习

1. 基本概念

栈是一种逻辑结构，是特殊的线性表。特殊在：

  • 只能在固定的一端操作

只要满足上述条件，那么这种特殊的线性表就会呈现一种“后进先出”的逻辑，这种逻辑就被称为栈。栈在生活中到处可见，比如堆叠的盘子、电梯中的人们、嵌套函数的参数等等。

img

由于约定了只能在线性表固定的一端进行操作，于是给栈这种特殊的线性表的“插入”、“删除”，另起了下面这些特定的名称：

  • 栈顶：可以进行插入删除的一端
  • 栈底：栈顶的对端
  • 入栈：将节点插入栈顶之上，也称为压栈，函数名通常为push()
  • 出栈：将节点从栈顶剔除，也称为弹栈，函数名通常为pop()
  • 取栈顶：取得栈顶元素，但不出栈，函数名通常为top()

基于这种固定一端操作的简单约定，栈获得了“后进先出”的基本特性，如下图所示，最后一个放入的元素，最先被拿出来：

img

2. 存储形式

栈只是一种数据逻辑，如何将数据存储于内存则是另一回事。一般而言，可以采用顺序存储形成顺序栈，或采用链式存储形成链式栈。

- 顺序栈

顺序存储意味着开辟一块连续的内存来存储数据节点，一般而言，管理栈数据除了需要一块连续的内存之外，还需要记录栈的总容量、当前栈的元素个数、当前栈顶元素位置，如果有多线程还需要配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体之中：

struct seqStack
{
    datatype *data; // 顺序栈入口
    int size;       // 顺序栈总容量
    int top;        // 顺序栈栈顶元素下标
};
img

- 链式栈

链式栈的组织形式与链表无异，只不过插入删除被约束在固定的一端。为了便于操作，通常也会创建所谓管理结构体，用来存储栈顶指针、栈元素个数等信息：

// 链式栈节点
typedef struct node
{
    datatype data;
    struct node *next;
}node;

// 链式栈管理结构体
struct linkStack
{
    node *top; // 链式栈栈顶指针
    int  size; // 链式栈当前元素个数
};

3.栈的顺序存储实现

顺序栈的初始化

//创建顺序栈并对顺序栈进行初始化
SeqStack_t * SeqStack_Create(unsigned int size)
{
	//1.利用calloc为顺序栈的管理结构体申请一块堆内存
	SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));

if(NULL == Manager)
	perror("calloc memory for manager is failed");
	exit(-1); //程序异常终止
}

//2.利用calloc为所有元素申请堆内存
Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));

if (NULL == Manager->Bottom)
{
	perror("calloc memory for element is failed");
	free(Manager);
	exit(-1); //程序异常终止
}

//3.对管理顺序栈的结构体进行初始化（元素容量 + 最后元素下标）
Manager->Size = size;	//对顺序栈中的容量进行初始化
Manager->Top = -1;		//由于顺序栈为空，则最后元素下标初值为-1

return Manager;
}

入栈与出栈

//入栈
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
	//1.判断顺序栈是否已满
	if ( SeqStack_IsFull(Manager) )
	{
		printf("SequenceStack is Full!\n");
		return false;
	}

	//2.如果顺序栈有空闲空间，则把新元素添加到顺序栈顶
	Manager->Bottom[++Manager->Top] = Data;  //++必须写在前面
	//Manager->Top++;
	//Manager->Bottom[Manager->Top] = Data;
	return true;
}

//出栈
bool SeqStack_Pop(SeqStack_t *Manager)
{
	DataType_t temp=0;  //用于储存出栈的元素
	//1.判断顺序栈是否为空
	if ( SeqStack_IsEmpty(Manager) )
	{
		printf("SequenceStack is Empty!\n"); 
		return false;
	}
        
	//2.删除顺序栈的元素
	temp = Manager->Bottom[Manager->Top--];  //数据还残留在内存中，只是逻辑上被删除
	//Manager->Top--;
    return temp;	
}

摧毁与遍历

//遍历顺序栈的元素
void SeqStack_Print(SeqStack_t *Manager)
{
	for (int i = 0;i <= Manager->Top;i++)
	{
		printf("Stack Element[%d]=%d\n",i,Manager->Bottom[i]);
	}
}

//销毁顺序栈
void SeqStack_Destroy(SeqStack_t *Manager)
{
    //1.释放顺序栈中所有元素所占的堆内存
	free(Manager->Bottom);
	//2.释放顺序栈的管理结构体所占的堆内存
	free(Manager);
}

判断栈空间已满或空

//判断顺序栈是否已满
bool SeqStack_IsFull(SeqStack_t *Manager)
{
	return (Manager->Top + 1 == Manager->Size) ? true : false;
}

//判断顺序栈是否为空
bool SeqStack_IsEmpty(SeqStack_t *Manager)
{
	return (-1 == Manager->Top) ? true : false;
}

4.栈的链式存储实现（单向链表）

链式栈的初始化

//指的是链式栈中的元素的数据类型，用户可以根据需要进行修改
typedef int  DataType_t;

//构造记录链式栈LinkStackStack各项参数
typedef  struct LinkStack
{
    DataType_t Data;//栈中元素的数据
    struct LinkStack *Next;//指向下一个元素的指针

}LLStack_t;

//构造函数，用于初始化链式栈

//创建一个空链表，空链表应该有一个头结点,对链表进行初始化
LLStack_t *CreateEmptyLinkedList(void)
{
	//1.创建一个头结点并为头结点申请内存
        LLStack_t *Head = (LLStack_t *)calloc(1,sizeof(LLStack_t));
        if(Head == NULL)
        {
            perror("Calloc memory for Head is Failed");
            exit(-1);
        }
	//2.对头结点进行初始化，头节点是不存储有效内容的
    Head->Next = NULL;

    //3.把头结点的地址返回即可S
    return Head;
}

//创建新的结点，并对新结点进行初始化(数据域+指针域)
LLStack_t *CreateNewLinkedList(DataType_t Data)
{
    //1.申请一个结点的内存空间
    LLStack_t *NewNode = (LLStack_t *)calloc(1,sizeof(LLStack_t));
    if(NewNode == NULL)
    {
        perror("Calloc memory for Head is Failed");
        return NULL;
    }
    //2.对新结点的数据域和指针域进行初始化
    NewNode->Data = Data;
    NewNode->Next = NULL;
    //3.返回新结点的地址
    return NewNode;
}

入栈与出栈

//入栈
bool LinStack_Push(LLStack_t *Head, DataType_t Data)
{
    //1.创建一个新结点
    LLStack_t *NewNode = CreateNewLinkedList(Data);
    if(NewNode == NULL)
    {
        perror("CreateNewLinkedList is Failed");
        return false;
    }
    //2.判断链表是否为空，如果为空，则新结点直接插入到链表的头部
    if(Head->Next == NULL)
    {
        Head->Next = NewNode;
        return true;
    }
    //3.如果链表不为空，则新结点插入到链表的头部
    NewNode->Next = Head->Next;
    Head->Next = NewNode;
    return true;
}

//出栈
bool LinStack_Pop(LLStack_t *Head)
{
    //1.判断链表是否为空，如果为空，直接返回
    if(Head->Next == NULL)
    {
        return false;
    }
    //2.判断链表是否只有一个结点，如果只有一个结点，则直接删除该结点
    if(Head->Next->Next == NULL)
    {
        free(Head->Next);
        Head->Next = NULL;
        return true;
    }
    //3.如果链表有多个结点，则删除第一个结点
    LLStack_t *Phead = Head->Next;
    Head->Next = Phead->Next;
    Phead->Next = NULL;
    return true;
}

摧毁与遍历

//遍历链栈的元素
void LinStack_Print(LLStack_t *Head)
{
    //1.判断链表是否为空
    if(Head->Next == NULL)
    {
        printf("LinkStack is Empty\n");
        return;
    }
    //2.遍历链表
    LLStack_t *Phead = Head->Next;
    while(Phead != NULL)
    {
        printf("%d\n",Phead->Data);
        Phead = Phead->Next;
    }
}

//销毁链栈
void LinStack_Destroy(LLStack_t *Head)
{
    //1.判断链表是否为空
    if(Head->Next == NULL)
    {
        return;
    }
    //2.遍历链表，依次释放内存
    LLStack_t *Phead = Head->Next;
    while(Phead != NULL)
    {
        LLStack_t *Ptemp = Phead;
        Phead = Phead->Next;
        free(Ptemp);
    }
    //3.释放头结点的内存
    free(Head);
}

5.笔试题

设计一个进制转换程序，使用顺序栈设计一个把十进制数转换为十六进制数的接口，实现当通过键盘输入一个非负的十进制数，可以在终端输出对应的十六进制数。

/*****************************************************
  * @function_name  : DecimalToHexadecimal
  * @brief_         : 顺序栈实现十进制转十六进制
  * @param_         : 
  *                   SeqStack_t *Manager --> 顺序栈的管理结构体
  *            
  * @retval_        : 空
  * @date_          : 2024/04/25
  * @version_       : v1.0 
  * @note_          : None
  *******************************************************/
//10进制转16进制
void DecimalToHexadecimal(SeqStack_t *Manager)
{
	//输入十进制数
	printf("please input Decima number:");
    int Decimal=0;
	scanf("%d",&Decimal); 	
	int num;//记录每一位数
    //2.利用顺序栈进行10进制转16进制
	do
	{ 	
		num=Decimal%16;
		SeqStack_Push(Manager,num);	
	}while(Decimal=Decimal/16);

	//显示部分
		printf("0X");
		for (int i = Manager->Top;i >= 0;i--)
	{
		if((Manager->Bottom[i])>9)
		printf("%c",55+(Manager->Bottom[i]));
		else
		printf("%c",48+(Manager->Bottom[i]));

	}
}

通过键盘输入一个包括 '(' 和 ')' 的字符串string ，判断字符串是否有效。要求设计算法实现检查字符串是否有效，有效的字符串需满足以下条件：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。
/*****************************************************
  * @function_name  : BracketMatc
  * @brief_         : 顺序栈实现括号匹配
  * @param_         : 
  * @retval_        : 空
  * @date_          : 2024/04/25
  * @version_       : v1.0 
  * @note_          : None
  *******************************************************/
//括号匹配
void BracketMatch()
{
    //输入字符串
	char str[100];
	printf("please input string:");
	//scanf("%s",&str);
	gets(str);
	//计算字符串长度
	int length=strlen(str);
	//创建顺序栈
	SeqStack_t * Manager = SeqStack_Create(length);
	//2.利用顺序栈进行括号匹配
	for(int i=0;i<length;i++)
	{
		if('('==str[i])
		SeqStack_Push(Manager,i);
		if(')'==str[i])
		//修改了出栈函数 出栈时即使flase也执行Top--
		SeqStack_MYPop(Manager);  
	}
	//判断栈顶指针的位置
	if(Manager->Top==-1)
	{
		printf("YES");
	}
	else
	{
		printf("NO");
	}
	//释放顺序栈	 
	SeqStack_Destroy(Manager);
}
/*****************************************************
  * @function_name  : SeqStack_MYPop
  * @brief_         : 方便顺序栈实现括号匹配写的函数 
  * @param_         : 
  * @retval_        : 空
  * @date_          : 2024/04/25
  * @version_       : v1.0 
  * @note_          : None
  *******************************************************/
//出栈时即使flase也执行Top--
bool SeqStack_MYPop(SeqStack_t *Manager)
{
	DataType_t temp=0;  //用于储存出栈的元素
	//1.判断顺序栈是否为空
	if ( SeqStack_IsEmpty(Manager) )
	{
		//printf("SequenceStack is Empty!\n");
		Manager->Top--; 
		return false;
	}
        
	//2.删除顺序栈的元素
	temp = Manager->Bottom[Manager->Top--];  //数据还残留在内存中，只是逻辑上被删除
	//Manager->Top--;
    return temp;
	
}

标签：Head,SeqStack,return,Next,学习,Manager,顺序
From： https://www.cnblogs.com/san39/p/18158620

相关文章

  • Web学习笔记(杂)
    理解React中的useStateHook在React中，useStatehook是一种用于在函数组件中添加状态的机制。通过useState，你可以在函数组件中声明状态变量，并且可以通过相应的函数来更新这些状态。例如：const[catHappiness,setCatHappiness]=useState(1);这段代码创建了一个名为cat......
  • 【笔记】动手学深度学习-预备知识
    预备知识2.1数据操作importtorchx=torch.arange(12)print(x.shape)print(torch.Size(x))print(x.numel())X=x.reshape(3,4)print(X)print(torch.ones((2,3,4)))print(torch.randn(3,4))print(torch.tensor([[2,1,3,4],[1,2,3,4],[3,4,5,......
  • JAVA安全学习 Day 1
    JAVAClassLoader机制谈起JAVA就不得不谈起他的基本类的加载机制谈一下我的粗略理解:我一开始也不理解为什么学习java安全要从一个classloader讲起，似乎有点太基层了，但是学到后面的cc链，才有了更明显的理解，因为只有深入理解了java的classloader机制才会在后面构造cc链的时候不会......
  • （数据科学学习手札160）使用miniforge代替miniconda
    本文已收录至我的Github仓库https://github.com/CNFeffery/DataScienceStudyNotes1简介大家好我是费老师，conda作为Python数据科学领域的常用软件，是对Python环境及相关依赖进行管理的经典工具，通常集成在anaconda或miniconda等产品中供用户日常使用。但长久以来，conda......
  • 开源相机管理库Aravis例程学习（四）——multiple-acquisition-signal
    目录简介例程代码函数说明g_main_loop_newg_main_loop_rung_main_loop_quitg_signal_connectarv_stream_set_emit_signalsQ&A回调函数的同步调用与异步调用帧丢失问题简介本文针对官方例程中的：02-multiple-acquisition-signal做简单的讲解。并简单介绍其中调用的g_main_loop_new......
  • 多项式乘法（FFT）学习笔记
    Reference：@自为风月马前卒亦@attack的博客这里为了帮助我自己理解，先手推（抄）一遍这位dalao给出的快速傅里叶逆变换的证明。\((y_0,y_1,\dots,y_{n-1})\)为多项式\((a_0,a_1,\dots,a_{n-1})\)在\(x\)取\((\omega^0_n,\omega^1_n,\dots,\omega^{n-1}_n)\)时......
  • 【pytorch学习】之线性神经网络-图像分类数据集
    图像分类数据集MNIST数据集(LeCunetal.,1998)是图像分类中广泛使用的数据集之一，但作为基准数据集过于简单。我们将使用类似但更复杂的Fashion‐MNIST数据集(Xiaoetal.,2017)。%matplotlibinlineimporttorchimporttorchvisionfromtorch.utilsimportdatafromt......
  • 使用 Visual Studio 调试 .NET 和 ASP.NET Core 源代码 | 学习地址
    使用VisualStudio调试.NET和ASP.NETCore源代码|MicrosoftLearn新建自签名证书|Microsoft学习AuthenticationHttpContextExtensions.ChallengeAsync方法(Microsoft.AspNetCore.Authentication)|MicrosoftLearn.netcore地址：  ASP.NETCore入门|Microsoft......
  • 【学习笔记】Python 使用 matplotlib 画图
    目录安装中文显示折线图、点线图柱状图、堆积柱状图坐标轴断点参考资料本文将介绍如何使用Python的matplotlib库画图，记录一些常用的画图demo代码安装#建议先切换到虚拟环境中pipinstallmatplotlib中文显示新版的matplotlib已经支持字体回退功能，因此可以直接设置......
  • nvidia公司官方迁移学习套件 —— NVIDIA TAO Toolkit
    资料：https://blogs.nvidia.com/blog/what-is-transfer-learning/相关：https://developer.nvidia.com/tao-toolkit......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99