初级数据结构（三）——栈

  文中代码源文件已上传：数据结构源码

<-上一篇 初级数据结构（二）——链表        |        初级数据结构（四）——队列 下一篇->

1、栈的特性

1.1、函数栈帧简述

        即使是刚入门几天的小白，对栈这个字也应该略有耳闻。在操作系统层面，栈是系统在内存中划分的一整块连续的地址范围。并且系统对于单个程序在栈区的空间使用也是连续的。以一段代码举例：

void FunctionInside()
{
    /* ... */
}

void Function_1()
{
    /* ... */
}

void Function_2()
{
    /* ... */
    FunctionInside();
    /* ... */
}

int main()
{
    Function_1();
    Function_2();
    return 0;
}

        在运行上述代码时，首先调用 main 函数，系统将为 main 函数在栈上单独开辟一块空间供 main 函数使用，这块空间称作 main 函数的栈帧。而当在 main 中调用 Function_1 时，系统又在 main 函数栈帧之上为 Function_1 开辟一块  Function_1 的栈帧。而随着 Function_1 函数调用结束， Function_1 的栈帧也被销毁，该栈帧的空间归还给操作系统。

        而进入 Function_2 函数时，系统同样为 Function_2 开辟一块栈帧。如果如上述代码中的  Function_1 和 Function_2 是连续调用的话， Function_2 栈帧很可能覆盖之前 Function_1 被销毁的栈帧空间。此时进入 Function_2 函数内部，又在内部调用 FunctionInside 函数。此时，系统将在 Function_2 栈帧之上为 FunctionInside 创建栈帧。

        随着 FunctionInside 调用结束 FunctionInside 栈帧也随之归还，今儿回到 Function_2 的栈帧空间。当然， Function_2 调用结束后， Function_2 的栈帧也将归还，并回到 main 函数的栈帧空间。最后随着程序结束，main 函数的栈帧也随之销毁。

         或许有点绕。但看上图也不难发现其规律，这就是栈的特性：后入先出、先入后出，也称为 LIFO （ Last In First Out ）。

1.2、栈结构

        基于某些需求（如通过程序判断记录数学公式字符串的大中小括号是否配对、计算字符串中的数学公式的值、甚至最基本的数组倒序等），程序的数据处理需要用到后入先出的特性，对这类数据进行操作的结构就称为栈结构。

        栈结构的实现仍然是通过顺序表或者链表实现，只是在存取数据时必须遵循 LIFO 的规则。并且，栈结构不存在改和查的操作。如果要，必须将尾部数据至需要修改的数据之间的元素依次弹出后重新依次写入新数据，至于查，只允许查看尾部元素，一旦查看必须弹出。

        通常栈结构都用顺序表创建较为方便，因此以下便以顺序表的方式进行演示。同时最后附上链表实现栈结构的代码。

2、栈创建

2.1、文件结构

        与之前章节相同，依然创建三个文件，文件名如下：

        stack.h ：用于创建项目的结构体类型以及声明函数；

        stack.c ：用于创建栈各种操作功能的函数；

        main.c ：仅创建 main 函数，用作测试。

 2.2、前期工作

        stack.h 中内容如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

//存储数据类型的定义及打印占位符预定义
#define DATAPRT "%d"
typedef int DATATYPE;

//栈主体
typedef struct Stack
{
	DATATYPE* data;		//数据段
	size_t top;			//栈顶位置下标
	size_t capacity;	//开辟空间记录
}Stack;

//函数声明---------------------------------

//初始化
extern int StackInit(Stack*);
//销毁
extern void StackDestroy(Stack*);
//入栈
extern void StackPush(Stack*, DATATYPE);
//出栈
extern void StackPop(Stack*);

        然后 stack.c 中先创建初始化及销毁的两个函数。这里需要注意的是对结构体中的 top 值的操作。虽然这个值等同于顺序表中的 size ，但需要区分 top 是储存栈结构最后一个数据的下标。顺序表中的空表 size 则是等于 0 ，取顺序表的最后一个元素下标都是以 size - 1 进行操作，而对于栈来说，如果是空栈，top 则置为 -1 ：

#include "stack.h"

//初始化
int StackInit(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	//初始开辟1个数据位
	st->data = (DATATYPE*)malloc(sizeof(DATATYPE) * 1);
	if (!st->data)
	{
		fprintf(stderr, "Malloc Fail\n");
		return -2;
	}
	st->top = -1;
	st->capacity = 1;
	return 0;
}

//销毁
void StackDestroy(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	//释放
	free(st->data);
	st->data = NULL;
	st->top = -1;
	st->capacity = 0;
}

        在 main.c 中则预先创建一个结构体变量，无需进行其他操作。

#include "stack.h"

int main()
{
	Stack st;
	return 0;
}

3、栈的数据操作

3.1、入栈

        入栈实际上就是顺序表的尾插，具体实现过程可以参考第一篇顺序表中的插入数据操作。这个功能实现起来并不复杂。此外跟顺序表一样，如果已开辟的空间不足则需要进行扩容操作。这里可以将扩容封装为一个函数，使代码看起来更简洁。此外，由于扩容函数仅在该代码文件内调用，可以加上 static 修饰。

        在 static.c 中加入以下代码：

//扩容
static void StackExpand(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	DATATYPE* temp = (DATATYPE*)realloc(st->data, sizeof(DATATYPE) * st->capacity * 2);
	if (!temp)
	{
		fprintf(stderr, "Realloc Fail\n");
		return;
	}
	st->data = temp;
	st->capacity *= 2;
}

//入栈
void StackPush(Stack* st, DATATYPE data)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	st->top++;
	//空间不足则扩容
	if ((st->top) >= (st->capacity))
	{
		StackExpand(st);
	}
	//入栈
	st->data[st->top] = data;
}

        然后在 main.c 中输入以下，并测试：

    StackInit(NULL);
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

        测试无误，进行下一步。

3.2、出栈

        入栈等于尾插，那出栈自然就等同于尾删。对于出栈操作需要注意两点，栈是否为空以及空间回收。是否空栈只需判别 top 是否等于 -1 。至于空间回收，顺序表中也有提到，操作逻辑完全一致。

        这里为了代码可读性，将空栈判断封装为函数，将空间回收也一并封装为函数。 stack.c 中增加如下代码：

//收缩空间
static void StackContract(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	DATATYPE* temp = (DATATYPE*)realloc(st->data, sizeof(DATATYPE) * st->capacity / 2);
	if (!temp)
	{
		fprintf(stderr, "Realloc Fail\n");
		return;
	}
	st->data = temp;
	st->capacity /= 2;
}

//空表判断 空表返回true
static bool StackIsEmpty(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return true;
	}
	return (st->top == -1 ? true : false);
}

//出栈
void StackPop(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	//数据为空直接返回
	if (StackIsEmpty(st))
	{
		fprintf(stderr, "Stack Empty\n");
		return;
	}
	//出栈
	st->top--;
	//空间过剩则收缩空间
	if ((st->top) < (st->capacity) / 2)
	{
		StackContract(st);
	}
}

3.3、附加功能

        出栈功能写完后，获取栈顶数据及打印输出栈顶数据的功能也一并加上。首先在 stack.h 中进行声明：

//打印
extern void StackPrint(Stack*);
//获取栈顶数据
extern DATATYPE StackGetTopData(Stack*);

        然后继续在 static.c 中补充这两个功能。

        这里需要注意，因为获取栈顶数据是有返回值的，因此如果空表或者传入空指针便不能简单地 return ，容易对返回值的接收产生误解。而不论 return 任何值，均有可能被误以为栈顶数据就是该值，因此这里以 assert 判定最佳：

//获取栈顶数据
DATATYPE StackGetTopData(Stack* st)
{
	//参数判断
	assert(st);
	//空表警告
	assert(!StackIsEmpty(st));
	//取数据并出栈
	DATATYPE data = st->data[st->top];
	StackPop(st);
	return data;
}

//打印
void StackPrint(Stack* st)
{
	//参数判断
	if (!st)
	{
		fprintf(stderr, "Illegal Stack Address\n");
		return;
	}
	//空表打印NULL后返回
	if (StackIsEmpty(st))
	{
		printf("NULL ");
		return;
	}
	//打印栈顶并出栈
	printf(DATAPRT " ", StackGetTopData(st));
}

        至此功能完毕。之后便是测试，同时也顺带测试之前出栈的函数。完整的 main 函数代码：

int main()
{
	Stack st;
	StackInit(NULL);
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPrint(&st);        //5
	StackPrint(&st);        //4
	StackPrint(&st);        //3
	StackPrint(&st);        //2
	StackPrint(&st);        //1
	StackPrint(&st);        //NULL
	StackPrint(&st);        //NULL
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPrint(&st);        //3
	StackDestroy(&st);
	StackPrint(&st);        //NULL

	return 0;
}

        测试结果如下： 

        至此栈结构便完成了。 

4、以链表实现栈

        链表实现栈的文件结构与顺序表实现栈的结构一致，根据以下代码自行测试研究。有链表的基础打底，这里实现起来也将十分轻松：

        stack.h ：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#define DATAPRT "%d"

typedef int DATATYPE;

typedef struct StackNode
{
	DATATYPE data;
	struct StackNode* next;
}StackNode;

typedef struct StackInfo
{
	StackNode* StackHead;
	size_t StackSize;
}StackInfo;

//函数声明---------------------------------
//初始化
extern void StackInit(StackInfo*);
//销毁
extern void StackDestroy(StackInfo*);
//入栈
extern void StackPush(StackInfo*, DATATYPE);
//出栈
extern void StackPop(StackInfo*);
//获取栈顶数据
extern DATATYPE StackGetHead(StackInfo*);
//打印栈顶数据
extern void StackPrint(StackInfo*);

        stack.c ：

#include "stack.h"

//初始化
void StackInit(StackInfo* info)
{
	//参数有效判断
	if (!info)
	{
		fprintf(stderr, "Illegal StackInformation Address\n");
		return;
	}
	//初始化
	info->StackHead = NULL;
	info->StackSize = 0;
}

//销毁
void StackDestroy(StackInfo* info)
{
	//参数有效判断
	if (!info)
	{
		fprintf(stderr, "Illegal StackInformation Address\n");
	}
	//空链表直接返回
	if (!info->StackSize)
	{
		return;
	}
	//逐节点释放空间
	StackNode* currentNode = info->StackHead;
	while (currentNode)
	{
		StackNode* destroyNode = currentNode;
		currentNode = currentNode->next;
		free(destroyNode);
	}
	info->StackHead = NULL;
	info->StackSize = 0;
}

//判空
static bool StackIsEmpty(StackInfo* info)
{
	//参数有效判断
	if (!info)
	{
		fprintf(stderr, "Illegal StackInformation Address\n");
		return;
	}
	return (info->StackSize == 0 ? true : false);
}

//入栈
void StackPush(StackInfo* info, DATATYPE data)
{
	//参数有效判断
	if (!info)
	{
		fprintf(stderr, "Illegal StackInformation Address\n");
		return;
	}
	StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
	if (!newNode)
	{
		fprintf(stderr, "Malloc Fail\n");
		return;
	}
	newNode->data = data;
	newNode->next = info->StackHead;
	info->StackHead = newNode;
	info->StackSize++;
}

//出栈
void StackPop(StackInfo* info)
{
	//参数有效判断
	if (!info)
	{
		fprintf(stderr, "Illegal StackInformation Address\n");
		return;
	}
	if (StackIsEmpty(info))
	{
		fprintf(stderr, "Stack Empty\n");
		return;
	}
	StackNode* destroyNode = info->StackHead;
	info->StackHead = info->StackHead->next;
	info->StackSize--;
	free(destroyNode);
}

//获取栈顶数据
DATATYPE StackGetHead(StackInfo* info)
{
	//参数有效判断
	assert(info);
	//空表警告
	assert(!StackIsEmpty(info));
	DATATYPE data = info->StackHead->data;
	StackPop(info);
	return data;
}

//打印栈顶数据
void StackPrint(StackInfo* info)
{
	//参数有效判断
	if (!info)
	{
		fprintf(stderr, "Illegal StackInformation Address\n");
		return;
	}
	if (StackIsEmpty(info))
	{
		printf("NULL ");
		return;
	}
	printf(DATAPRT " ", StackGetHead(info));
}

        main.c 的测试用例：

#include "stack.h"

int main()
{
	StackInfo info;
	StackInit(NULL);
	StackInit(&info);
	StackPush(&info, 1);
	StackPush(&info, 2);
	StackPush(&info, 3);
	StackPush(NULL, 20);
	StackPush(&info, 4);
	StackPush(&info, 5);
	StackPrint(&info);
	StackPrint(&info);
	StackPrint(&info);
	StackPrint(&info);
	StackPrint(&info);
	StackPrint(&info);
	StackPrint(&info);
	StackPrint(&info);
	StackPush(&info, 1);
	StackPush(&info, 2);
	StackPush(&info, 3);
	StackPrint(&info);
	StackDestroy(&info);
	StackPrint(&info);
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/241567.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux——MySQL数据库系统()

Linux——MySQL数据库系统()

一、访问MySQL数据库 MySQL数据库系统也是一个典型的C/S(客户端/服务器&#xff09;架构的应用&#xff0c;要访问MySQL数据库需要使用专门的客户端软件。在Linux系统中&#xff0c;最简单、易用的MySQL客户端软件是其自带的mysql命令工具。 1、登录到MySQL服务器经过安装后的初…
阅读更多...
深入理解TheadLocal的使用场景和注意事项

深入理解TheadLocal的使用场景和注意事项

前言 在日常实际开发当中我们往往会看到项目中有使用 ThreadLocal 的场景&#xff0c;大多数人有时候可能涉及不到自己的业务则没有进行关注。通常我在看代码时对于一些未知的东西常常引起我的好奇&#xff0c;我往往会分析&#xff1a;为什么要这么做&#xff1f;好处是什么&…
阅读更多...
一文看懂支付前链路流程

一文看懂支付前链路流程

一文看懂支付前链路流程 前序 首先支付流程讲究的就是快&#xff0c;还有就是订单的冲入&#xff0c;我们不能说一笔交易订单进来都加一个分布式锁去解决&#xff0c;所以我们目前常用的做法就是一个订单进来&#xff0c;首先落库&#xff0c;如果落库失败&#xff0c;并且是…
阅读更多...
用XAMPP在Windows系统构建一个本地Web服务器

用XAMPP在Windows系统构建一个本地Web服务器

用XAMPP在Windows系统构建一个本地Web服务器 Build a Local Web Server for Windows with XAMPP By JacksonML 本文简要介绍如何获取和安装XAMPP以实现Windows环境下本地Web服务器的过程&#xff0c;希望对广大网友和学生有所帮助。 所谓本地Web服务器&#xff0c;即使用本地…
阅读更多...
UML-认识6种箭头（画类图无烦恼）

UML-认识6种箭头（画类图无烦恼）

文章目录 一、背景二、箭头详解2.1 泛化&#xff08;Generalization&#xff09;2.2 实现&#xff08;Realize&#xff09;2.3 依赖&#xff08;Dependency&#xff09;2.4 关联&#xff08;Association&#xff09;2.5 聚合&#xff08;Aggregation&#xff09;2.6 组合&#…
阅读更多...
24V降12V2A同步降压芯片WT6023A

24V降12V2A同步降压芯片WT6023A

24V降12V2A同步降压芯片WT6023A 今天给大家带来一款高性能的DC/DC转换器WT6023A&#xff0c;快来一起了解一下吧&#xff01; WT6023A是一款采用抖动频率模式控制架构的高效、单片同步降压型DC/DC转换器&#xff0c;能够提供高达6A的连续负载&#xff0c;具有出色的线路和负载…
阅读更多...
BugKu-Web-Flask_FileUpload(模板注入与文件上传）

BugKu-Web-Flask_FileUpload(模板注入与文件上传）

Flask Flask是一个使用Python编写的轻量级Web应用框架。它是一个微型框架&#xff0c;因为它的核心非常简单&#xff0c;但可以通过扩展来增加其他功能。Flask的核心组件包括Werkzeug&#xff0c;一个WSGI工具箱&#xff0c;以及Jinja2&#xff0c;一个模板引擎。 Flask使用BSD…
阅读更多...
快速准确翻译文件夹名：英文翻译成中文，文件夹批量重命名的技巧

快速准确翻译文件夹名：英文翻译成中文，文件夹批量重命名的技巧

在处理大量文件夹时&#xff0c;可能会遇到要将英文文件夹名翻译成中文的情况。同时也可能要批量重命名这些文件夹。今天一起来看下云炫文件管理器如何快速准确翻译文件夹名&#xff0c;进行批量重命名的技巧。 下图是文件夹名翻译前后的效果图。 英文文件夹名批量翻译成中文…
阅读更多...
注意力机制和自注意力机制

注意力机制和自注意力机制

有很多自己的理解&#xff0c;仅供参考 Attention注意力机制 对于一张图片&#xff0c;我们第一眼看上去&#xff0c;眼睛会首先注意到一些重点的区域&#xff0c;因为这些区域可能包含更多或更重要的信息&#xff0c;这就是注意力机制&#xff0c;我们会把我们的焦点聚焦在比…
阅读更多...
2023年12月7日：QT实现登陆界面

2023年12月7日：QT实现登陆界面

#include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {//窗口设置this->resize(600,500);//重新设置窗口大小this->setWindowTitle("QQ-盗版");//设置窗口名为QQ-盗版this->setWindowIcon(QIcon("D:\\Qt\\funny\\pi…
阅读更多...
【改进YOLOv8】融合感受野注意力卷积RFCBAMConv的杂草分割系统

【改进YOLOv8】融合感受野注意力卷积RFCBAMConv的杂草分割系统

1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 研究背景与意义 随着计算机视觉技术的不断发展&#xff0c;图像分割成为了一个重要的研究领域。图像分割可以将图像中的不同对象或区域进行有效的分离&#xff0c;对于许多应用领…
阅读更多...
【广州华锐视点】仓储物流3D数字孪生平台打造更高效、智能的物流管理体验

【广州华锐视点】仓储物流3D数字孪生平台打造更高效、智能的物流管理体验

在当今快速发展的物流行业中&#xff0c;传统的管理和监控方法往往难以满足复杂运营的需求。为了解决这个问题&#xff0c;广州华锐互动提供仓储物流3D数字孪生平台定制开发服务&#xff0c;打造更为高效、智能的物流管理体验。 仓储物流3D数字孪生平台是一种基于虚拟现实技术的…
阅读更多...
DNS漫游指南：从网址到IP的奇妙之旅

DNS漫游指南：从网址到IP的奇妙之旅

当用户在浏览器中输入特定网站时发生的整个端到端过程可以参考下图 1*4vb-NMUuYTzYBYUFSuSKLw.png 问题&#xff1a; 什么是 DNS&#xff1f; 答案 → DNS 指的是域名系统&#xff08;Domain Name System&#xff09;。DNS 是互联网的目录&#xff0c;将人类可读的域名&#…
阅读更多...
flutter 代码混淆

flutter 代码混淆

Flutter 应用混淆&#xff1a; Flutter 应用的混淆非常简单&#xff0c;只需要在构建 release 版应用时结合使用 --obfuscate 和 --split-debug-info 这两个参数即可。 –obfuscate --split-debug-info 用来指定输出调试文件的位置&#xff0c;该命令会生成一个符号映射表。目前…
阅读更多...
学习Django从零开始之一

学习Django从零开始之一

Django 是用Python开发的一个免费开源的Web框架&#xff0c;可以用于快速搭建高性能&#xff0c;优雅的定制网站&#xff01;采用了MVC的框架模式&#xff0c;即模型M&#xff0c;视图V和控制器C&#xff0c;也可以称为MVT模式&#xff0c;模型M&#xff0c;视图V&#xff0c;模…
阅读更多...
python编程需要的电脑配置,python编程用什么电脑

python编程需要的电脑配置,python编程用什么电脑

大家好&#xff0c;小编来为大家解答以下问题&#xff0c;python编程对笔记本电脑配置的要求&#xff0c;python编程对电脑配置的要求有哪些&#xff0c;现在让我们一起来看看吧&#xff01; 学习python编程需要什么配置的电脑 简单的来讲&#xff0c;Python的话普通电脑就可以…
阅读更多...
应用ICP-MS实验PFA烧杯耐腐蚀带刻度反应杯的特点分析

应用ICP-MS实验PFA烧杯耐腐蚀带刻度反应杯的特点分析

聚四氟&#xff08;PFA&#xff09;烧杯可用于痕量分析、同位素分析等实验&#xff0c;ICP-MS实验室适用。半导体、多晶硅、光伏电子 锂电池行业均适用。杯体刻度清晰&#xff0c;方便观察&#xff0c;尖嘴方便倾倒溶液。 可溶性聚四氟乙烯烧杯特性&#xff1a; 1、透明&…
阅读更多...
企业U盘防泄密的必备秘籍！迅软DSE答疑解析一切你需要知道的！

企业U盘防泄密的必备秘籍！迅软DSE答疑解析一切你需要知道的！

关于U盘防泄密&#xff1a; U盘是企事业单位办公时经常需要用到的存储介质&#xff0c;而一旦U盘不慎丢失或是落入他人手中&#xff0c;都会面临U盘内数据泄密的情况发生。 因此&#xff0c;企事业单位可通过天锐绿盾安全U盘系统对公司重要数据进行U盘防泄密保护&#xff0c;确…
阅读更多...
如何使用Docker将.Net6项目部署到Linux服务器（一）

如何使用Docker将.Net6项目部署到Linux服务器（一）

目录 配置服务器环境 配置yum 配置docker 安装.NetCore SDK6.0 发布Net6 添加Dockerfile。 发布文件。 编辑DockerFile文件 ​编辑 上传文件 安装MySql 配置服务器环境 配置yum 在配置yum之前&#xff0c;我们需要先了解yum是什么&#xff0c;yum&#xff0c;是Yellow…
阅读更多...
实时视频美颜SDK的选择指南与性能比较

实时视频美颜SDK的选择指南与性能比较

时下&#xff0c;直播平台如何选取合适的SDK成为了一项重要的决策。本文将带您深入探讨实时视频美颜SDK的选择指南&#xff0c;并进行性能比较&#xff0c;助您做出明智的决策。 一、SDK功能概览 在选择实时视频美颜SDK之前&#xff0c;首先需要明确您的应用需求。不同的SDK可…
阅读更多...
最新文章

Copyright @ 2022~2023