我已经开始学习 数据结构最近,刚有了我自己的 linked list
实现。
现在我偶然发现了两个新的数据结构:stack
和 queue
.
从我到目前为止所学到的stack
是 linked list
只允许从它的尾部插入/移除,和
queue
是 linked list
只允许插入它的尾部,只允许从它的头部移除。
我的问题是:
为什么我要使用这两种数据结构而不是常规 linked list
允许从任何地方插入和移除?
另外,为什么这两种数据结构被归类为独立的数据结构而不是“有限访问链表”?
最佳答案
栈和队列都有其存在的理由。
堆栈是可以使用数组、链表或其他形式实现的 FILO(先进后出)或 LIFO(任何一种方式)数据结构。考虑浏览器历史记录。您导航到站点 A -> 然后 B -> 然后 C -> D。当用户继续前进时,您首先推 (在尾部插入)网站列表。这可确保当前站点始终位于堆栈顶部。
然后当用户点击后退按钮时,你 流行音乐顶部的那个(从尾部移除 - 用于插入的同一端)给出最后访问的站点 - C。因此,先入(即站点 A)和后出(最后一个进入的站点是站点)的概念D 反过来成为第一个出去的人)
对于 FIFO(先进先出)的队列也可以这样说。考虑作业队列的例子。在执行一项工作时,您会(不考虑任何优化算法)为第一个到达的人服务。这使得队列成为一种优秀的数据结构,以先到先得的方式处理作业。
在这两种情况下,您都不希望在任何索引处任意删除或插入元素。不,这会导致不良行为。因此,需要堆栈/队列。我再次强调堆栈/队列可以通过对链表实现限制来实现。
很抱歉图像质量很差 - 我只是用油漆画的。
关于data-structures - 堆栈、队列和链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32151392/