线性表、栈与队列

词汇

两种布局，不同的端

Python 列表是连续的数组 array：索引 $i$ 一步算出地址，但头部插入要全员挪动。链表 linked list 用便宜拼接换掉跳转：每个节点 node 带一个指向下一个的指针。
栈 stack 在同一端进出（后进先出）；队列 queue 一端进另一端出（先进先出）。

{exercise:uni-cs0502-layouts}

练习

连续数组里取下标 i 的代价是——

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励

{exercise:uni-cs0502-append}

练习

在 Python 列表末尾追加是——

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励

栈：push 3, push 7, push 1 后 pop, pop 返回 $1$ 再 $7$——后进先出。括号配对同法：扫 ([]){} 压入开括号，闭括号必须匹配栈顶；([)] 失败，因为 ) 看到的是 [。
队列：入队 a, b, c；两次出队返回 a 再 b；队首是 c。collections.deque 两端都 $O(1)$——循环里 list.pop(0) 是经典 $O(n)$ 陷阱。