加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

栈和队列

(2013-05-15 19:21:02)
标签:

队列

比较

it

分类: 数据结构

栈是限定仅在表尾进行插入和删除操作的线性表,允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈。具有先进后出的特性。

栈的抽象数据类型定义

ADT Stack

Data

 栈中元素具有相同的类型及后进先出的性质,相邻元素具有前驱和后继关系

Operation

 InitStack

    前置条件:栈不存在

    输入:无

    功能:栈的初始化

    输出:无

    后置条件:构造一个空栈

DestroyStack

    前置条件:栈已存在

    输入:无

    功能:销毁栈

    输出:无

    后置条件:释放栈所占用的存储空间

Push

    前置条件:栈已存在

    输入:元素值为x

    功能:入栈操作,在栈顶插入一个元素x

    输出:如果插入不成功,抛出异常

    后置条件:如果插入成功,则栈顶增加了一个元素

Pop

    前置条件:栈已存在

    输入:无

    功能:出栈操作,删除栈底元素

    输出:如果删除成功,返回被删除元素值,否则,抛出异常

    后置条件:如果删除成功,则栈顶减少了一个元素

GetTop

    前置条件:栈已存在

    输入:无

    功能:取栈顶元素,读取当前的栈顶元素

    输出:如栈不空,返回当前的栈顶元素值

    后置条件:栈不变

Empty

    前置条件:栈已存在

    输入:无

    功能:判空操作,判断栈是否为空

    输出:如果栈为空,返回1,否则返回0

    后置条件:栈不变

endADT

栈的顺序存储结构称为顺序栈

两栈的共享空间

在一个程序中如果需要同时使用具有相同数据类型的两个栈时,最直接的方法会是为了每个栈开辟一个数组空间,不过这样做的结果可能出现一个栈的空间已被占满而无法再进行插入操作,同时另一个栈的空间仍有大量的剩余而没有得到利用的情况,从而造成存储空间的浪费。一种可取的方法是充分利用顺序栈单向延伸的特性,使用一个数组来存储两个栈,让一个栈的栈底为该数组的始端,另一个栈的栈底为该数组的末端,每个栈从各自的端点向中间延伸。

top1和top2分别为栈1和栈2的栈顶指针,StackSize为整个数组空间的大小,栈1的底固定在下标为0的一端,栈2的底固定在下标为StackSize-1的一端。

两栈共用一个数组空间的抽象数据类型可以定义为:

ADT BothStack

Data

  共享的数据长度StackSize

  存放栈元素的数组data[StackSize]

  栈1的栈顶指针 top1

  栈2的栈顶指针 top2

Operation

BothStack

   前置条件:共享数组空间不存在

   输入:无

   功能:创建亮栈共享的数组空间

   输出:无

   后置条件两栈均为空,top1等于-1,top2等于-2

~BothStack

   前置条件:共享空间已存在

   输入:无

   功能:销毁两栈共享的数据空间

   输出:无

   后置条件:将两栈共享的数据空间释放

GetTop

   前置条件:共享空间已存在

   输入:栈号i

   功能:读取栈i当前的栈顶元素

   输出:若栈i不空,返回

   后置条件:两栈均不变

Push

   前置条件:共享空间已存在

   输入:栈号i,元素值x

   功能:入栈操作,在栈i插入一个元素x

   输出:若插入不成功,则抛出插入异常

   后置条件:若插入成功,则栈i插入了一个栈顶元素

Pop

   前置条件:共享空间已存在

   输入:栈号i

   功能:出栈操作,在栈i中删除栈顶元素

   输出:若删除不成功,则抛出删除异常

   后置条件:若删除成功,则栈i中删除了栈顶元素

Empty

   前置条件:共享空间已存在

   输入:栈号i

   功能:判空操作,判断i是否为空栈

   输出:若栈i为空栈,返回1,否则返回0

   后置条件:两栈均不变

栈的链接存储结构称为链栈

通常链栈用单链表示,因此其结点结构与单链表的结点结构相同。

顺序栈和链栈的比较:

实现顺序栈和链栈的所有基本操作的算法都只需要常数时间,因此唯一可以比较是空间性能。初始时顺序栈必须确定一个固定的长度,所以又存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题,只要当内存没有可用空间时才会出现栈满,但是每个元素都需要一个指针域,从而产生了结构性开销。所以当栈的使用过程中元素个数变化较大时,用链栈是适宜的,反之,应该采用顺序栈。

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

允许插入的一端称为队尾,允许删除的一端称为队头,具有先进先出的特性。

队列的抽象数据类型定义

ADT Queue

Data

 队列中的元素具有相同类型及先进先出的特性,相邻元素具有前驱和后继关系

Operation

InitQueue

  前置条件:队列不存在

  输入:无

  功能:初始化队列

  输出:无

  后置条件:创建一个空队列

DestroyQueue

  前置条件:队列已存在  输入:无

  功能:销毁队列

  输出:无

  后置条件:释放队列所占用的存储空间

EnQueue

  前置条件:队列已存在

  输入:元素值x

  功能:入队操作,在队尾插入一个元素

  输出:如果插入不成功,抛出异常

  后置条件:如果插入成功,队尾增加了一个元素

DeQueue

  前置条件:队列已存在

  输入:无

  功能:出对操作,删除队头元素

  输出:如果删除成功,返回被删除元素值,否则,抛出删除异常

  后置条件:如果删除成功,队头减少了一个元素

GetQueue

  前置条件:队里已存在

  输入:无

  功能:读取队头元素

  输出:对队列不空,返回队头元素

  后置条件:队列不变

Empty

  前置条件:队列已存在

  输入:无

  功能:判空操作,判断列队是否为空

  输出:如果列队为空,返回1,后置返回0

  后置条件:队列不变

随着队列的插入和删除操作的进行,整个列队向数组中下标较大的位置移动,从而产生了列队的单向移动性,当元素被插入到数组中下表最大的位置上之后,队列的空间就用尽了,尽管此时数组的地段还有空闲空间,这种现象叫做“假溢出”,解决假溢出的方法是将存储队列的数组看成是头尾相接的循环结果,即允许队列直接从数组中下标最大的位置延续到下标最小的位置。这通过取模操作很容易实现。队列这种头尾相接的顺序存储结构称为循环队列

队列的链接存储结构称为链队列

循环队列和链队列的比较:

实现循环队列和链队列的基本操作的算法都需要常数时间O(1)。循环队列和链队列的空间性能的比较和顺序栈的空间性能的比较类似,只是循环队列不能像顺序栈那样共享空间,通常不能在一个数组中存储两个循环队列。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:线性表
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇线性表
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有