为了尽量简化堆栈和队列的描述,它们都是动态的信息元素链,可以从链的一端访问,它们之间唯一真正的区别是:
使用堆栈时
- 您在链的一端插入元素,然后
- 您从链的同一端检索和/或删除元素
排队时
- 您在链的一端插入元素,然后
- 您从另一端检索/删除它们
注意:我在这种情况下使用检索/删除的抽象措辞,因为有些情况下您只是从链中检索元素,或者在某种意义上只是读取它或访问它的值,但也有当您从链中删除元素的情况链,最后还有一些实例,当您使用同一个调用执行两个操作时。
此外,为了尽可能地抽象虚构的链并将其与特定的编程语言术语解耦,特意使用了元素一词。这个称为元素的抽象信息实体可以是任何东西,从指针、值、字符串或字符、对象……取决于语言。
在大多数情况下,尽管它实际上是一个值或一个内存位置(即指针)。其余的只是将这个事实隐藏在语言行话后面<
当元素的顺序很重要并且需要与元素首次进入程序时的顺序完全相同时,队列会很有帮助。例如,当您处理音频流或缓冲网络数据时。或者当您执行任何类型的存储和转发处理时。在所有这些情况下,您需要以与进入程序的顺序相同的顺序输出元素的顺序,否则信息可能会失去意义。因此,您可以将程序分解为从某个输入中读取数据、进行一些处理并将它们写入队列的部分,以及从队列中检索数据的部分处理它们并将它们存储在另一个队列中以供进一步处理或传输数据.
当您需要临时存储将在程序的直接步骤中使用的元素时,堆栈会很有帮助。例如,编程语言通常使用堆栈结构将变量传递给函数。他们实际上所做的是将函数参数存储(或推送)在堆栈中,然后跳转到他们从堆栈中删除和检索(或弹出)相同数量的元素的函数。这样,堆栈的大小取决于函数嵌套调用的数量。此外,在一个函数被调用并完成它正在做的事情之后,它使堆栈处于与调用之前完全相同的状态!这样,任何函数都可以使用堆栈操作,而忽略其他函数如何使用它。
最后,您应该知道还有其他术语用于相同的类似概念。例如,堆栈可以称为堆。这些概念也有混合版本,例如双端队列可以同时作为堆栈和队列运行,因为它可以同时被两端访问。此外,数据结构作为堆栈或队列提供给您这一事实并不一定意味着它是这样实现的,在某些情况下,数据结构可以作为任何东西实现并作为特定的数据结构仅仅是因为它可以表现得像这样。换句话说,如果您为任何数据结构提供 push 和 pop 方法,它们就会神奇地变成堆栈!