Scribd
Upload
5 views4 pages

Queue Using Linked List

A queue is a linear data structure that operates on a FIFO basis, implemented using a linked list for dynamic size and efficient operations. Key operations include ENQUEUE for inserting at the rear, DEQUEUE for removing from the front, and PEEK for viewing the front element. While it offers advantages like no overflow and fast operations, it requires extra memory for links and is not as cache-friendly as arrays.

Uploaded by

rehna
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views4 pages

Queue Using Linked List

A queue is a linear data structure that operates on a FIFO basis, implemented using a linked list for dynamic size and efficient operations. Key operations include ENQUEUE for inserting at the rear, DEQUEUE for removing from the front, and PEEK for viewing the front element. While it offers advantages like no overflow and fast operations, it requires extra memory for links and is not as cache-friendly as arrays.

Uploaded by

rehna
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Queue Using Linked List

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.
The element inserted first is removed first.
In a linked-list implementation, insertion (ENQUEUE) happens at the rear, and
deletion (DEQUEUE) happens at the front.
Why Linked List?
• Dynamic size — grows and shrinks at runtime
• No overflow until memory is full
• No shifting of elements
• Efficient insertion at rear and deletion at front (O(1))
Node Structure
Each element is stored inside a Node that contains:
• data (value)
• next (reference to the next node)

Two reference variables are maintained:


• front → points to the first node
• rear → points to the last node
When the queue is empty → front = rear = null.
Queue Operations
1. ENQUEUE – Insert an element at the rear
2. DEQUEUE – Remove an element from the front
3. PEEK / FRONT – View the first element without removing it
4. isEmpty – Check whether the queue has no elements
Algorithm for ENQUEUE(x)
Purpose: Insert an element at the rear
ENQUEUE(x):
1. Create a new Node
2. [Link] = x
3. [Link] = null
4. If front == null
front = rear = newNode
Else
[Link] = newNode
rear = newNode
Algorithm for DEQUEUE()
It removes and returns the front element
DEQUEUE():
1. If front == null
print "Queue Underflow" and stop
2. item = [Link]
3. front = [Link]
4. If front == null
rear = null
5. return item
Algorithm for PEEK() / FRONT()
Returns the front element without deleting it
PEEK():
1. If front == null
print "Queue is Empty"
2. else
return [Link]
Algorithm for isEmpty()
Checks whether the queue is empty
isEmpty():
1. If front == null
return TRUE
2. else
return FALSE
isFull()
Not required — queue grows dynamically.
Overflow only if system memory ends.
Advantages
• Dynamic size
• No overflow
• Fast enqueue at rear and dequeue at front
• Good for scheduling and buffering
Disadvantages
• Extra memory for links
• Slightly slower than array due to dynamic allocation
• Not cache-friendly
Applications
• CPU scheduling
• Printer queue
• Task scheduling
• Call center systems
• Ticket reservation
• BFS graph traversal
• Buffer management

You might also like