数据结构:线性表(栈的实现)

文章目录

  • 1. 栈(Stack)
    • 1.1 栈的概念
    • 1.2 栈的结构
      • 链表栈
      • 数组栈
  • 2. 栈的定义
  • 3. 栈的实现
    • 3.1 初始化栈 (StackInit)
    • 3.2 入栈 (StackPush)
    • 3.3 出栈 (StackPop)
    • 3.4 检测栈是否为空 (StackEmpty)
    • 3.5 获取栈顶元素 (StackTop)
    • 3.6 获取栈中有效元素个数 (StackSize)
    • 3.7 销毁栈 (StackDestroy)
    • 3.8 完整代码

1. 栈(Stack)

1.1 栈的概念

  • 栈(Stack)是只允许在一端进行插入或删除操作的线性表.首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作.
  • 进行数据插入和删除操作的一端栈顶,另一端称为栈底.
  • 栈中的元素遵循后进先出LIFO(Last In First Out)的原则

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶.
出栈:栈的删除操作叫做出栈,出数据也在栈顶.

1.2 栈的结构

在这里插入图片描述

栈的元素,遵循后进先出原则


栈采用什么逻辑结构呢?
通常栈可以用链表和数组实现.
当然我们调用的时候不需要知道,使用的是什么方法实现.

链表栈

通过在表前端插入来实现 push ,通过删除表前端元素实现 pop.
可以使用之前实现的单链表来实现栈,单链表实现详见.只用注意,栈只有插入删除操作,需要头删和头插.

虽然操作都是花费常数时间,但是对mallocfree的调用是十分昂贵的.

数组栈

更为流行的是使用数组来实现栈.虽然数组的大小需要提前说明或者临时开辟,但是,在典型的应用程序中,栈元素的实际个数一般不会太大,使用数组是更加高效的方法.


总结:

  • 推荐使用数组结构实现栈
  • 若使用链表实现栈
    用尾做栈顶,尾删尾插,要设计成双向链表
    用头做栈顶,头删头插,要设计成单链表

2. 栈的定义

一般来说,使用动态栈而非静态栈,需要扩容的时候,可以进行适当扩容,增加了程序的适用性.

动态栈实现的数据结构

typedef int STDataType;typedef struct Stack
{STDataType* a;  //指向栈空间int top;        //栈顶int capacity;   //容量
}Stack;

接口函数

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

3. 栈的实现

3.1 初始化栈 (StackInit)

// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;     ps->top = 0;ps->capacity = 0;
}
  1. 和创建顺序表的操作是一致的,通过结构体指针ps修改主函数中的结构体的成员变量,将ps指向的数组指针指向NULL,同时将容量capacity和栈顶元素top置为 0.
  1. 注意,在这里,top所指向的是栈顶元素后一个空间,此时没有元素,自然就指向了数组的第一个空间

3.2 入栈 (StackPush)

//入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);       //确保ps合法//如果容量不够则扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;   //定义新的容量STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);  //开辟新的空间if (tmp == NULL){perror("malloc error");exit(-1);}else {ps->a = tmp;ps->capacity = newCapacity;}}//将数据入栈ps->a[ps->top] = data;ps->top++;
}
  1. 首先确保ps合法
  2. 因为是动态栈,会出现空间不够的情况,在入栈之前首先确保容量充足,如果容量不够,则进行扩容
  3. 将数据入栈,同时top++

3.3 出栈 (StackPop)

// 出栈
void StackPop(Stack* ps)
{assert(ps); //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空ps->top--;}
  1. 确保 ps 合法
  2. 确保栈不为空
  3. 直接将top--即可

3.4 检测栈是否为空 (StackEmpty)

// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps)
{assert(ps); //确保ps合法if (ps->top > 0){return 0;}else {return 1;}
}
  1. 确保ps合法
  2. 如果top大于0,说明栈不为空,反之则为空

3.5 获取栈顶元素 (StackTop)

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);   //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空return ps->a[ps->top - 1];
}
  1. 确保ps合法
  2. 确保栈不为空
  3. 直接返回top - 1位置的元素

3.6 获取栈中有效元素个数 (StackSize)

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);   //确保ps合法return ps->top;
}
  1. 确保ps合法
  2. 直接将top返回即可

3.7 销毁栈 (StackDestroy)

// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps); //确保ps合法free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
  1. 确保ps合法
  2. 将ps指向的数组空间归还给操作系统,同时将topcapacity置为0

3.8 完整代码

  • Stack.h
#pragma once #include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* a;  //指向栈空间int top;        //栈顶int capacity;   //容量
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
  • Stack.c
#include "Stack.h"// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;     ps->top = 0;ps->capacity = 0;
}//入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);       //确保ps合法//如果容量不够则扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;   //定义新的容量STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);  //开辟新的空间if (tmp == NULL){perror("malloc error");exit(-1);}else {ps->a = tmp;ps->capacity = newCapacity;}}//将数据入栈ps->a[ps->top] = data;ps->top++;
}// 出栈
void StackPop(Stack* ps)
{assert(ps); //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空ps->top--;}// 检测栈是否为空, 如果为空返回非零结果, 如果不为空返回 0
int StackEmpty(Stack* ps)
{assert(ps); //确保ps合法if (ps->top > 0){return 0;}else {return 1;}
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);   //确保ps合法assert(!StackEmpty(ps));  //确保栈不为空return ps->a[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);   //确保ps合法return ps->top;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps); //确保ps合法free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
  • Test.c
#include "Stack.h"void StackTest1()
{Stack st;StackInit(&st);StackPush(&st, 1);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 2);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 3);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 4);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPush(&st, 5);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);
}int main(void)
{StackTest1();return 0;
}printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);
}int main(void)
{StackTest1();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥杯官网练习题(纸牌三角形)

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 A,2,3,4,5,6,7,8,9 共 99 张纸牌排成一个正三角形&#xff08;A 按 1 计算&#xff09;。要求每个边的和相等。 下图就是一种排法。 这样的排法可能会有很多。 如果…

Docker-安装(Linux,Windows)

目录 前言安装版本Docker版本说明前提条件Linux安装使用YUM源部署获取阿里云开源镜像站YUM源文件安装Docker-ce配置Docker Daemon启动文件启动Docker服务并查看已安装版本 使用二进制文件部署 Windows安装实现原理安装步骤基本使用 参考说明 前言 本文主要说明Docker及其相关组…

Mac brew -v 报错 fatal: detected dubious ownership in repository

Mac 电脑查询 brew版本时报错&#xff0c;如下错误&#xff1a; Last login: Fri Sep 8 14:56:21 on ttys021 sunshiyusunshiyudeMacBook-Pro-2 ~ % brew -v Homebrew 4.0.3-30-g7ac31f7 fatal: detected dubious ownership in repository at /usr/local/Homebrew/Library/Ta…

C++面向对象

C面向对象知识 内存字节对齐 #pragma pack(n) 表示的是设置n字节对齐,windows默认是8字节&#xff0c;linux是4字节&#xff0c;鲲鹏是4字节 struct A{char a;int b;short c; };char占一个字节&#xff0c;起始偏移为零&#xff0c;int占四个字节&#xff0c;min(8,4)4&#x…

计算机毕设之基于Hadoop+springboot的物品租赁系统的设计与实现(前后端分离,内含源码+文档+教程)

该系统基于Hadoop平台&#xff0c;利用Java语言、MySQL数据库&#xff0c;结合目前流行的 B/S架构&#xff0c;将物品租赁管理的各个方面都集中到数据库中&#xff0c;以便于用户的需要。在确保系统稳定的前提下&#xff0c;能够实现多功能模块的设计和应用。该系统由管理员功能…

小白备战大厂算法笔试(六)——堆

文章目录 堆常用操作堆的实现存储与表示访问堆顶元素元素入堆元素出堆 常见应用建堆操作自上而下构建自下而上构建 TOP-K问题遍历选择排序堆 堆 堆是一种满足特定条件的完全二叉树&#xff0c;主要可分为下图所示的两种类型。 大顶堆&#xff1a;任意节点的值 ≥ 其子节点的值…

Android MeidiaCodec之OMXPluginBase与QComOMXPlugin实现本质(四十)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…

tomcat的优化

TOMCAT的优化 tomcat的优化主要是从三个方面进行的&#xff0c;第一个是 tomcat配置的优化第二是对JVM虚拟机的优化第三是对Linux系统内核的优化&#xff0c;配置文件中的优化主要在tomcat中server.xml文件夹内 tomcat配置文件的优化 1、 maxThreads&#xff1a; Tomcat 使用…

Java笔记:线程池

一. 正确使用ThreadPoolExecutor创建线程池 1.1、基础知识 Executors创建线程池便捷方法列表&#xff1a;下面三个是使用ThreadPoolExecutor的构造方法创建的 方法名功能newFixedThreadPool(int nThreads)创建固定大小的线程池newSingleThreadExecutor()创建只有一个线程的线…

HTML5Plus

之前写过在 vue 中使用 mui 框架的方法&#xff0c;因为用 vue 开发后打包 5App 会有一些问题&#xff0c;所以当时用到了&#xff0c;最近又一次开发移动端&#xff0c;不同的是这次使用的是 vue3 开发的&#xff0c;导致之前使用的 vue-awesome-mui 依赖不能使用了&#xff0…

java 工程管理系统源码+项目说明+功能描述+前后端分离 + 二次开发

Java版工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离 功能清单如下&#xff1a; 首页 工作台&#xff1a;待办工作、消息通知、预警信息&#xff0c;点击可进入相应的列表 项目进度图表&#xff1a;选择&#xff08;总体或单个&#xff09;项目显示…

华为OD机考算法题:分奖金

题目部分 题目分奖金难度难题目说明公司老板做了一笔大生意&#xff0c;想要给每位员工分配一些奖金&#xff0c;想通过游戏的方式来决定每个人分多少钱。按照员工的工号顺序&#xff0c;每个人随机抽取一个数字。按照工号的顺序往后排列&#xff0c;遇到第一个数字比自己数字…

YOLOv5:对yolov5n模型进一步剪枝压缩

YOLOv5&#xff1a;对yolov5n模型进一步剪枝压缩 前言前提条件相关介绍具体步骤修改yolov5n.yaml配置文件单通道数据&#xff08;黑白图片&#xff09;修改models/yolo.py文件修改train.py文件 剪枝后模型大小 参考 前言 由于本人水平有限&#xff0c;难免出现错漏&#xff0c;…

chrome_elf.dll丢失怎么办?修复chrome_elf.dll文件的方法

Chrome是目前最受欢迎的网络浏览器之一&#xff0c;然而有时用户可能会遇到Chrome_elf.dll丢失的问题。该DLL文件是Chrome浏览器的一个重要组成部分&#xff0c;负责启动和管理程序的各种功能。当Chrome_elf.dll丢失时&#xff0c;用户可能无法正常启动Chrome或执行某些功能。本…

springboot jpa手动事务

创建springboot项目 搭建最简单的SpringBoot项目_Steven-Russell的博客-CSDN博客 引入jpa和数据据依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-jpa</artifactId> </dependency>…

手搓消息队列【RabbitMQ版】

什么是消息队列&#xff1f; 阻塞队列&#xff08;Blocking Queue&#xff09;-> 生产者消费者模型 &#xff08;是在一个进程内&#xff09;所谓的消息队列&#xff0c;就是把阻塞队列这样的数据结构&#xff0c;单独提取成了一个程序&#xff0c;进行独立部署~ --------&…

yolov8 模型部署--TensorRT部署-c++服务化部署

写目录 yolov8 模型部署--TensorRT部署1、模型导出为onnx格式2、模型onnx格式转engine 部署 yolov8 模型部署–TensorRT部署 1、模型导出为onnx格式 如果要用TensorRT部署YOLOv8&#xff0c;需要先使用下面的命令将模型导出为onnx格式&#xff1a; yolo export modelyolov8n.p…

【算法】常见位运算总结

目录 1.基础位运算2. 给一个数n&#xff0c;确定它的二进制表示中的第x位是0还是13.将一个数n的二进制表示的第x位修改成14.将一个数n的二进制表示的第x位修改成0、5. 位图的思想6.提取一个数(n)二进制表示中最右侧的17.干掉一个数(n)二进制表示中最右侧的18.位运算的优先级9.异…

华为OD七日集训第4期 - 按算法分类,由易到难,循序渐进,玩转OD

目录 一、适合人群二、本期训练时间三、如何参加四、7日集训第4期五、精心挑选21道高频100分经典题目&#xff0c;作为入门。第1天、数据结构第2天、滑动窗口第3天、贪心算法第4天、二分查找第5天、分治递归第6天、深度优先搜索dfs算法第7天、宽度优选算法&#xff0c;回溯法 六…

SpringBoot2.0(过滤器,监听器,拦截器)

目录 一&#xff0c;过滤器1.1&#xff0c;自定义Filter1.2&#xff0c;启动类代码1.2&#xff0c;创建filter类和LoginFilter包1.2.1&#xff0c;编写loginFilter类 过滤器代码1.2.2&#xff0c;创建二个Controller类 二&#xff0c;监听器2.1&#xff0c;自定义监听器2.2&…