首页 > 其他分享 >【数据结构】线性表之《栈》超详细实现

【数据结构】线性表之《栈》超详细实现

时间：2024-06-22 21:01:30浏览次数：24  
标签：ps arr 线性表 top ST assert 详细 数据结构 void

栈

一.栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除
操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）
的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二.顺序栈与链栈

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上
插入数据的代价比较小。那是为什么？且听下文分解。

1.顺序栈

在这里插入图片描述

2.链栈

1.单链表栈

在这里插入图片描述

将栈顶与栈低换个位置可以解决该问题，如下图：

在这里插入图片描述

2.双链表栈

在这里插入图片描述

  1. 由于双向链表比单链表多一个指针，基于节省内存的原由单链表优于双向链表。
  2. 数组的效率更优于单链表，原因：链表每一次插入一个数据都要申请一个节点，每次删除一个数据都要释放一个节点，且顺序栈包含数据+容量+栈顶，而链栈包含数据+指针，每个数据都要包含指针，顺序栈较于连栈会省一些内存。

接下来我将实现最优的——>顺序栈

三.顺序栈的实现

会写顺序表，那么实现顺序栈会非常轻松，这里就不一一介绍了，直接上代码。

1.栈的初始化

void StackInit(ST* ps)
{
	assert(ps);//断言

	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

2.检查栈的容量

void CheckCapacity(ST* ps)
{
	assert(ps);
	//栈满
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)//空间开辟失败
		{
			perror("realloc fail!");
			exit(-1);//退出程序
		}
		//空间开辟成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

3.入栈

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	CheckCapacity(ps);
	ps->arr[ps->top] = x;
	ps->top++;
}

4.出栈

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//栈空，无法出栈，否则下标越界

	ps->top--;
}

5.获取栈顶元素

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->arr[ps->top - 1];
}

6.栈的大小

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

7.栈的判空

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

8.栈的清空

void StackClear(ST* ps)
{
	assert(ps);

	ps->top = 0;
	ps->capacity = 0;
}

9.栈的销毁

void StackDestory(ST* ps)
{
	assert(ps);

	StackClear(ps);
	free(ps->arr);
	ps->arr = NULL;
}

四.模块化源代码

1.Stack.h

//#pragma once 防止头文件被重复包含
#ifndef __STACK_H__
#define __STACK_H__

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr; //栈空间的首地址
	int top;         //栈顶
	int capacity;    //容量
}ST;

void StackInit(ST* ps);//栈的初始化

void CheckCapacity(ST* ps);//检查栈的容量

void StackPush(ST* ps, STDataType x);//入栈

void StackPop(ST* ps);//出栈

STDataType StackTop(ST* ps);//获取栈顶元素

int StackSize(ST* ps);//获取栈的长度

bool StackEmpty(ST* ps);//栈的判空

void StackClear(ST* ps);//栈的清空

void StackDestory(ST* ps);//栈的销毁

#endif

2.Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void StackInit(ST* ps)
{
	assert(ps);//断言

	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void CheckCapacity(ST* ps)
{
	assert(ps);
	//栈满
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)//空间开辟失败
		{
			perror("realloc fail!");
			exit(-1);//退出程序
		}
		//空间开辟成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	CheckCapacity(ps);
	ps->arr[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//栈空，无法出栈，否则下标越界

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->arr[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackClear(ST* ps)
{
	assert(ps);

	ps->top = 0;
	ps->capacity = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);

	StackClear(ps);
	free(ps->arr);
	ps->arr = NULL;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

enum
{
	EXIT,
	PUSH,
	POP,
	TOP,
	SIZE,
	EMPTY,
	CLEAR
};

void Menu()
{
	printf("***************栈**************\n");
	printf("****1.入栈           2.出栈****\n");
	printf("****3.栈顶           4.大小****\n");
	printf("****5.判空           6.清空****\n");
	printf("****0.退出               ******\n");
	printf("*******************************\n");
}

int main()
{
	ST st;
	StackInit(&st);
	int select = 0;
	STDataType value;
	bool flag;
	do
	{
		Menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case EXIT:
			printf("退出栈!\n");
			break;
		case PUSH:
			printf("请输入您要入栈的值：");
			scanf("%d", &value);
			StackPush(&st, value);
			break;
		case POP:
			StackPop(&st);
			break;
		case TOP:
			value = StackTop(&st);
			printf("栈顶元素：%d\n", value);
			break;
		case SIZE:
			printf("栈的大小为：%d\n", StackSize(&st));
			break;
		case EMPTY:
			flag = StackEmpty(&st);
			if (flag)
			{
				printf("栈为空!\n");
			}
			else
			{
				printf("栈不为空!\n");
			}
			break;
		case CLEAR:
			StackClear(&st);
			break;
		default:
			printf("输入错误，请重新输入！\n");
			break;
		}
	} while (select);
	StackDestory(&st);
	return 0;
}

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！

标签：ps,arr,线性表,top,ST,assert,详细,数据结构,void
From： https://blog.csdn.net/2203_76003626/article/details/139884798

相关文章

  • CentOS7安装Gitlab13详细步骤
    环境配置CentOS Version7.6GitlabVersiongitlab-ce-13.12.15-ce.0.el7.x86_64下载rpm包Gitlab历史版本下载地址：https://packages.gitlab.com/gitlab/gitlab-ce（我在这里下载的gitlab-ce-13.12.15-ce.0.el7.x86_64.rpm建议使用下载工具进行下载）wgethttps://d20......
  • 大数据处理的坚实基石：Scala不可变数据结构的作用
    在大数据处理领域，数据的一致性、可靠性和性能至关重要。Scala语言提供的不可变数据结构在保证数据处理的稳定性和高效性方面发挥着重要作用。本文将详细探讨Scala中不可变数据结构的概念、优势以及它们在大数据处理中的应用。不可变数据结构的概念在Scala中，不可变数据结构......
  • 【学习笔记】使用第三方工具（secureCRT软件）通过console口本地访问访问交换机的详细操作
    一、前期准备1.终端设备（个人电脑）已正确安装，并能成功运行secureCRT软件（本次实验软件为：secureCRT）2.通过console口本地访问则需要准备一根console线（本次实验软console线为：USB转RJ45console调试线）二、操作步骤1、简明步骤说明：简明步骤需要一定基础1.1console线的USB端......
  • 【数据结构】顺序表实操——通讯录项目
    Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎~~......
  • 队列：先进先出的数据结构
    1.队列的概念及结构队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstInFirstOut)入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头2.队列的实现队列可以通过多种方式实现，包括数组、链表等。数......
  • Android面试题：App性能优化之Java和Kotlin常见的数据结构
    本文首发于公众号“AntDream”，欢迎微信搜索“AntDream”或扫描文章底部二维码关注，和我一起每天进步一点点Java常见数据结构特点ArrayListArrayList底层是基于数组实现add、删除元素需要进行元素位移耗性能，但查找和修改块适合不需要频繁添加删除的链表LinkedList是双......
  • 麒麟系统通过CrossOver软件安装Windows软件（.exe）的详细过程
    一、前期准备1.成功安装麒麟系统（本次实验的安装的系统是：Kylin-Desktop-V10-SP1））2.麒麟系统已经成功安装CrossOver软件3.Windows软件包（.exe文件）已经完成拷贝至麒麟系统4.知晓登录账户密码二、操作步骤选中需要安装的.exe软件，然后点击鼠标右键，然后选中打开方式，然......
  • 【设计文档】软件详细设计说明书案例文档（word直接套用）
    一、关于本文档（一）编写目的（二）预期读者二、项目概要（一）建设背景（二）建设目标（三）建设内容三、总体设计（一）需求规定（二）设计原则1．先进性2．实用性3．规范性4．安全性5．可维护性6．可扩展性（三）平台设计思路1．全面对象化和组件化2．良好的系统架......
  • ES6 新增Set 和 Map 两种数据结构
    ES6新增了Set和Map这两种数据结构，它们为JavaScript提供了更强大和灵活的数据处理能力。下面详细介绍一下Set和Map的特性和用法：SetSet是一种类似于数组的数据结构，但是成员的值都是唯一的，没有重复的值。特性：Set中的元素是唯一的，不会出现重复的值。Set可以接......
  • 【自学】从零开始学习数据结构--1.数据结构绪论
     本系列只用于我自己自学总结做出来的笔记，具有一定的参考性，但不多。凑合看吧。数据：数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。例如图片，音频这样的。数据元素：组成数据的，有一定意义的基本单位，在计算机中通常作为整体......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99