Queue, Stack & Linked List Note

Queue

• Usages: Breadth-First Search related problems.

典型问题

• Tree printout by level (https://leetcode.com/problems/binary-tree-level-order-traversal/description/)
• 103. Binary Tree Zigzag Level Order Traversal (https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/)
• 232. Implement Queue using Stacks (https://leetcode.com/problems/implement-queue-using-stacks/description/)

• Stack1: is the only stack to store new elements when adding a new element into the queue.
• Stack2: is the only stack to pop old element out of the queue. (When stack2 is empty, we move all data from stack1 to stack2 (if any)) time complexity: Push(): O(1) Pop(): O(n) -> Amortized time complexity O(1)

Stack

• 什么问题要往Stack上考虑？ Answer：从左到右linear scan一个array／string时，如果要不断回头看左边最新的元素时，往往要用到stack。
  1. Histogram中找最大的长方形
  2. reverse polish notation 逆波兰表达式的计算 a*(b + c) -> abc+*
  3. String的repeatedly deduplication. cabba -> caa -> c

Linked List

Deque

• 239. Sliding Window Maximum (https://leetcode.com/problems/sliding-window-maximum/description/)