专栏首页hui数据结构 - 栈和队列

数据结构 - 栈和队列

数据结构 - 栈和队列
  • 栈和队列的定义
  • 栈的定义和特点
    • 栈的相关概念
    • 栈的示意图
  • 栈的应用
  • 队列的定义和特点
    • 队列的示意图
  • 队列的常见应用

栈和队列的定义

  • 栈和队列是两种常用的、重要的数据结构
  • 栈和队列是限定插入和删除只能在表的 “端点” 进行的 线性表
    • 栈和队列是线性表的子集(是插入和删除位置受限的线性表)

栈的定义和特点

栈(stack) 是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。表尾的一端有其特殊含义,称为 栈顶(top) ,相应地,表头称为 栈底(bottom)

栈的特点就是 后进先出(LIFO, Last In First Out)。

为了更好的理解,我们可以把栈想象成 手电筒、子弹夹。像手电筒装电池,后进去的电池先拿出来。

子弹夹也是,最后填充的子弹在子弹夹的顶端,最先填充的子弹在尾端。

栈的相关概念

  • 插入元素到 栈顶 的操作,称为 入栈(Push)
  • 栈顶 删除最后一个元素的操作,称为 出栈(Pop)

栈的示意图

栈的应用

由于栈的操作具有 后进先出 的固有特性,使得栈成为程序设计中的有用工具。另外,如果问题解的过程具有 后进先出 的天然特性话,则求解的算法中也必然需要利用 。例如:

数制转换

表达式求值

括号匹配的检验

八皇后问题

行编辑程序

函数调用

迷宫求解

递归调用的实现

队列的定义和特点

在队列中,只允许在一端进行插入,而在另一端删除元素。允许插入的一端叫做 队尾(rear) ,允许删除的一端则称为 队头(front)

队列的特点就是 先进先出(FIFO, First In First Out)。

队列的示意图

队列的常见应用

由于队列的操作具有 先进先出 的特性,使得队列成为程序设计中解决突似 排队问题 的有用工具。

例如:

  • 脱机打印输出:按申请的先后顺序依次输出。
  • 多用户系统中,多个用户排成队,分时地循环使用CPU和主存。
  • 按用户的优先级排成多个队,每个优先级一个队列。
  • 实时控制系统中,信号按接收的先后顺序依次处理。
  • 网络电文传输,按到达的时间先后顺序依次进行。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C语言实现顺序队列

    顺序队列和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个 “指针” front 和 rear...

    忆想不到的晖
  • C语言实现循环队列

    2️⃣:入队a1、a2、a3,q -> front = 0, q -> rear = 3

    忆想不到的晖
  • Markdown的语法介绍+Typora的简单使用

    Markdown是一种可以使用普通文本编辑器编写的标记语言,通过简单的标记语法,它可以使普通文本内容具有一定的格式。

    忆想不到的晖
  • liteos队列

    队列又称消息队列,是一种常用于任务间通信的数据结构,实现了接收来自任务或中断的不固定长度的消息,并根据不同的接口选择传递消息是否存放在自己空间。任务能够从队列里...

    233333
  • 消息队列的理解

    队列的主要作用是消除高并发访问高峰,加快网站的响应速度。消息队列在大型电子商务类网站,如京东、淘宝、去哪儿等网站有着深入的应用,

    葆宁
  • 解读Java阻塞队列BlockingQueue的实现

    上篇文章我们介绍了队列的基类接口Queue它定义了所有实现队列的类必须拥有的方法行为而BlockingQueue阻塞队列接口继承了Queue接口,此外Block...

    我是攻城师
  • 什么是消息队列?

    消息队列不知道大家看到这个词的时候,会不会觉得它是一个比较高端的技术,反正我是觉得它好像是挺牛逼的。

    mafeifan
  • 什么是消息队列?

    公司用到的很多技术,自己之前都没学过(尬),于是只能慢慢补了。这次给大家写写我学习消息队列的笔记,希望对大家有帮助。

    用户4447430
  • 死信队列的消息处理方案

    应该是处理此条消息的时候,实体类未序列化?然后我重试下,将实体类序列化去掉,这在运行时会直接异常的,目前原因不详。

    疯狂的KK
  • Java 并发集合的实现原理

    可以用原子方式更新int值。类 AtomicBoolean、AtomicInteger、AtomicLong 和 AtomicReference 的实例各自提供...

    哲洛不闹

扫码关注云+社区

领取腾讯云代金券