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

Linked List

Deque

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