Queue is a linear data structure in which data can be added to one end and retrieved from the other. Just like the queue of the real world, the data that goes first into the queue is the first one to be retrieved. That is why queues are sometimes called as First-In-First-Out data structure.
In case of queues, we saw that data is inserted both from one end but in case of Queues; data is added to one end (known as REAR) and retrieved from the other end (known as FRONT).
The data first added is the first one to be retrieved while in case of queues the data last added is the first one to be retrieved.
ALGORITHMS:
Insert ( ):
Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of
the QUEUE. ITEM is the value to be inserted.
1. If (REAR == N) Then [Check for overflow]
2. Print: Overflow
3. Else
4. If (FRONT and REAR == 0) Then [Check if QUEUE is empty]
(a) Set FRONT = 1
(b) Set REAR = 1
5. Else
6. Set REAR = REAR + 1 [Increment REAR by 1]
[End of Step 4 If]
7. QUEUE[REAR] = ITEM
8. Print: ITEM inserted
[End of Step 1 If]
9. Exit
Delete ( ):
Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of
the QUEUE.
1. If (FRONT == 0) Then [Check for underflow]
2. Print: Underflow
3. Else
4. ITEM = QUEUE[FRONT]
5. If (FRONT == REAR) Then [Check if only one element is left]
(a) Set FRONT = 0
(b) Set REAR = 0
6. Else
7. Set FRONT = FRONT + 1 [Increment FRONT by 1]
[End of Step 5 If]
8. Print: ITEM deleted
[End of Step 1 If]
9. Exit
QUEUE USING ARRAY
QUEUE USING LINKED LIST