Queue

FIFO

• dequeue()
• enqueue()

Implementation

Array

两个variable front 和 rear来记录位置, start from -1(empty queue)

• enqueue() add to rear
• dequeue() delete from front

will have function like isEmpty() to check if queue is empty and check front == rear

can do a cyclic array and reuse space

next position would be (i+1) % n, (rear + 1 ) % n == front mean it's full

Linked List

用一个tail记录现在List的end, head still head

• enqueue() add after tail
• dequeue() delete from head