Stack and Queue

16th March 2021 at 9:51pm

栈(先进后出,FILO,first in first out)和队列(先进先出,FIFO,first in first out)。

栈和队列可以用同样的底层数据结构来实现,比如用双向链表(doubly linked list)。因此在一些算法实现中,栈可以随时变成队列,反之亦然。

通过栈使元素反向排列

比如把 1, 2, 3, 4, 5 分别压入栈。如果想知道这串输入的反向是怎样的,可以依次 pop 元素出来,就变成 5, 4, 3, 2, 1。

在实现 二叉树的后序遍历 中有使用。