How Queue is Implemented in Data Structure?

A queue is implemented in data structure using two primary methods: arrays and linked lists.

Array Implementation

An array is a contiguous block of memory that can store elements of the same data type. To implement a queue using an array, we use two pointers: front and rear.

• Front: Points to the first element in the queue.
• Rear: Points to the last element in the queue.

Operations:

• Enqueue: To add an element to the queue, we increment the rear pointer and store the element at the new rear position.
• Dequeue: To remove an element from the queue, we increment the front pointer and return the element at the previous front position.

Example:

Consider a queue with a maximum capacity of 5 elements. Initially, the queue is empty, so front and rear pointers are set to 0.

queue: [ , , , , ]
front = 0
rear = 0

Now, let's enqueue elements 1, 2, and 3:

enqueue(1):
queue: [1, , , , ]
front = 0
rear = 1

enqueue(2):
queue: [1, 2, , , ]
front = 0
rear = 2

enqueue(3):
queue: [1, 2, 3, , ]
front = 0
rear = 3

To dequeue an element, we increment the front pointer:

dequeue():
queue: [ , 2, 3, , ]
front = 1
rear = 3

Advantages:

• Simple to implement.
• Efficient for enqueue and dequeue operations.

Disadvantages:

• Fixed size.
• Can lead to overflow if the queue becomes full.

Linked List Implementation

A linked list is a dynamic data structure where each element is a node that contains data and a pointer to the next node. To implement a queue using a linked list, we use two pointers: front and rear.

• Front: Points to the first node in the queue.
• Rear: Points to the last node in the queue.

Operations:

• Enqueue: To add an element to the queue, we create a new node, store the element in it, and set the next pointer of the new node to NULL. If the queue is empty, we set both front and rear pointers to the new node. Otherwise, we set the next pointer of the rear node to the new node and update the rear pointer.
• Dequeue: To remove an element from the queue, we return the data stored in the front node and update the front pointer to the next node. If the queue is empty, we return NULL.

Example:

Consider a queue implemented using a linked list. Initially, the queue is empty, so front and rear pointers are set to NULL.

queue: NULL
front = NULL
rear = NULL

Now, let's enqueue elements 1, 2, and 3:

enqueue(1):
queue: 1 -> NULL
front = 1
rear = 1

enqueue(2):
queue: 1 -> 2 -> NULL
front = 1
rear = 2

enqueue(3):
queue: 1 -> 2 -> 3 -> NULL
front = 1
rear = 3

To dequeue an element, we return the data stored in the front node and update the front pointer:

dequeue():
queue: 2 -> 3 -> NULL
front = 2
rear = 3

Advantages:

• Dynamic size.
• No overflow issues.

Disadvantages:

• More complex to implement than array implementation.
• Enqueue and dequeue operations can be slightly slower than array implementation.

Conclusion

Both array and linked list implementations have their advantages and disadvantages. Choosing the right implementation depends on the specific requirements of the application.