堆栈,队列和链接列表

Question

我最近开始学习数据结构,并且只有我自己的linked list实现.

现在我偶然发现了两个新的数据结构:stack 和queue.
从什么到目前为止,我已经学会
stack是一个linked list只允许从它的尾巴插入/移除,并且
queue是一个linked list允许插入只在它的尾巴,只有从其头部取出.

我的问题是:
为什么我会使用这两种数据结构而不是linked list允许从任何地方插入和删除的常规数据？
另外,为什么这两种数据结构被归类为独立的数据结构而不是"有限的访问链表"？

Answer 1

堆栈和队列有自己的存在理由.堆栈是可以使用数组,链接列表或其他形式实现的FILO(先进先出)或LIFO(任一方式)数据结构.考虑浏览器历史.你导航到站点A - >然后乙 - >然后Ç - > d.当用户向前移动时,首先推送(插入尾部)网站列表.这可确保当前站点始终位于堆栈顶部.

然后,当用户点击后退按钮,你弹出了一个在顶部-这给最近访问过的网站- (从尾部除去同一端用于插入)Ç.因此,First In(这是A站点)和Last Out(最后一个进入的站点D的概念反过来成为第一个出去的)

类似的可以说是队列,即FIFO(先入先出).考虑作业队列的示例.在执行作业时,您(不考虑任何优化算法)首先服务于该作业.这使得队列成为一个出色的数据结构,以先到先得的方式处理作业.

在这两种情况下,您都不希望在任何索引处任意删除或插入元素.不,这会导致不良行为.因此,需要堆栈/队列.我再次强调,堆栈/队列可以通过对链表实施限制来实现.

抱歉图像质量差 - 我只是画了油漆.