Queues

Question 1

what’s the order principle of queue

Answer 1

first in first out

Question 2

how to implement queue using linkedlist

Answer 2

• enqueue at the tail by adding to the back
• dequeue at the head by removing from the head, because removing only costs O(1) when removing form the head

Question 3

how to implement queue using arrays

Answer 3

• use a wrap-around array
• need a front and a back index tracker for optimization
• back index = last item’s index + 1
• enqueue at the back by adding to the back
• dequeue at the front by removing from the head

Question 4

linkedlist backed queue time complexity
- enqueue
- dequeue
- check empty
- get size
- clear
- resize

Answer 4

• enqueue: O(1)
• dequeue:O(1)
• check empty: O(1)
• get size: O(1)
• clear: O(1)
• resize: O(1)

Question 5

array backed queue time complexity
- enqueue
- dequeue
- check empty
- get size
- clear
- resize

Answer 5

• enqueue: O(1)*, because of resizing
• dequeue:O(1)
• check empty: O(1)
• get size: O(1)
• clear: O(1)
• resize: O(n)

Question 6

double ended queue (deque) vs. queue

Answer 6

• deque makes adding and removing from both ends efficient
• deque can be implemented using arrays and linkedlists