栈与队列

本篇文章从定义、抽象数据类型和存储结构等方面,分别介绍两种特殊的线性表,即栈(Stack)和队列(Queue)。

栈的定义

栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不包含任何元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表。

栈的插入操作,叫做进栈,也称压栈、入栈;删除操作叫做出栈,也叫弹栈。

栈的抽象数据类型

ADT : 栈(Stack)

Data :同线性表。元素具有相同的类型,相邻元素具有前驱和后继的关系。

Operation

  • init(初始化,建立一个空栈)
  • clear(将栈清空)
  • isEmpty(判断栈是否为空)
  • getTop(获取栈顶元素)
  • push(入栈操作)
  • pop(出栈操作)
  • length(获取栈的元素个数)

endADT

栈的存储结构

栈为线性表的一种,存储结构跟线性表一样,分为 顺序存储结构链式存储结构 两种。

栈的顺序存储结构

栈的顺序存储结构是线性表顺序存储结构的简化,称为顺序栈,可以用一维数组来实现。

用下标为 0 的一端作为栈底,再定义一个 top 变量记录栈顶元素在数组中的位置。

当两个栈的空间需求有相反关系时(一个栈增长时另一个栈缩短),可以让两个栈共有一个数组,栈底分别在数组两段,随栈中元素增加,栈顶分别向中间靠拢。

栈的链式存储结构

栈的链式存储结构简称为链表。

定义 top 变量记录栈顶元素的指针,每个元素除数据域外还包含指向下一个元素的指针域。

两种存储结构的对比

顺序栈和链栈,进栈和出栈的时间复杂度均为 O(1)。

顺序栈需要事前确定固定的长度,可能存在空间浪费的问题,优势是存取时定位方便。

链栈没有长度的限制,但每个元素都有指针域这一额外开销。

栈的作用

栈的引入简化了程序设计,划分了不同的关注层次,使思考范围更小,更加聚焦于问题核心。

递归

一个直接调用自己,或通过一系列调用语句间接调用自己的函数,称为递归函数,是栈的一个重要应用。

每个递归定义必须至少有一个条件,满足条件时递归不再进行,即不再引用自身,返回结果值并退出。

使用递归的例子:斐波那些数列(1,1,2,3,5,8,13 … )。

逆波兰式

逆波兰式,即四则运算表达式的后缀表示法,如中缀表达式 9 + ( 3 - 1 ) * 3 + 10 / 2 可转后后缀表达式 9 3 1 - 3 * + 10 2 / +

后缀表达式计算结果:从左至右遍历表达式的每个数字和符号,遇到数字进栈,遇到符号取出栈顶两个数字出栈,运算后将结果进栈,直到获得最终结果。

中缀表达式转后缀表达式:从左至右遍历表达式的每个数字和符号,数字直接输出称为表达式的一部分,遇到符号先判断与栈顶符号的优先级,是右括号或优先级不高于栈顶符号,则栈顶元素依次出栈并输出,并将当前符号入栈,最后将栈中符号全部出栈并输出。

通过将中缀表达式转为后缀表达式,可以让计算机具有处理中缀表达式的能力。

队列的定义

队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

允许插入的一端称为队尾,允许删除的一端称为队头。队列又称为先进先出(First In First Out )的线性表。

队列的抽象数据类型

ADT : 队列(Queue)

Data :同线性表。元素具有相同的类型,相邻元素具有前驱和后继的关系。

Operation

  • init(初始化,建立一个空队列)
  • clear(将队列清空)
  • isEmpty(判断队列是否为空)
  • getHead(获取队头元素)
  • enQueue(入队列操作)
  • deQueue(出队列操作)
  • length(获取队列的元素个数)

endADT

队列的存储结构

队列是一种特殊的线性表,存储结构分为 顺序存储结构链式存储结构 两种。

队列的顺序存储结构

顺序存储的队列需要建立一个数组,将元素存储在数组的前 n 的单元中,数组下标为 0 的一端为队头。

入队列操作直接在队尾追加一个元素,不需要移动任何元素,时间复杂度为 O(1) 。而出队列操作需要将所有元素向前移动,时间复杂度为 O(n) 。

如出队列操作不移动元素,而是改变队头的位置,性能会大大增加。而如果数组头部有空闲空间,数组尾部没有空闲空间,再继续添加元素就会出现假溢出。

使队列头尾相接相接,数组尾部满了时将元素添加到数组的头部,这种循环队列可以解决假溢出的问题。

队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,不过只能尾进头出。

两种存储结构的对比

循环队列和链队列的基本操作复杂度都为 O(1) ,不过循环队列是预先申请好空间,而链队列每次操作都要申请和释放空间。循环队列必须有一个固定的长度,存在元素个数的限制,还可能出现空间浪费,而链队列没有这些问题。

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2016-2020 姜越

谢谢老板

支付宝
微信