Advanced Data Structure
▪ Stack 栈
– An ordered collection where data items are accessed based on
LIFO (Last-In-First-Out)
– push(item): add a new item onto the top of the stack
– pop(): remove an existing item from the top of the stack
– peek(): look at the top item of the stack; without modifying the stack
▪ Queue
– An ordered collection where data items are accessed based on
FIFO (First-In-First-Out)
– Enqueue, dequeue, peek
Append: append a new item at the rear (end) of the queue 存入
serve: remove an existing item from the front of the queue 取出
▪ Heap
called Priority Queue
– special kind of tree, the top element is the extreme max or min of all
elements for min-heap
– Add, serve
Tree
– Graph of nodes and edges:
root, leaf, parent, child nodes
– Tree search: BFS, DFS
▪ Binary search tree (BST)
– Definition:
▪ Nodes in left subtree < the root.
▪ Nodes in right subtree > the root.
▪ The left and right subtree each must also be a BST
– Tree imbalance
