看完书上的栈不过瘾,为什么不动手试试呢?

一.栈的基本概念

1.栈的定义

(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作

其中注意几点:

栈顶(Top):线性表允许进行插入删除的那一端。

栈底(Bottom):固定的,不允许进行插入和删除的另一端。

空栈:不含任何元素的空表。

栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构

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); 

二.栈的顺序存储结构

1.栈的顺序存储

采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置。

若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判断条件定位top等于-1。

当然我们也可以把top初始化成零,这样top指针就指向栈顶的下一个元素,只不过我们在实现的时候依然是通过指针的偏移量来对栈顶的元素来进行访问,所以两种初始化都是可以的,都是先存数据在移动指针。

2.顺序栈的基本算法

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

typedef int STDatatype;
typedef struct Stack
{
    STDatatype* a;
    int capacity;
    int top;   // 初始为0,表示栈顶位置下一个位置下标
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
STDatatype StackTop(ST* ps);

bool StackEmpty(ST* ps);
int StackSize(ST* ps);

3.顺序栈的实现

#include "Stack.h"

void StackInit(ST* ps)
{
    assert(ps);

    //ps->a = NULL;
    //ps->top = 0;
    //ps->capacity = 0;

    ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
    if (ps->a == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }

    ps->top = 0;
    ps->capacity = 4;
}

void StackDestroy(ST* ps)
{
    assert(ps);

    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDatatype x)
{
    assert(ps);

    // 
    if (ps->top == ps->capacity)
    {
        STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }

        ps->a = tmp;
        ps->capacity *= 2;
    }

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

// 20:20
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    ps->top--;
}

STDatatype StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

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

bool StackEmpty(ST* ps)
{
    assert(ps);

    /*if (ps->top == 0)
    {
        return true;
    }
    else
    {
        return false;
    }*/
    return ps->top == 0;
}

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

4.测试程序

#include"stack.h"
void test(void)
{
    ST ST1;
    StackInit(&ST1);
    StackPush(&ST1, 1);
    StackPush(&ST1, 2);
    StackPush(&ST1, 3);
    StackPush(&ST1, 4);
    while (!StackEmpty(&ST1))
    {
        printf("%d\n", StackTop(&ST1));
        StackPop(&ST1);
    }
    StackDestroy(&ST1);
}
int main()
{
    test();
}

三.栈的链式存储结构

  1. 链栈

和顺序表一样,针对顺序栈的缺点,我们可以设计出链栈,采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点,指针Lhead指向栈顶元素,如下图所示。

2.链栈的定义

typedef struct Stack
{
    Datetype x;//数据域
    ST *next   // 指针域
}ST;

3.性能分析

链栈的进栈push和出栈pop操作都很简单,时间复杂度均为O(1)。

对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

四.共享栈(节省空间)

1.共享栈概念

利用栈底位置相对不变的特征,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸,如下图所示:

两个栈的栈顶指针都指向栈顶元素,top0=-1时0号栈为空,top1=MaxSize时1号栈为空;仅当两个栈顶指针相邻(top0+1=top1)时,判断为栈满。当0号栈进栈时top0先加1再赋值,1号栈进栈时top1先减一再赋值出栈时则刚好相反。

2.设计一个共享栈

/*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef DataType int;   //ElemType的类型根据实际情况而定,这里假定为int
/*两栈共享空间结构*/
typedef struct{
    DataType a[MAXSIZE];
    int top0;    //栈0栈顶指针
    int top1;    //栈1栈顶指针
}SqDoubleStack;

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

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

相关文章

【C语言蓝桥杯每日一题】—— 单词分析

【C语言蓝桥杯每日一题】—— 单词分析&#x1f60e;前言&#x1f64c;单词分析&#x1f64c;总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右铭&#xff1a;全神贯注的上吧&#xff01;&#xff01;&#xff01; &#x1f60a;作者…

三天吃透MySQL面试八股文

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…

C 语言编程 — 线程池设计与实现

目录 文章目录目录线程池&#xff08;Thread Pool&#xff09;tiny-threadpool数据结构设计Task / JobTask / Job QueueWorker / ThreadThread Pool ManagerPublic APIsPrivate Functions运行示例线程池&#xff08;Thread Pool&#xff09; 线程池&#xff08;Thread Pool&am…

Spring Cloud学习笔记【初识微服务基础框架搭建】

文章目录微服务架构介绍架构图核心组件Spring Cloud版本对应基础框架搭建1.建造父工程2.建造子工程user工程建造auth工程建造RestTemplate 实现微服务远程调用RestTemplate 介绍配置RestTemplate测试远程访问总结微服务架构 介绍 微服务架构是一种将应用程序拆分成小型、自治…

设计模式之工厂模式

工厂模式是设计模式中的经典模式&#xff0c;工厂模式又可分为以下三种类型&#xff1a; 简单工厂模式工厂方法模式抽象工厂模式 这三种模式可以理解为同一种编程思想的三个版本&#xff0c;从简单到高级不断升级。本文将着重介绍简单工厂模式。 简单工厂模式 简单工厂模式&…

哈佛与冯诺依曼结构

1. 下图是典型的冯诺依曼结构 2. CPU分为三部分&#xff1a;ALU运算单元&#xff0c;CU控制单元&#xff0c;寄存器组。 3. 分析51单片机为何能使用汇编进行编程 51指令集&#xff08;Instruction Set&#xff09;是单片机CPU能够执行的所有指令的集合。在编写51单片机程序时&a…

Python打包成exe,文件太大问题解决办法(比保姆级还保姆级)

首先我要说一下&#xff0c;如果你不在乎大小&#xff0c;此篇直接别看了&#xff0c;因为我写过直接打包的&#xff0c;就多20M而已&#xff0c;这篇就别看了&#xff0c;点击查看不在乎大小直接打包这篇我觉得简单的令人发指 不废话&#xff0c;照葫芦画瓢就好 第1步&#…

Linux- 系统随你玩之--网络上的黑客帝国

文章目录1、前言2、TCPDump介绍2.1、问题来了&#xff1a; 所有用户都可以采用该命令吗&#xff1f;2.2、抓包原理2.3、特点2.3.1、参数化支持2.2.2、 TCP功能3、 服务器安装Tcpdump3.1、安装3.2、检查安装是否正常。4、tcpdump 命令4.1、常用功能选项4.2、输出内容5、实操5.1、…

初识C++需要了解的一些东西(2)

&#x1f601;关注博主&#xff1a;翻斗花园第一代码手牛爷爷 &#x1f603;Gitee仓库&#xff1a;牛爷爷爱写代码 目录&#x1f30d;内联函数&#x1f315;内联函数概念&#x1f316;内联函数特性&#x1f313;auto关键字(C11)&#x1f31e;类型别名⭐️auto简介☀️auto的使…

【数据库】数据库查询(进阶命令详解)

目录 1.聚合查询 1.1聚合函数 COUNT函数 SUM函数 AVG函数 MAX函数 MIN函数 1.2GROUP BY子句 1.3HAVING 2.联合查询 2.1内连接 2.2外连接 2.3自连接 2.4子查询 3.合并查询 写在前面&#xff1a; 文章截图均是每个代码显示的图。数据库对代码大小写不敏感&am…

java ArrayList源码分析(深度讲解)

ArrayList类的底层实现ArrayList类的断点调试空参构造的分步骤演示&#xff08;重要&#xff09;带参构造的分步骤演示一、前言大家好&#xff0c;本篇博文是对单列集合List的实现类ArrayList的内容补充。之前在List集合的万字详解篇&#xff0c;我们只是拿ArrayList演示了List…

C语言函数调用栈

栈溢出&#xff08;stack overflow&#xff09;是最常见的二进制漏洞&#xff0c;在介绍栈溢出之前&#xff0c;我们首先需要了解函数调用栈。 函数调用栈是一块连续的用来保存函数运行状态的内存区域&#xff0c;调用函数&#xff08;caller&#xff09;和被调用函数&#xf…

Java8使用Lambda表达式(流式)快速实现List转map 、分组、过滤等操作

利用java8新特性&#xff0c;可以用简洁高效的代码来实现一些数据处理。1 数据准备1.1 定义1个Fruit对象package com.wkf.workrecord.work;import org.junit.Test;import java.math.BigDecimal; import java.util.ArrayList; import java.util.List;/*** author wuKeFan* date …

Stable Diffusion加chilloutmixni真人图片生成模型,AI绘图杀疯了

上期图文教程,我们分享过AI绘图大模型Stable Diffusion以及中文版本文心AI绘画大模型的基础知识以及代码实现,截至到目前为止。Stable Diffusion模型已经更新到了V2.1版本,其文生图大模型也越来越火,其在2022年底,由AI绘制的图片被荣为国际大奖,让大家对AI绘画大模型也越…

Node.js-----使用express写接口

使用express写接口 文章目录使用express写接口创建基本的服务器创建API路由模块编写GET接口编写POST接口CROS跨域资源共享1.接口的跨域问题2.使用cros中间件拒绝跨域问题3.什么是cros4.cros的注意事项5.cros请求的分类JSONP接口1.回顾jsonp的概念和特点2.创建jsonp接口的注意事…

请相信总有一扇门为你而开——社科院与杜兰大学金融管理硕士项目

考研人数每年都在递增&#xff0c;考研的竞争压力也逐年增长。考研话题也备受人们关注&#xff0c;初试&#xff0c;国家线&#xff0c;复试&#xff0c;考研的每一个关卡都会冲上热搜&#xff0c;引发热议。国家线公布后&#xff0c;有人欢喜有人忧。祝福成功上岸的学子们&…

【Leetcode——排序的循环链表】

&#x1f60a;&#x1f60a;&#x1f60a; 文章目录一、力扣题之排序循环链表二、解题思路1. 使用双指针法2、找出最大节点&#xff0c;最大节点的下一个节点是最小节点&#xff0c;由此展开讨论总结一、力扣题之排序循环链表 题目如下&#xff1a;航班直达&#xff01;&#…

有什么比较好的bug管理工具?5款热门工具推荐

工具再优秀&#xff0c;适合自己才最重要。 为尽量讲透这个问题&#xff0c;本文的行文结构我先整理如下&#xff1a; 1、为什么需要bug管理工具&#xff1f; 2、好的bug管理工具的标准是什么&#xff1f; 3、好的bug管理工具推荐&#xff08;5款&#xff09; 4、如何挑选适合…

雪花算法(SnowFlake)

简介现在的服务基本是分布式、微服务形式的&#xff0c;而且大数据量也导致分库分表的产生&#xff0c;对于水平分表就需要保证表中 id 的全局唯一性。对于 MySQL 而言&#xff0c;一个表中的主键 id 一般使用自增的方式&#xff0c;但是如果进行水平分表之后&#xff0c;多个表…

【python实操】用python写软件弹窗

文章目录前言组件label 与 多行文本复选框组件Radiobutton单选组件Frame框架组件labelframe标签框架列表框Listboxscrollbar滚动条组件scale刻度条组件spinbox组件Toplevel子窗体组件PanedWindow组件Menu下拉菜单弹出菜单总结针对组件前言 python学习之路任重而道远&#xff0…
最新文章