深入理解栈(Stack)(纯小白进)

news/2024/11/7 15:44:04/

目录:

  • 一、栈是什么?
    • 1. 栈的概念
    • 2.栈的结构选择
  • 二、栈的实现
    • 1. 栈结构体的定义
    • 2. 栈的初始化
    • 3. 栈的销毁
    • 4. 入栈
    • 5.出栈
    • 6. 取栈顶元素
    • 7. 栈中元素的个数
    • 8. 判断栈是否为空
  • 总结

一、栈是什么?

1. 栈的概念

栈(Stack):⼀种特殊的线性表,是一种常见的数据结构,其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶,另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。栈的应用非常广泛,例如函数调用栈、表达式求值、括号匹配等。

栈的基本操作包括:

  1. 入栈(Push):将元素压入栈顶。

  2. 出栈(Pop):将栈顶元素弹出。

  3. 查看栈顶元素(Top):获取栈顶元素的值,但不弹出。

  4. 判断栈是否为空(Empty):检查栈是否为空。

  5. 查看栈的大小(Size):获取栈内元素的个数。

栈就像是一叠摞在一起的盘子,我们放盘子只能放到盘子的最上面,同理取盘子,也只能从栈的最上方来取。放盘子称为入栈,去盘子称为出栈。
【<a class=数据结构入门】栈(Stack)的实现(定义、销毁、入栈、出栈等) | 图解数据结构,超详细哦~_销毁栈-CSDN博客" />

2.栈的结构选择

栈底层结构选型:

栈的实现⼀般可以使⽤数组或者链表实现,相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。

对比:

数组实现的栈是一种固定大小的栈,其优点是实现简单,缺点是大小固定。

链表实现的栈是一种动态大小的栈,其优点是大小可变,缺点是实现稍微复杂。

img

img

定长的静态栈,实际中我们一般不使用,所以我们下面主要实现的就是支持动态增长的栈 。


二、栈的实现

1. 栈结构体的定义

基于下面这张图,再类比顺序表,我们可以发现,栈的实现需要三个元素。
在这里插入图片描述

typedef int STDataType;
typedef struct Stack
{STDataType* arr;        //栈数组int capacity;           //栈的空间大小int top;                //栈顶位置
}ST;

对数据类型进行重命名,这样以后需要更换其他数据类型使用的时候只需要更改这一个地方就可以了。

ps: 定义一个数组动态的开辟空间,top用来记录栈顶元素的位置,capacity来表示栈的总容量大小。


2. 栈的初始化

先将栈中所有的数据都初始化为空,因为栈只需要在容量满的时候进行扩容,这里可以不需要先开辟空间,这一步可以节省。
具体的实现是:

//栈的初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

3. 栈的销毁

有初始化必然有销毁。

我们需要释放栈中的空间,别忘了将其置为NULL,防止内存泄漏。
释放掉栈中所有的元素。

注意:

这里不能直接对ps进行释放,因为ps中的arr是动态开辟来的,所以需要先对arr进行free,然后将其他成员置空。

//栈的销毁
void STDestroy(ST* ps)
{assert(ps);if(ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

4. 入栈

//数据入栈
void STPush(ST* ps, STDataType x); //STDataType x 是我们需要插入的数据

在这里插入图片描述

在入栈之前我们需要判断数组容量够不够,需不需要扩容。
在这里插入图片描述
在这里插入图片描述

具体实现是

void STPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (temp == NULL) {perror("realloc fail");return;}ps->a = temp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}

5.出栈

注意,如果栈为空,则不能出数据。

//数据出栈
void STPop(ST* ps);
//栈判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

在这里插入图片描述

开始出栈

//数据出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}

6. 取栈顶元素

//取栈顶元素
STDataType STTop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}

那么只要栈不为空,就可以一直取栈顶元素
在这里插入图片描述


7. 栈中元素的个数

//获取栈中有效元素个数
int STSize(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

8. 判断栈是否为空

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

总结

栈是一种简单且高效的数据结构,适用于需要“后进先出”操作的场景。通过掌握栈的基本操作和实现方式,我们可以更好地理解和应用这一数据结构,从而提高程序的效率和可靠性。希望这篇博客可以帮租到你,下一站:队列。


http://www.ppmy.cn/news/1537532.html

相关文章

第七章 常见攻击事件分析--钓鱼邮件

简介 请勿在本机运行恶意文件样本 请勿在本机运行恶意文件样本 请勿在本机运行恶意文件样本 小张的公司最近遭到了钓鱼邮件攻击&#xff0c;多名员工的终端被控制做为跳板攻击了内网系统&#xff0c;请对钓鱼邮件样本和内网被攻陷的系统进行溯源分析&#xff0c;请根据小张备…

LeetCode Hot100 | Day1 | 二叉树:二叉树的直径

LeetCode Hot100 | Day1 | 二叉树&#xff1a;二叉树的直径 主要学习内容&#xff1a; 二叉树深度求法 深度的 leftright1 得到的是从根结点到叶子结点的节点数量 543.二叉树的直径 [543. 二叉树的直径 - 力扣&#xff08;LeetCode&#xff09;](https://leetcode.cn/prob…

压力测试指南-压力测试基础入门

压力测试基础入门 在当今快速迭代的软件开发环境中&#xff0c;确保应用程序在高负载情况下仍能稳定运行变得至关重要。这正是压力测试大显身手的时刻。本文将带领您深入了解压力测试的基础知识&#xff0c;介绍实用工具&#xff0c;并指导您设计、执行压力测试&#xff0c;最…

WSL2环境下Ubuntu的Docker安装与配置

检查是否存在安装残留&#xff0c;移除可能会造成冲突的组件。 for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done从apt Docker仓库中安装官方GPG key&#xff1a; sudo apt-get update …

<OS 有关> Docker.Desktop - Unexpected WSL error #14030 不能启动, 问题已经解决 fixed

Windows Docker.Desktop 想用时报错&#xff1a; “deploying WSL2 distributions ensuring main distro is deployed: deploying "docker-desktop": importing WSL distro "WSL2 is not supported with your current machine configuration. Please enable th…

OpenAI 推出全新 “Canvas” 工具的系统提示词泄露

OpenAI 推出了一款叫做 Canvas 的新工具&#xff0c;用来帮助用户更好地与 ChatGPT 协作写作和编程。 Canvas 允许用户和 ChatGPT 在一个独立的窗口中协作&#xff0c;实时修改内容。这个工具可以帮助改进文本、调整语言、审查和修复代码&#xff0c;甚至转换成不同编程语言。…

C++设计模式——代理模式

欢迎来到 破晓的历程的 博客 ⛺️不负时光&#xff0c;不负己✈️ 文章目录 引言代理模式的定义代理模式的具体实现 引言 我们经常听到代理服务器「代理服务器是一个中间服务器&#xff0c;能够接收客户端的请求&#xff0c;并代表客户端向服务器发起请求&#xff0c;然后将服…

知识付费的市场有多大

在数字化时代&#xff0c;知识付费如同一股清流&#xff0c;悄然改变了我们的学习方式。那么&#xff0c;这个市场究竟有多大&#xff1f;它的未来又将如何&#xff1f; 近年来&#xff0c;知识付费市场如同坐上了火箭&#xff0c;迅速膨胀。从最初的线上课程、音频讲座&#…