NzN的数据结构--栈的实现

         在前面我们已经学习了哪些线性数据结构呢?大家一起来回顾一下:C语言学过的数组,数据结构中的线性表和顺序表和链表。那我们今天再来介绍数据结构里的两个线性结构--栈和队列。

目录

一、栈的概念及结构 

二、用数组实现栈

1. 栈的初始化和销毁

2. 从栈顶插入数据

3. 删除栈顶元素

4. 取栈顶元素

5. 计算栈中元素的数量

6. 判断栈是否为空

三、用链表实现栈

四、两种实现对比

1. 支持操作

2. 时间效率

3. 空间效率

五、栈的应用


一、栈的概念及结构 

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

        压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

        出栈:栈的删除操作叫做出栈,出数据也在栈顶

二、用数组实现栈

        栈的实现一般可以使用数组或链表实现,相对而言数组的结构实现更优一些

         使用数组实现栈时,我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素。那我们先通过数组实现栈。

        先在头文件中定义需要实现的功能接口:

//Stack.h
#pragma once
#include<stdio.h>
#include <stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//数组实现
	int top;//栈顶
	int capacity;//栈的容量
}ST;
//栈的初始化和销毁
void STInit(ST* ps);
void STDestroy(ST* ps);
//插入(只能从栈顶插入)
void STPush(ST* ps, STDataType x);
//栈中元素的删除
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//计算栈中元素的数量
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);

1. 栈的初始化和销毁

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//top=0指向的是栈顶元素的下一个
	//我们也可以让top=-1,这样top就指向栈顶元素
	ps->capacity = 0;
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

2. 从栈顶插入数据

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//空间不够直接扩容
	if (ps->top == ps->capacity)
	{
		//一开始没有给容量多大,因此需要判断
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//ps->a为空的话,realloc相当于malloc
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

3. 删除栈顶元素

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

4. 取栈顶元素

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

5. 计算栈中元素的数量

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

6. 判断栈是否为空

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

三、用链表实现栈

        使用链表实现栈时,我们可以将链表的头节点视为栈顶,尾节点视为栈底。

        对于入栈操作,我们只需将元素插入链表头部,这种节点插入方法被称为“头插法”。而对于出栈操作,只需将头节点从链表中删除即可。

         实现逻辑与数组相似,因此在这里直接给出实现代码:

//基于链表实现的栈
typedef struct {
    ListNode *top;//将头节点作为栈顶
    int size;//栈的长度
} LinkedListStack;

//栈的初始化
LinkedListStack *newLinkedListStack() 
{
    LinkedListStack *s = malloc(sizeof(LinkedListStack));
    s->top = NULL;
    s->size = 0;
    return s;
}

//栈的销毁
void delLinkedListStack(LinkedListStack *s) 
{
    while (s->top) 
    {
        ListNode *n = s->top->next;
        free(s->top);
        s->top = n;
    }
    free(s);
}

//计算栈中元素的数量
int size(LinkedListStack *s) 
{
    return s->size;
}

//判断栈是否为空
bool isEmpty(LinkedListStack *s) 
{
    return size(s) == 0;
}

//从栈顶插入数据
void push(LinkedListStack *s, int num) 
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->next = s->top;//更新新加节点指针域
    node->val = num;//更新新加节点数据域
    s->top = node;//更新栈顶
    s->size++;//更新栈大小
}

//取栈顶元素
int peek(LinkedListStack *s) {
    if (s->size == 0) 
    {
        printf("栈为空\n");
        return -1;
    }
    return s->top->val;
}

//删除栈顶元素
int pop(LinkedListStack *s) 
{
    int val = peek(s);
    ListNode *tmp = s->top;
    s->top = s->top->next;
    //释放内存
    free(tmp);
    s->size--;
    return val;
}

四、两种实现对比

1. 支持操作

        两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问,但这已超出了栈的定义范畴,因此一般不会用到。

2. 时间效率

在基于数组的实现中,入栈和出栈操作都在预先分配好的连续内存中进行,具有很好的缓存本地性,因此效率较高。然而,如果入栈时超出数组容量,会触发扩容机制,导致该次入栈操作的时间复杂度变为O(N) 。

在基于链表的实现中,链表的扩容非常灵活,不存在上述数组扩容时效率降低的问题。但是,入栈操作需要初始化节点对象并修改指针,因此效率相对较低。不过,如果入栈元素本身就是节点对象,那么可以省去初始化步骤,从而提高效率。

        综上所述,当入栈与出栈操作的元素是基本数据类型时,例如int或double我们可以得出以下结论。

  • 基于数组实现的栈在扩容时效率会降低,但由于扩容是低频操作,因此平均效率更高。
  • 基于链表实现的栈可以提供更加稳定的效率表现。

3. 空间效率

        在初始化列表时,系统会为列表分配“初始容量”,该容量可能超出实际需求;并且,扩容机制通常是按照特定倍率(例如 2 倍)进行扩容的,扩容后的容量也可能超出实际需求。因此,基于数组实现的栈可能造成一定的空间浪费

        然而,由于链表节点需要额外存储指针,因此链表节点占用的空间相对较大

        综上,我们不能简单地确定哪种实现更加节省内存,需要针对具体情况进行分析。

五、栈的应用

  • 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页,浏览器就会对上一个网页执行入栈,这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进,那么需要两个栈来配合实现。
  • 程序内存管理。每次调用函数时,系统都会在栈顶添加一个栈帧,用于记录函数的上下文信息。在递归函数中,向下递推阶段会不断执行入栈操作,而向上回溯阶段则会不断执行出栈操作。

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

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

相关文章

linux--进程创建

执行了3次ps -f ,ps -f的父进程的ID(PPID)都是一样的,即bash. 实际上Linux上这个bash就是不断的复制自身,然后把复制出来的用exec替换成想要执行的程序(比如ps); 运行ps,发现ps是bash的一个子进程;原因就是bash把自己复制一份,然后替换成ps; 替换,这里就体现了写时拷贝的意义,…

ETL中如何自定义规则

一、ETL中的规则 在使用规则之前我们先来了解一下什么是规则&#xff0c;ETL中规则在很多组件中都能看见&#xff0c;可以理解为按照事前约定好的逻辑去执行&#xff0c;规则可以使得数据更加的规范统一&#xff0c;同时也不需要去纵向的修改底层代码&#xff0c;只需要动态编…

自动驾驶汽车关键技术_感知

自动驾驶汽车关键技术|感知 附赠自动驾驶学习资料和量产经验&#xff1a;链接 两套标准 分别由美国交通部下属的国家高速路安全管理局(NationalHighwayTraffic Safety Administration &#xff0c;NHSTA) 和国际汽车工程师协会&#xff08;Societyof Automotive Engineers&am…

复现chatgpt_ros,需要openapi key

&#xff11;&#xff0e; 前置工作&#xff1a; 现在&#xff55;buntu系统是20.04ros1&#xff0c;现在用docker新建并安装ros2&#xff1a; 最简单的&#xff0c;用大佬的一键安装&#xff1a; wget http://fishros.com/install -O fishros && . fishros 其次自己装…

代码随想录刷题——5双指针法

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言5.1 移除元素&#xff08;3.30&#xff09;5.2 翻转字符串&#xff08;3.30&#xff09;5.3 替换数字&#xff08;3.30&#xff09;5.4 翻转字符串里的单词(3.3…

FlutterFlame游戏实践#08 | 打砖块 -关卡设计

theme: cyanosis 本文为稀土掘金技术社区首发签约文章&#xff0c;30天内禁止转载&#xff0c;30天后未获授权禁止转载&#xff0c;侵权必究&#xff01; Flutter\&Flame 游戏开发系列前言: 该系列是 [张风捷特烈] 的 Flame 游戏开发教程。Flutter 作为 全平台 的 原生级 渲…

SQL注入---POST注入

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 一. POST提交概述 在Webshell文章中介绍过post提交和get提交的区别&#xff0c;这里不再赘述 post提交和get提交的区别&#xff1a; get方式提交URL中的参数信息&#xff0c;post方式则是将信…

【学习分享】小白写算法之选择排序篇

【学习分享】小白写算法之选择排序篇 前言一、什么是选择排序算法二、选择排序算法如何实现三、C语言实现算法四、复杂度计算五、算法稳定性六、小结 前言 简单排序有三种&#xff0c;冒泡排序&#xff0c;插入排序和选择排序。这三种排序的算法算是入门级别的&#xff0c;打好…

UART设计

一、UART通信简介 通用异步收发器&#xff0c; 特点&#xff1a;串行、异步、全双工通信 优点&#xff1a;通信线路简单&#xff0c;传输距离远 缺点&#xff1a;传输速度慢 数据传输速率&#xff1a;波特率&#xff08;单位&#xff1a;baud&#xff0c;波特&#xff09; …

解决IDEA下载mysql驱动太慢

下载驱动 下载页 解压后&#xff0c;提取**.jar**文件&#xff0c;放到一个目录下(你自己决定这个目录) 打开IDEA项目&#xff0c;点击右侧的数据库选项卡 在打开的页面&#xff0c;点击号 依次选择&#xff1a;数据源->MySQL 在弹出的页面&#xff0c;依次选择&#…

注解式 WebSocket - 构建 群聊、单聊 系统

目录 前言 注解式 WebSocket 构建聊天系统 群聊系统&#xff08;基本框架&#xff09; 群聊系统&#xff08;添加昵称&#xff09; 单聊系统 WebSocket 作用域下无法注入 Spring Bean 对象&#xff1f; 考虑离线消息 前言 很久之前&#xff0c;咱们聊过 WebSocket 编程式…

华为ensp中高级acl (控制列表) 原理和配置命令 (详解)

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月6日23点18分 高级acl&#xff08;Access Control List&#xff09;是一种访问控制列表&#xff0c;可以根据数据包的源IP地址、目标IP地址、源端口、目标端口、协议…

【ARM 嵌入式 C 常用数据结构系列 25.1 -- linux 双向链表 list_head 使用详细介绍】

请阅读【嵌入式开发学习必备专栏 】 文章目录 内核双向链表双向链表的数据结构初始化双向链表在双向链表中添加元素遍历双向链表链表使用示例注意事项 内核双向链表 在Linux内核中&#xff0c;双向链表是一种广泛使用的数据结构&#xff0c;允许从任意节点高效地进行前向或后向…

STM32F407-SRAM

SRAM—> 内存 Flash–>硬盘 外置SRAM 可以存储1M数据 地址线&#xff1a;A0-A18&#xff1b;2^18次方&#xff1b;512K个数据块 每个数据块是2字节&#xff1b; 数据线&#xff1a;D0-D15 UB/LB 掩码&#xff1b;低电平有效 UB -》低电平-》数据高字节有效 LB-》低电平…

golang 选择排序

学习笔记&#xff5e; // Author sunwenbo // 2024/4/6 21:49 package mainimport "fmt"/* 选择排序基本介绍选择式排序也属于内部排序法&#xff0c;是从预排序的数据中按指定的规则选出某一元素&#xff0c;经过和其他元素重整&#xff0c;再依原则交换位置后达到…

轻量的 WebHook 工具:歪脖虎克

本篇文章聊聊轻量的网络钩子&#xff08;WebHook&#xff09;工具&#xff1a;歪脖虎克。 写在前面 这是一篇迟到很久的文章&#xff0c;在 21 年和 22 年的时候&#xff0c;我分享过两篇关于轻量的计划任务工具 Cronicle 的文章&#xff1a;《轻量的定时任务工具 Cronicle&a…

Linux(Ubuntu)中创建【samba】服务,用于和Windows系统之间共享文件

目录 1.先介绍一下什么是Samba 2.安装&#xff0c;配置服务 安装 配置&#xff08;smb.conf&#xff09; 配置用户 3.出现的问题&#xff08;Failed to add entry for user XXXX&#xff09; 4.创建文件夹 5.windows访问 1.先介绍一下什么是Samba Samba是一个开源的软…

2024.4.3-[作业记录]-day08-CSS 盒子模型(溢出显示、伪元素)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 作业 2024.4.3-学习笔记css溢出显示单行文本溢出显示省略号多行文本溢出显示省…

【Android】图解View的工作流程原理

文章目录 入口DecorView如何加载到Window中MeasureSpec MeasureView的测量ViewGroup的测量 LayoutView的layout() Draw1、绘制背景3、绘制View内容4、绘制子View6、绘制装饰 入口 DecorView如何加载到Window中 MeasureSpec 该类是View的内部类&#xff0c;封装View的规格尺寸…

C++资源重复释放问题

这不是自己释放了2次&#xff1b; 可能是类互相引用&#xff0c;有类似现象释放资源时引起&#xff1b;还不太了解&#xff1b; 类对象作为函数参数也会引起&#xff1b; 下面是一个简单示例&#xff1b; #include <iostream> #include <string.h> #include &l…