Queue

Question 1

What is a Queue?

Answer 1

A Queue is a linear structure which follows a First In First Out (FIFO) structure
e.g. Queue of people in a billing counter

A queue is used when things don’t have to be processed immediately, but have to be processed in First InFirst Out order like Breadth-First Search.

Question 2

Common operation on a Queue

Answer 2

• Create a Queue
• enqueue (maintain a topOfQueue variable to insert at the end)
• dequeue (maintain beginingOfQueue and endOfQueue, when b > e then reset both to 0)
• peekInQueue: Does not remove the element from the stack only return the value
• isEmpty (if beginingOfQueue is -1)
• isFull (if topOfQueue === arr.length -1)
• Delete Queue (set arr = null)

Question 3

When to use/avoid a Queue

Answer 3

Whenever need to use FIFO
Cannot easily be corrupted

Random access is not possible. if a mistake happens all elements need to be dequeued

Question 4

How is Queue implemented?

Answer 4

A queue can be implemented using an array or linked list

Array:
We need to keep track of two indices, front, and rear. We enqueue an item at the rear and dequeue an item from the front.

Complexity Analysis:

Time Complexity:
Operations              Complexity
Enque(insertion)           O(1)
Deque(deletion)            O(1)
Front(Get front)           O(1)
Rear(Get Rear)             O(1)              
Auxiliary Space: O(N).
N is the size of the array for storing elements.