Stack and Queue

抽象数据类型(Abstract Data Type): 带有一组操作的一些对象的集合

Stack ADT

栈本质是个表

from infix to postfix

遇见操作数，放到输出队列中，遇见操作符，push进栈，按照优先级弹出（如果当前操作符的优先级比top低，那么弹出top，直至优先级高于top）

正在处理的开符号不会随便弹出

当输入为空时，将栈清空

Activation Record & Stack Frame

tail recursion 可以被while循环消除

while循环模拟递归调用

递归总能够消除，一般是使用stack。一般非递归程序比等价递归快，但是牺牲了清晰度

Queue ADT

queue的本质也是表，可以用array实现

也可以用circular array实现

file server

queueing theory