栈的实现详解

news/2024/6/18 21:39:42 标签: c#, c语言

目录

  • 1. 栈
    • 1.1 栈的概念及结构
    • 1.2 栈的实现方式
    • 1.3 栈的应用场景
  • 2. 栈的实现
    • 2.1 结构体
    • 2.2 初始化
    • 2.3 销毁
    • 2.4 入栈
    • 2.5 出栈
    • 2.6 获取栈顶元素
    • 2.7 判空
    • 2.8 获取个数
  • 3. test主函数
  • 4. Stack.c文件
  • 5. Stack.h文件
  • 6. 运行展示

1. 栈

1.1 栈的概念及结构

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

在这里插入图片描述

在这里插入图片描述

1.2 栈的实现方式

栈可以通过多种方式实现，包括数组和链表等。使用数组实现的栈具有连续的内存空间，操作效率较高；而使用链表实现的栈则更加灵活，可以在动态环境中调整栈的大小。

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
实现用的是数据栈。

1.3 栈的应用场景

函数调用：在计算机程序中，函数调用和返回的过程可以用栈来实现。当调用一个函数时，会将函数的返回地址和参数压入栈中；当函数返回时，会从栈中弹出这些信息，并返回到调用点继续执行。
浏览器的前进与后退：在浏览器中，可以使用两个栈来实现前进和后退功能。一个栈记录新访问的页面，另一个栈记录后退弹出的页面。当用户点击前进按钮时，从记录新访问页面的栈中弹出页面；当用户点击后退按钮时，从记录后退页面的栈中弹出页面。
表达式求值：在编译器中，可以使用栈来进行表达式的求值。将运算符和操作数压入栈中，并根据运算符的优先级和结合性进行出栈和计算操作，最终得到表达式的值。

2. 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

在这里插入图片描述

在这里插入图片描述

2.1 结构体

首先要先把结构体定义出来，一个是数组栈，一个是指向栈顶元素的下一个，还有一个是增容。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//指向栈顶元素的下一个
	int capaicty;
}ST;

2.2 初始化

top等于0指向栈顶元素的下一个位置，top等于-1指向栈顶元素

//初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	//pst->top = -1;//指向栈顶元素
	pst->top = 0;//指向栈顶元素的下一个位置
	pst->capaicty = 0;
}

2.3 销毁

防止造成野指针的错误

//销毁
void STDestroy(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->top = 0;
	pst->capaicty = 0;
	free(pst->a);
}

2.4 入栈

先判断容量是否够，再实现动态增容。

//入栈
void STPush(ST* pst, STDataType x)
{
	//扩容
	if (pst->top == pst->capaicty)
	{
		int newCapaicty = pst->capaicty = 0 ? 4 : pst->capaicty * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapaicty * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("STPush");
			return;
		}

		pst->a = tmp;
		pst->capaicty = newCapaicty;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

2.5 出栈

看栈是否空，不是空就不能删，再top减减就行

//出栈
void STPpo(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	pst->top--;
}

2.6 获取栈顶元素

因为top指向栈顶元素的下一个，所以top要减1，当然空的时候也要判断一下

//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	return pst->a[pst->top - 1];
}

2.7 判空

//判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

2.8 获取个数

打印之前可以看还有多少个在栈中

//获取个数
int STsize(ST* pst)
{
	assert(pst);

	return pst->top;
}

3. test主函数

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "Stack.h"

void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPpo(&st);
	STPush(&st, 3);
	STPush(&st, 4);
	printf("size: %d\n", STsize(&st));
	
	//打印
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPpo(&st);
	}

	STDestroy(&st);
}

int main()
{
	TestStack1();
	return 0;
}

4. Stack.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"


//初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	//pst->top = -1;//指向栈顶元素
	pst->top = 0;//指向栈顶元素的下一个位置
	pst->capaicty = 0;
}

//销毁
void STDestroy(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->top = 0;
	pst->capaicty = 0;
	free(pst->a);
}

//入栈
void STPush(ST* pst, STDataType x)
{
	//扩容
	if (pst->top == pst->capaicty)
	{
		int newCapaicty = pst->capaicty = 0 ? 4 : pst->capaicty * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapaicty * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("STPush");
			return;
		}

		pst->a = tmp;
		pst->capaicty = newCapaicty;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

//出栈
void STPpo(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	pst->top--;
}

//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	return pst->a[pst->top - 1];
}

//判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

//获取个数
int STsize(ST* pst)
{
	assert(pst);

	return pst->top;
}

5. Stack.h文件

#pragma once
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//指向栈顶元素的下一个
	int capaicty;
}ST;

//初始化
void STInit(ST* pst);

//销毁
void STDestroy(ST* pst);

//入栈
void STPush(ST* pst, STDataType x);

//出栈
void STPpo(ST* pst);

//获取栈顶元素
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);

//获取个数
int STsize(ST* pst);

6. 运行展示

在这里插入图片描述


http://www.niftyadmin.cn/n/5520440.html

相关文章

Linux 内核的 notifier 机制

Linux 内核的 notifier 机制

Linux内核使用通知链的机制在内核各子系统之间进行事件通知&#xff08;注&#xff1a;无法用于内核态和用户态之 Linux内核中的notifier机制是一种重要的组件间通信机制&#xff0c;它允许在内核中的某些事件发生时&#xff0c;相关的组件能够得到通知并作出相应的处理。这种…
阅读更多...
Go-知识并发控制RWMutex

Go-知识并发控制RWMutex

Go-知识并发控制RWMutex 1. 介绍2. 原理2.1 读写锁的数据结构2.2 接口定义2.3 Lock() 写锁定 原理2.4 Unlock() 写锁定解锁 原理2.5 RLock() 读锁定 原理2.6 RUnlock() 读锁定解锁 原理 3. 场景分析3.1 写锁定如何阻塞写锁定3.2 写锁定如何阻塞读锁定3.3 读锁定如何阻塞写锁定3…
阅读更多...
SpringBoot + Maven 项目的创建

SpringBoot + Maven 项目的创建

文章目录 1、Maven2、SpringBoot3、二者之间的联系4、项目的创建 在创建项目之前&#xff0c;肯定要知道他们之间的区别 1、Maven maven是一个跨平台的项目管理工具。它是Apache的一个开源项目&#xff0c;主要服务于基于Java平台的项目构建、依赖管理和项目信息管理。 比如说…
阅读更多...
利用Cesium和JS实现地点点聚合功能

利用Cesium和JS实现地点点聚合功能

引言 在实现基于地图的业务场景时&#xff0c;当地图上需要展示过多的标记点时&#xff0c;大量的分散点会使地图上显得杂乱无章&#xff0c;导致标记点对地图上的其他重要信息造成遮挡和混淆&#xff0c;降低地图整体的可读性。 标记点的聚合就很好的解决了这些痛点的同时&a…
阅读更多...
【分形技术在神经网络建模中的应用】

【分形技术在神经网络建模中的应用】

分形技术在神经网络建模中的应用 随着大数据时代的到来&#xff0c;神经网络的应用越来越广泛。神经网络的优势在于其能通过学习的方式将任务的模式记忆下来并预测未知的数据。然而&#xff0c;神经网络的主要缺点是需要大量的训练数据和计算资源&#xff0c;这使得它难以解决…
阅读更多...
Linux文件系统【真的很详细】

Linux文件系统【真的很详细】

目录 一.认识磁盘 1.1磁盘的物理结构 1.2磁盘的存储结构 1.3磁盘的逻辑存储结构 二.理解文件系统 2.1如何管理磁盘 2.2如何在磁盘中找到文件 2.3关于文件名 哈喽&#xff0c;大家好。今天我们学习文件系统&#xff0c;我们之前在Linux基础IO中研究的是进程和被打开文件…
阅读更多...
C#——只读属性readonly

C#——只读属性readonly

只读属性readonly 类的字段可以通过一个readonly(只读)表示这个为只读字段&#xff0c;不能被构造函数之外地方进行修改&#xff0c;静态只读字段不能在非静态的构造函数中使用 定义 只读属性的特点&#xff1a; 字段是只读的非静态 只能在非静态方法中进行修改 字段是只读的…
阅读更多...
JavaEE——声明式事务管理案例：实现用户登录

JavaEE——声明式事务管理案例：实现用户登录

一、案例要求 本案例要求在控制台输入用户名密码&#xff0c;如果用户账号密码正确则显示用户所属班级&#xff0c;如果登录失败则显示登录失败。实现用户登录项目运行成功后控制台效果如下所示。 欢迎来到学生管理系统 请输入用户名&#xff1a; zhangsan 请输入zhangsan的密…
阅读更多...
最新文章

Copyright @ 2022~2023