风也温柔

计算机科学知识库

数据结构 队列 fifo 数据结构-栈和队列小结

  1栈

  1>栈的定义:

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

  我们把插入和删除的一端称为栈顶(TOP),另一端称为栈底(),不包含任何元素的栈称为空栈。栈又称为后进先出(Last in first out)的线性表,简称LIFO结构。

  2>栈的存储结构

  由于栈也是线性表,因此线性表的存储结构对栈也使用,通常有顺序栈和链栈两种存储结构,这两种存储结构的不同,即使得实现栈的基本运算的算法也有所不同。

  (1)顺序存储结构

  其实栈的顺序存储还是挺方便的,因为他只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷,就是必须事先确定数组存储空间大小,玩意不够用了,就需要编程手段来扩展数组的容量,非常麻烦,

  (2)链式存储结构

  如果栈的使用过程中元素变化不可预测,有时很小,有时非常大,那么最好是用链栈【存储空间不固定可伸缩】。

  2 队列

  1>队列的定义

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

  队列是一种先进先出(first in first out)的线性表,简称FIFO。允许插入的一端称为队尾(rear),允许删除的一端称为队头(Front)。

  队列是一种运算受限的线性表,它的运算限制与栈不同数据结构 队列 fifo 数据结构-栈和队列小结,是两头都有限制数据结构 队列 fifo,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进)。

  2>队列的存储结构

  队列也是线性表,所以有两种存储方式,顺序存储和链式存储。

  (1)顺序存储结构(顺序队列)

  缺点数据结构 队列 fifo,存储空间不够用的时候需要开发人员通过编程手段来扩展数组容量。

  衍生循环队列:头尾相接的顺序存储结构成为循环队列。

  (2)链式存储结构(链队)

  队列的链式存储结构,其实也就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。

  总结:

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

  队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。它们均可使用线性表的顺序存储结构来实现,但都存在着顺序存储的一些弊端(空间不够用)。因此它们各自有各级的技巧来解决这个问题,

  对于栈来说,如果是两个相同数据类型的栈,则可以用数组的两端作为栈底的方法来让两个栈共享数据,这就可以最大化地利用数组的空间。

  对于队列来说,为了避免数组插入和删除时需要移动数据,于是就引入了循环队列,使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗。

  他们也都可以通过链式存储结构来实现,实现原则上与线性表基本相同。

  文章来源:https://blog.csdn.net/XiangTianZaiJie500/article/details/52913022