前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构 - 栈和队列

数据结构 - 栈和队列

作者头像
忆想不到的晖
发布2020-07-15 11:45:21
4090
发布2020-07-15 11:45:21
举报
文章被收录于专栏:hui

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

栈和队列的定义

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

栈的定义和特点

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

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

图解栈的后进先出的特性
图解栈的后进先出的特性

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

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

栈的相关概念
  • 插入元素到 栈顶 的操作,称为 入栈(Push)
  • 栈顶 删除最后一个元素的操作,称为 出栈(Pop)
栈的示意图
栈的示意图
栈的示意图

栈的应用

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

数制转换

表达式求值

括号匹配的检验

八皇后问题

行编辑程序

函数调用

迷宫求解

递归调用的实现

队列的定义和特点

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

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

图解队列的先进先出的特性
图解队列的先进先出的特性
队列的示意图
队列的示意图
队列的示意图

队列的常见应用

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

例如:

  • 脱机打印输出:按申请的先后顺序依次输出。
  • 多用户系统中,多个用户排成队,分时地循环使用CPU和主存。
  • 按用户的优先级排成多个队,每个优先级一个队列。
  • 实时控制系统中,信号按接收的先后顺序依次处理。
  • 网络电文传输,按到达的时间先后顺序依次进行。
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/06/22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据结构 - 栈和队列
  • 栈和队列的定义
  • 栈的定义和特点
    • 栈的相关概念
      • 栈的示意图
      • 栈的应用
      • 队列的定义和特点
        • 队列的示意图
        • 队列的常见应用
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档