栈的实现详解

2024-06-15 1285阅读

目录

  • 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 
#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 
#include 
#include 
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. 运行展示

        栈的实现详解

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]