美文网首页
数据结构之栈和队列

数据结构之栈和队列

作者: iOSLover | 来源:发表于2019-11-03 12:53 被阅读0次
回顾一下上章我们学的线性表 是 零个或多个数据元素的有限序列,以及她的抽象数据类型:

线性表分为 顺序存储结构 与 链式存储结构

顺序存储结构:是用一段地址连续的存储单元来依次存放线性表的元素。例如:数组
链式存储结构:不收固定存储空间,引入指针的概念来快速的实现数据元素的插入,删除操作的链式存储结构。分类为:单链表,双链表,循环链表,,静态链表(额外理解不使用指针去实现链式存储结构)。

裂解了线性表后,下面我们正式介绍一下栈和队列:

限定只能在栈尾插入和删除操作的线性表。

我们知道栈是一个线性表,只是它的操作比较特殊,限定操作的位置的线性表。通常我们把可以删除和插入的一端叫做栈顶,相反另一端叫做栈底,这里有几个概念:

LIFO 结构(last in first out) 后进先出

我们需要知道有一些人程也叫他LIFO结构,因为栈的数据元素操作顺序为后进先出

进栈 压栈 入栈

栈的插入操作

出栈 弹栈

栈的删除操作

既然栈为一种特殊线性表我们就来探讨一下栈的顺序存储方式和链式存储方式:

栈的顺序存储方式

不同于一般的线性表而言,栈的顺序存储方式的操作,删除和插入时间复杂度均为O(1),他不涉及到操作后元素的移动,仅仅操作栈尾的位置。
我们都知道顺序存储方式的缺点:空间分配固定,我们想想有没有既要空间高效而且又不会出现溢出的栈呢,那么久诞生了共享栈事实上它处理的问题局限比较大这里就不深入讲解了。

栈的链式存储方式

这里需要注意的是栈的链式存储结构因为栈顶就在线性表的头部,所以我们不在需要头结点,我们把头指针直接指向栈顶,它的进栈,出栈操作仅限于栈顶,所以时间复杂度也为O(1).

栈的应用
递归
例子:斐波那契数列的实现
四则运算法则
例子:后缀(逆波兰)标识定义法

队列

只允许在一端进行插入操作,另一端进行删除操作的线性表。

与栈类似的是,他也是一种特殊的线性表,限定在一端删除,一端插入的特殊线性表。这里它也有几个概念:

FIFO(first in first out)先进先出

我们可以类比生活中的排队

队头

我们把允许删除的一端叫做队头

队尾

我们把允许插入的一端叫做队尾

同样我们来分析一下队列的顺序存储方式和链式存储方式:

队列的顺序存储方式

我们延伸出循环队列这个概念。它是一种头尾相接的顺序存储方式。我们通过改变头指针和尾指针的方式来实现。

队列的链式存储方式

因为它仅仅在队尾和队头进行插入和删除操作,所以他的时间复杂度也均为O(1).

相关文章

  • 实战PHP数据结构基础之栈

    栈和队列 栈和队列和之前讲到的实战PHP数据结构基础之双链表 一样都是线性结构。 栈有什么特点 栈遵循后进先出的原...

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 栈和队列—什么是栈

    栈和队列是两种重要的数据结构 从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子...

  • 栈和队列—什么是队列

    栈和队列是两种重要的数据结构 从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子...

  • 队列和栈的应用

    队列和栈的使用 标签(空格分隔): algorithm 队列和栈的应用 1.队列的应用 队列是一种常见的数据结构,...

  • 泡杯茶,我们坐下聊聊javascript事件环

    栈和队列 在计算机内存中存取数据,基本的数据结构分为栈和队列。 栈(Stack)是一种后进先出的数据结构,注意,有...

  • 算法导论 基本数据结构

    MIT公开课没有讲到的内容,介绍几种基本数据结构- 栈和队列- 链表- 二叉树 栈和队列 栈和队列都是动态集合,元...

  • 栈、队列和链表

    基本数据结构 栈和队列 栈和队列都是动态集合。栈实现的是一种后进先出策略。队列是一种先进先出策略。 栈 栈上的in...

  • 数据结构:栈和队列

    栈和队列 栈和队列是软件设计中常用的两种数据结构,逻辑结构和线性表相同。 特点: 栈: "先进后出"队列:"先进先...

  • 数据结构 栈和队列

    数据结构 栈和队列 栈 顺序栈 top = -1 链栈 初始化 判断队空 入队: 头插法 出队: 单链表删除 队列...

网友评论

      本文标题:数据结构之栈和队列

      本文链接:https://www.haomeiwen.com/subject/kwvkbctx.html