【C语言/数据结构】栈:从概念到两种存储结构的实现


目录

一、栈的概念

二、栈的两种实现方式

1.顺序表实现栈

2.链表实现栈

三、栈的顺序存储结构及其实现

1.栈的声明

2.栈的初始化

3.栈的销毁

4.栈的压栈

5.栈的弹栈

6.栈的判空

7.返回栈顶元素

8.返回栈的长度

四、栈的链式存储结构及其实现

1.栈的声明

2.栈的初始化

3.栈的销毁

4.栈的压栈

5.栈的弹栈

6.栈的判空

7.返回栈顶元素

8.返回栈的长度


一、栈的概念

  • 栈的定义:栈是一种特殊的线性表;但在概念上又有一些规定,栈只允许在一端进行数据的插入与删除的操作,被称为栈顶,而另一端则被称为栈底
  • 出栈(弹栈):在栈顶进行数据的删除
  • 入栈(压栈):在栈底进行数据的插入      
  • LIFO原则:栈中的数据服从后进先出原则(last in first out)

二、栈的两种实现方式

1.顺序表实现栈

  • 设计思路:将数组下标为0的位置作为栈底,而数组的最大下标(即长度减一)作为栈顶元素可能存在的位置;用top指向栈顶元素下一位置的索引
  • 压栈:栈的压栈操作,即为顺序表的尾插
  • 弹栈:栈的弹栈操作,即为顺序表的尾删
  • 设计优势:避免了数组增加删除数据时候需要移动数据;压栈与弹栈的时间复杂度为O(1)
  • 自身优势:缓冲区的利用率高;用一段连续的物理地址来存储数据
  • 缺点:动态顺序表实现的栈需要扩容,而扩容会导致空间浪费或性能消耗

2.链表实现栈

  • 设计思路:将单链表的尾部作为栈底,将链表的头部作为栈顶;链表的头指针指针栈顶元素的位置
  • 压栈:栈的压栈操作,即为链表的头插
  • 弹栈:栈的弹栈操作,即为链表的头删
  • 设计优势:避免了链表删除数据结点的时候,需要找到该结点的前一个结点;压栈与弹栈的时间复杂度为O(1)
  • 自身优势:没有扩容所带来的空间的浪费与性能的消耗
  • 缺点:缓存利用率不如顺序表高

三、栈的顺序存储结构及其实现

1.栈的声明

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>#define STDateType int typedef struct Stack
{STDateType* date;int top;int capacity;
}ST;void STInit(ST* st);
void STDestory(ST* st);
void STPush(ST* st, STDateType x);
void STPop(ST* st);
STDateType STTop(ST* st);
bool STEmpty(ST* st);
int STSize(ST* st);

2.栈的初始化

void STInit(ST* st)
{assert(st);st->date = NULL;st->capacity = st->top = 0;
}

3.栈的销毁

void STDestory(ST* st)
{assert(st);free(st->date);st->date = NULL;st->top = 0;st->capacity = 0;
}

4.栈的压栈

void STPush(ST* st, STDateType x)
{assert(st);if (st->top == st->capacity){size_t newcapacity = (st->capacity == 0 ? 4 : 2 * st->capacity);STDateType* tmp = (STDateType*)realloc(st->date, sizeof(STDateType) * newcapacity);if (tmp != NULL){st->date = tmp;st->capacity = newcapacity;}}st->date[st->top++] = x;
}

5.栈的弹栈

void STPop(ST* st)
{assert(st);assert(st->top > 0);st->top--;
}

6.栈的判空

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

7.返回栈顶元素

STDateType STTop(ST* st)
{assert(st);assert(st->top > 0);return st->date[st->top - 1];
}

8.返回栈的长度

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

四、栈的链式存储结构及其实现

1.栈的声明

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>typedef int StDateType;typedef struct StackNode
{StDateType date;struct StackNode* next;
}StackNode;typedef struct Stack
{StackNode* top;size_t size;
}Stack;void StackInit(Stack* st);//初始化
void StackDestory(Stack* st);//销毁
void StackPush(Stack* st, StDateType x);//压栈
void StackPop(Stack* st);//弹栈
StDateType StackTop(Stack* st);//读取栈顶元素
bool StackEmpty(Stack* st);//判空
size_t StackSize(Stack* st);//返回栈的长度

2.栈的初始化

void StackInit(Stack* st)
{assert(st);st->top = NULL;st->size = 0;
}

3.栈的销毁

void StackDestory(Stack* st)
{assert(st);while (st->size > 0)StackPop(st);
}

4.栈的压栈

void StackPush(Stack* st, StDateType x)
{assert(st);StackNode* Node = (StackNode*)malloc(sizeof(StackNode));if (!Node){perror("malloc mistake");exit(-1);}Node->date = x;Node->next = NULL;Node->next = st->top;st->top = Node;st->size++;
}

5.栈的弹栈

void StackPop(Stack* st)
{assert(st);assert(st->top);StackNode* tmp = st->top;  st->top = st->top->next;  free(tmp);  st->size--;  
}

6.栈的判空

bool StackEmpty(Stack* st)
{assert(st);return st->top == NULL;
}

7.返回栈顶元素

StDateType StackTop(Stack* st)
{assert(st);return st->top->date;
}

8.返回栈的长度

size_t StackSize(Stack* st)
{assert(st);assert(st->top);return st->size;
}

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

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

相关文章

【SRC实战】前端脱敏信息泄露

挖个洞先 https://mp.weixin.qq.com/s/xnCQQCAneT21vYH8Q3OCpw “ 以下漏洞均为实验靶场&#xff0c;如有雷同&#xff0c;纯属巧合 ” 01 — 漏洞证明 一、前端脱敏&#xff0c;请求包泄露明文 “ 前端脱敏处理&#xff0c;请求包是否存在泄露&#xff1f; ” 1、获取验…

3.整数运算

系列文章目录 信息的表示和处理 : Information Storage&#xff08;信息存储&#xff09;Integer Representation&#xff08;整数表示&#xff09;Integer Arithmetic&#xff08;整数运算&#xff09;Floating Point&#xff08;浮点数&#xff09; 文章目录 系列文章目录前…

钟表——蓝桥杯十三届2022国赛大学B组真题

问题分析 这个问题的关键有两点&#xff1a;1.怎么计算时针&#xff0c;分针&#xff0c;秒针之间的夹角&#xff0c;2.时针&#xff0c;分针&#xff0c;秒针都是匀速运动的&#xff0c;并非跳跃性的。问题1很好解决看下面的代码就能明白&#xff0c;我们先考虑问题2&#xf…

Springboot+Vue项目-基于Java+MySQL的车辆管理系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…

Rx(Reactive Extensions)的由来

既然我们已经介绍了响应式编程&#xff0c;现在是时候了解我们的明星了:响应式扩展&#xff0c;通常简称为Rx。微软开发了Reactive扩展库&#xff0c;使其易于处理事件流和数据流。在某种程度上&#xff0c;时变值本身就是一个事件流;每个值更改都是一种类型的事件它会更新依赖…

Vue中使用$t(‘xxx‘)实现中英文切换;

&#xff08;原文链接&#xff09; 介绍 {{$t(key)}} &#xff1a;是VueI18n插件提供的函数&#xff0c;主要用于根据当前语言环境返回对应的翻译文本&#xff0c;以便在页面上显示多语言内容。 key&#xff1a;作为参数传递给函数$t()的字符串&#xff0c;用于指定需要翻译的…

【C++要哮着学】初识C++,什么是C++?什么是命名空间?什么又是缺省函数?

文章目录 前言1、C简介1.1、什么是C1.2、C起源1.3、C发展 2、C关键字&#xff08;C98&#xff09;3、命名空间3.1、命名空间的定义及使用3.2、命名空间的嵌套3.3、命名空间的三种使用方式3.3.1、加命名空间名称及作用域限定符3.3.2、使用using将命名空间中某个成员引入3.3.3、使…

MySQL 通过 systemd 启动时 hang 住了……

mysqld&#xff1a;哥&#xff0c;我起不来了…… 作者&#xff1a;贲绍华&#xff0c;爱可生研发中心工程师&#xff0c;负责项目的需求与维护工作。其他身份&#xff1a;柯基铲屎官。 爱可生开源社区出品&#xff0c;原创内容未经授权不得随意使用&#xff0c;转载请联系小编…

【Docker学习】重启容器的docker restart

命令&#xff1a; docker container restart 描述&#xff1a; 重启一个或多个容器 用法&#xff1a; docker container restart [OPTIONS] CONTAINER [CONTAINER...] 别名&#xff1a; docker restart(docker的一些命令可以简写&#xff0c;docker restart就等同于docker cont…

SQLZOO:The JOIN operation

数据表&#xff1a;game-gaol-eteam game idmdatestadiumteam1team210018 June 2012National Stadium, WarsawPOLGRE10028 June 2012Stadion Miejski (Wroclaw)RUSCZE100312 June 2012Stadion Miejski (Wroclaw)GRECZE100412 June 2012National Stadium, WarsawPOLRUS... goal …

UE4_照亮环境_不同雾效的动态切换

一、问题及思路&#xff1a; 我们在一个地图上&#xff0c;经常切换不同的区域&#xff0c;不同的区域可能需要不同的色调&#xff0c;例如暖色调的野外或者幽暗的山洞&#xff0c;这两种环境上&#xff0c;雾效的选用肯定不一样&#xff0c;夕阳西下的户外用的就是偏暖的色调&…

【小白的大模型之路】基础篇:Transformer细节

基础篇&#xff1a;Transformer 引言模型基础架构原论文架构图EmbeddingPostional EncodingMulti-Head AttentionLayerNormEncoderDecoder其他 引言 此文作者本身对transformer有一些基础的了解,此处主要用于记录一些关于transformer模型的细节部分用于进一步理解其具体的实现机…

LeetCode_栈和队列相关OJ题目

✨✨所属专栏&#xff1a;LeetCode刷题专栏✨✨ ✨✨作者主页&#xff1a;嶔某✨✨ 上一篇&#xff1a;数据结构_栈和队列(Stack & Queue)-CSDN博客 有效的括号 解析: 这里我们用数组实现的栈来解决这个问题&#xff0c;在有了栈的几个基础接口之后&#xff0c;我们运用这…

【Chrome实用命令笔记】

文章目录 Chrome实用命令笔记1、chrome基本介绍2. 打开开发者工具&#xff08;DevTools&#xff09;方法一&#xff1a;快捷键方法二&#xff1a;右键菜单方法三&#xff1a;浏览器设置 2. 开发者工具面板Elements面板Console面板Sources面板Network面板Performance面板Memory面…

(done) Beam search

参考视频1&#xff1a;https://www.bilibili.com/video/BV1Gs421N7S1/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 &#xff08;beam search 视频&#xff09; 参考博客1&#xff1a;https://jasonhhao.github.io/2020/06/19/…

Springboot项目如何创建单元测试

文章目录 目录 文章目录 前言 一、SpringBoot单元测试的使用 1.1 引入依赖 1.2 创建单元测试类 二、Spring Boot使用Mockito进行单元测试 2.1 Mockito中经常使用的注解以及注解的作用 2.2 使用Mockito测试类中的方法 2.3 使用Mockito测试Controller层的方法 2.4 mock…

通过 Java 操作 redis -- list 列表基本命令

目录 使用命令 lpush&#xff0c;lrange&#xff0c;rpush 使用命令 lpop 和 rpop 使用命令 blpop&#xff0c;brpop 使用命令 llen 关于 redis list 列表类型的相关命令推荐看Redis - list 列表 要想通过 Java 操作 redis&#xff0c;首先要连接上 redis 服务器&#xff…

电信网关配置管理系统 rewrite.php 文件上传致RCE漏洞复现

0x01 产品简介 中国电信集团有限公司(英文名称“China Telecom”、简称“中国电信”)成立于2000年9月,是中国特大型国有通信企业、上海世博会全球合作伙伴。电信网关配置管理系统是一个用于管理和配置电信网络中网关设备的软件系统。它可以帮助网络管理员实现对网关设备的远…

【Android】源码解析Activity的结构分析

源码解析Activity的结构分析 目录 1、Activity、View、Window有什么关联&#xff1f;2、Activity的结构构建流程3 源码解析Activity的构成 3.1 Activity的Attach方法3.2 Activity的OnCreate 4、WindowManager与View的关系总结 1、一个Activity对应几个WindowManage&#xff0…

【MySQL数据库开发设计规范】之字段设计规范

欢迎点开这篇文章&#xff0c;自我介绍一下哈&#xff0c;本人姑苏老陈 &#xff0c;是一名JAVA开发老兵。 本文收录于 《MySQL数据库开发设计规范》专栏中&#xff0c;该专栏主要分享一些关于MySQL数据库开发设计相关的技术规范文章&#xff0c;定期更新&#xff0c;欢迎关注&…