1栈的LIFO契约与应用
闭卷重建栈的LIFO契约与应用的ADT、表示不变量、操作与复杂度。
数据结构与抽象数据类型 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2表达式、调用栈与递归消除
闭卷重建表达式、调用栈与递归消除的ADT、表示不变量、操作与复杂度。
3队列FIFO与层次处理
闭卷重建队列FIFO与层次处理的ADT、表示不变量、操作与复杂度。
4环形数组队列
闭卷重建环形数组队列的ADT、表示不变量、操作与复杂度。
5Deque与工作窃取边界
闭卷重建Deque与工作窃取边界的ADT、表示不变量、操作与复杂度。
6单调栈与单调队列
闭卷重建单调栈与单调队列的ADT、表示不变量、操作与复杂度。
7实验：环形队列与单调窗口
闭卷重建实验：环形队列与单调窗口的ADT、表示不变量、操作与复杂度。
第 1 页 · 背面（答案）
机制：运算符栈按优先级/结合性延迟操作，显式栈可保存递归帧状态；实验：把中缀表达式转后缀并用值栈求值；边界：一元运算、右结合幂和括号边界会破坏只比较优先级的简单实现。
机制：push只在顶端加入，pop只移除最近加入元素；括号匹配和表达式求值依赖嵌套后进先出；实验：逐字符运行括号匹配并记录每步栈内容；边界：只统计左右括号数量不能检测顺序，空栈pop也必须有稳定契约。
机制：head、size或head/tail组合把数组首尾逻辑相接，入队出队用模运算推进；实验：在容量4中执行绕回、满、出队再入队序列；边界：只用head==tail无法同时区分空和满，必须牺牲一格、保存size或额外标志。
机制：enqueue从尾加入、dequeue从头移除，保证到达顺序；BFS按层扩展依赖这一语义；实验：模拟任务到达与服务并输出等待顺序；边界：用数组头删实现虽语义正确却每次移动后缀，复杂度会退化。
机制：删除不可能再成为答案的尾部元素，维护候选值单调与索引有效区间；实验：逐项求下一个更大元素和滑动窗口最大值；边界：只存值会无法淘汰过期重复元素，比较严格/非严格会改变相等值处理。
机制：双端队列允许两端O(1)操作，可实现滑动窗口和任务调度；并发版本还需原子同步；实验：用deque维护固定窗口元素并输出每步队首队尾；边界：双端接口不保证中间随机访问高效，并发work-stealing远复杂于顺序deque。
机制：实现定长环形队列、满空判定及基于索引deque的窗口最大值；实验：覆盖绕回、满队列、重复最大值和窗口大小1测试；边界：不得用list头删；每个索引最多入队出队一次的线性证明要能解释。