Stack Queue PriorityQueue

发自简书
栈、队列和优先级队列是经常用于简化某种程序的数据结构。

在这些数据结构中，只有一个数据项可以被访问。

栈允许访问最后一个插入的数据项。

栈中重要的操作是在栈顶插入（压入）一个数据项，以及从栈顶移除（弹出）一个数据项。

队列只允许访问第一个插入的数据项。

队列的重要操作是在队尾插入数据项和在队头移除数据项。

队列可以实现为循环队列，它基于数组，数组的下标可以从数组末端回绕到数组开始位置。

优先级队列允许访问最小（或者有事是最大）的数据项。

优先级队列的重要操作是有序地插入新数据和移除关键字最小的数据项。

这些数据结构可以用数组实现，也可以用其他机制（例如链表）来实现。

普通算术表达式是用中缀表达法表示的这种命名的原因是操作符写在两个操作数中间。

在后缀表达法中，操作符跟在两个操作数的后面。

算术表达式求值通常都是先转换成后缀表达式，然后再求后缀表达式的值。

在中缀表达式转换后缀表达式以及求后缀表达式的值得过程里，栈都是很有用的工具。

image