C++ 栈和队列的实现超详细解析

目录
  • 1、栈的介绍：
  • 2、栈的常用接口实现
  • 3、队列的介绍
  • 4、队列的常用接口实现

可算是把链表给结束了，很多小伙伴已经迫不及待想看到栈和队列了，那么它来了！相信有了顺序表和链表的基础，栈和队列对于你们来讲也是轻轻松松，那我就废话不多说，直接进入今天的重点：

1、栈的介绍：

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上 插入数据的代价比较小。

本次我们是用动态数组来实现栈！静态栈在实际中一般不实用！

2、栈的常用接口实现

首先是我们动态栈的结构：

有了顺序表和链表的基础我就直接上代码了！

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

栈的初始化：

入栈操作：

出栈操作：

出栈就很简单了，我们直接使top--就可以了，因为我们插入数据是先在top位置插入，然后再top++，这样我们下次插入数据就会覆盖pos位置的数据！注意：当栈没有初始化，没有数据的情况下不能进行出栈操作！

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

取栈顶元素操作：

我们知道top是栈顶元素的后一个，所以我们直接取top-1下标位置的数据就可以！

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

求栈的节点个数：

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

判断栈是否为空：

我们使用返回值为bool型的函数，bool类型只会返回true或false见下代码：

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

销毁栈操作：

记得养成释放动态内存的习惯哦！

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

栈相对来说还是比较简单了，栈的基本接口就到这里了，下面我们来实现队列的基本接口操作！

3、队列的介绍

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列，进行删除操作的一 端称为队头！

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构， 出队列在数组头上出数据，效率会比较低。

4、队列的常用接口实现

赞 (0)

相关推荐

  • Java数据结构专题解析之栈和队列的实现

    Java数据结构专题解析之栈和队列的实现

    目录 1. 栈 1.1 概念 1.2 助解图题 1.3 栈的数组实现 1.4 问题 1.5 栈的单链表实现 2. 队列 2.1 概念 2.2 问题 2.3 队列的单链表实现 2.4 数组实现队列 2.5 循环队列 2.6 双端队列 3. 栈和队列练习题 3.1 有效的括号 3.2 用队列实现栈 3.3 用栈实现队列 3.4 实现一个最小栈 3.5 设计循环队列 1. 栈 1.1 概念 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作. 特点:栈中的数据元素遵循先进后出的原则,但

  • Java特性队列和栈的堵塞原理解析

    做消息通信,消息会不断从网络流中取得,而后台也有线程不断消费.本来我一直是使用一些线程安全标识或方法来控制,后来在网上找到一些java新特性,里面包含了可以用到的堆栈使用,而且是堵塞的,这样至少可以保证一些安全性. 对于堆: BlockingQueue 不接受 null 元素.试图 add.put 或 offer 一个 null 元素时,某些实现会抛出 NullPointerException.null 被用作指示 poll 操作失败的警戒值. BlockingQueue 可以是限定容量的.它在

  • Java 栈和队列的相互转换详解

    Java 栈和队列的相互转换详解

    目录 用栈实现队列-力扣232题 用队列实现栈-力扣225题  1. 双队列实现栈 2.一个队列实现栈 栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除.因此,栈和队列可以相互转换. 用栈实现队列-力扣232题 题目要求:仅使用两个栈实现先入先出队列.队列应当支持一般队列支持的所有操作 使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助  上图可以看到,新元素进栈时,要确保该栈为空.进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中.

  • Java栈和基础队列的实现详解

    Java栈和基础队列的实现详解

    目录 栈(stack) 栈支持的三个核心操作: 栈的常见实际应用: 栈的实现 队列 无论是哪种队列,都必须支持三个核心操作: 基础队列的实现 栈和队列:都是线性表,都是基于List基础上的实现 线性表:数组,链表,字符串,栈,队列 元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素 栈(stack) 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)

  • Java深入了解数据结构之栈与队列的详解

    Java深入了解数据结构之栈与队列的详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现 ①入栈 ②出栈 ③获取栈顶元素 ④判断栈是否为空 4,实现mystack 二,队列 1,概念 2,队列的实现 ①入队 ②出队 ③获取队首元素 3,实现myqueue 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的

  • Java数据结构学习之栈和队列

    Java数据结构学习之栈和队列

    一.栈 1.1 概述 Java为什么要有集合类: 临时存储数据. 链表的本质: 对象间通过持有和引用关系互相关联起来. 线性表: 普通线性表, 操作受限线性表(某些操作受到限制 --> 某一个线性表它的增删改操作受到限制) --> 栈 & 队列 1.1.1 线性表的概念 (1)线性表:n个数据元素的有序序列. ①首先,线性表中元素的个数是有限的. ②其次,线性表中元素是有序的. (2)那这个"序"指的是什么呢? ①除表头和表尾元素外,其它元素都有唯一前驱和唯一后继,

  • Java数据结构之栈与队列实例详解

    Java数据结构之栈与队列实例详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现  4,实现mystack 二,队列 1,概念  2,队列的实现  3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页.   很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的

  • C++ 栈和队列的实现超详细解析

    C++ 栈和队列的实现超详细解析

    目录 1.栈的介绍: 2.栈的常用接口实现 3.队列的介绍 4.队列的常用接口实现 可算是把链表给结束了,很多小伙伴已经迫不及待想看到栈和队列了,那么它来了!相信有了顺序表和链表的基础,栈和队列对于你们来讲也是轻轻松松,那我就废话不多说,直接进入今天的重点: 1.栈的介绍: 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则. 压栈:栈的插入操作叫做

  • Go语言单元测试超详细解析

    目录 一.单元测试分类及其概念 1.基本分类 2.细说单元测试分类 二.结合代码细说每一种测试 1.基准测试 2.组测试与子测试 三.pprof调试工具 1.对主函数进行传参 2.pprof性能调优 前言: 平时根据需求写代码.人工进行测试往往不会面面俱到,还会因为需求的改变繁琐的进行测试通过完成一个测试函数,可以大大简化测试的步骤,并且在需求该变的时候只需要改变一下测试的输入与期望 一.单元测试分类及其概念 1.基本分类 测试函数 函数前缀为Test 主要用于测试程序的一些逻辑行为是否正确 基

  • 超详细解析C++实现快速排序算法的方法

    目录 一.前言 1.分治算法 2.分治算法解题方法 二.快速排序 1.问题分析 2.算法设计 3.算法分析 三.AC代码 一.前言 1.分治算法 快速排序,其实是一种分治算法,那么在了解快速排序之前,我们先来看看什么是分治算法.在算法设计中,我们引入分而治之的策略,称为分治算法,其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题,分而治之. 2.分治算法解题方法 1.分解: 将要解决的问题分解为若干个规模较小.相互独立.与原问题形式相同的子问题. 2.治理: 求解各个子问题.由于各个子

  • 超详细解析C++实现归并排序算法

    目录 一.前言 分治算法 分治算法解题方法 二.归并排序 1.问题分析 2.算法设计 3.算法分析 三.AC代码 一.前言 分治算法 归并排序,其实就是一种分治算法 ,那么在了解归并排序之前,我们先来看看什么是分治算法.在算法设计中,我们引入分而治之的策略,称为分治算法,其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题,分而治之. 分治算法解题方法 1.分解: 将要解决的问题分解为若干个规模较小.相互独立.与原问题形式相同的子问题. 2.治理: 求解各个子问题.由于各个子问题与原问题

  • C++带头双向循环链表超详细解析

    C++带头双向循环链表超详细解析

    目录 什么是带头双向循环链表 带头双向循环链表常用接口实现 上期我们讲完了无头单向非循环链表,这期我们接着来讲链表中结构最复杂的带头双向循环链表! 本期主要内容: 什么是带头双向循环链表? 带头双向循环链表常用接口实现! 顺序表和链表的区别和联系! 什么是带头双向循环链表 什么是带头?双向?循环?(带头双向循环链表) 带头:代表链表存在一个哨兵位节点,也就是头节点,这个节点不存放任何的有效数据! 双向:每个节点都有两个指针,分别指向它的前一个节点和后一个节点! 循环:最后一个节点next不再指向

  • C++ 二叉树的实现超详细解析

    C++ 二叉树的实现超详细解析

    目录 1.树的概念及结构(了解) 1.1树的概念: 1.2树的表示法: 2.二叉树的概念及结构 2.1二叉树的概念: 2.2特殊的二叉树: 2.3二叉树的性质: 2.4二叉树的顺序存储: 2.5二叉树的链式存储: 3.二叉树链式结构的实现 3.1二叉树的前中后序遍历: 3.2求二叉树的节点个数: 3.3求二叉树的叶子节点个数: 3.4销毁二叉树: 1.树的概念及结构(了解) 1.1树的概念: 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看

  • Go语言实现栈与队列基本操作学家

    Go语言实现栈与队列基本操作学家

    目录 一.前言 二.实现栈与队列基本操作 2.1 栈基本操作 2.2 队列基本操作 三.用栈实现队列 3.1 理论 3.2 算法题 3.3 思路 3.4 代码部分 四.用队列实现栈 4.1 理论 4.2 算法题 4.3 思路 4.4 使用两个队列实现 4.5 优化 4.6 使用一个队列实现 一.前言 go语言中,并没有栈与队列相关的数据结构,但是我们可以借助切片来实现栈与队列的操作:接下来我们一起实现栈与队列基本操作,并且还会实现用栈实现队列,用队列实现栈的操作. 二.实现栈与队列基本操作 2.

  • C语言超详细讲解栈与队列实现实例

    C语言超详细讲解栈与队列实现实例

    目录 1.思考-1 2.栈基本操作的实现 2.1 初始化栈 2.2 入栈 2.3 出栈 2.4 获取栈顶数据 2.5 获取栈中有效元素个数 2.6 判断栈是否为空 2.7 销毁栈 3.测试 3.1测试 3.2测试结果 4.思考-2 5.队列的基本操作实现 5.1 初始化队列 5.2 队尾入队列 5.3 队头出队列 5.4 队列中有效元素的个数 5.5 判断队列是否为空 5.6 获取队头数据 5.7 获取队尾的数据 5.8 销毁队列 6.测试 6.1测试 6.2 测试结果 1.思考-1 为什么栈用

  • Java 栈与队列超详细分析讲解

    Java 栈与队列超详细分析讲解

    目录 一.栈(Stack) 1.什么是栈? 2.栈的常见方法 3.自己实现一个栈(底层用一个数组实现) 二.队列(Queue) 1.什么是队列? 2.队列的常见方法 3.队列的实现(单链表实现) 4.循环队列 一.栈(Stack) 1.什么是栈? 栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底) 什么是java虚拟机栈? java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 jav

  • C语言超详细讲解队列的实现及代码

    C语言超详细讲解队列的实现及代码

    目录 前言 队列的概念 队列的结构 队列的应用场景 队列的实现 创建队列结构 队列初始化 队列销毁 入队列 出队列 队列判空 获取队列元素个数 获取队列头部元素 获取队列尾部元素 总代码 Queue.h 文件 Queue.c 文件 Test.c 文件 前言 队列的概念 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列和前文所学的栈

随机推荐