Scribd
Upload
4 views16 pages

Queue

A queue is a linear data structure that operates on a First In First Out (FIFO) basis, with main operations including enqueue, dequeue, and checking if it is empty. It can be implemented using arrays or linked lists, with circular queues addressing memory wastage issues in array implementations. Key applications of queues include CPU scheduling, printer spooling, and server request handling.

Uploaded by

misbah jamil
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
4 views16 pages

Queue

A queue is a linear data structure that operates on a First In First Out (FIFO) basis, with main operations including enqueue, dequeue, and checking if it is empty. It can be implemented using arrays or linked lists, with circular queues addressing memory wastage issues in array implementations. Key applications of queues include CPU scheduling, printer spooling, and server request handling.

Uploaded by

misbah jamil
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

Queues: Step-by-

Step Explanation
A COMPLETE LECTURE ON QUEUE ADT
ARRAY AND LINKED LIST IMPLEMENTATIONS
WITH EXAMPLES AND APPLICATIONS
1. What is a Queue?

Queue is a linear data structure that follows FIFO:


First In First Out

Example:
 - Ticket line
 - Printer queue
 - CPU scheduling
2. Queue Operations

Main operations:
- Enqueue(x): Insert at rear
- Dequeue(): Remove from front
- Front(): Return first element
- isEmpty(): Check if queue is empty
3. Queue Visualization

Enqueue 10, 20, 30:


 Front -> [10][20][30] <- Rear

Dequeue removes 10:


 Front -> [20][30] <- Rear
4. Array Implementation

Queue stored in array with two indexes:


 - front
 - rear

Insertion at rear, deletion at front


5. Array Queue Example

Array after insertions:


 [10][20][30][ ][ ]
 front rear

After dequeue:
 [10][20][30][ ][ ]
 front rear
6. Array Queue Code

class Queue {
int front, rear;
int arr[size];
enqueue(x)
dequeue()
};
7. Problem in Simple Array
Queue

 After several dequeues, free space at beginning


cannot be reused.
 This causes memory wastage.
 Solution: Circular Queue
8. Circular Queue

 rear = (rear + 1) % size


 Allows reuse of empty positions in array.
 Efficient memory utilization.
9. Linked List Queue

Dynamic implementation using nodes.


Each node has:
 - data
 - next

Pointers maintained:
 - front
 - rear
10. Linked Queue Example

Front -> [100]->[200]->[300] <- Rear


Dequeue removes front node.
No fixed size limitation.
11. Linked Queue Code

struct Node {
int data;
Node* next;
};

Queue uses front and rear pointers.


12. Complexity Analysis

 Enqueue: O(1)
 Dequeue: O(1)
 Display: O(n)

Same for array and linked implementations


13. Array vs Linked Queue

Array:
- Fixed size
- Simple

Linked List:
- Dynamic size
- Extra pointer memory
14. Applications of Queue

- CPU Scheduling
- Printer Spooling
- BFS Traversal
- Server Request Handling
15. Summary

 Queue is FIFO.
 Array Queue is simple but fixed.
 Linked Queue is flexible and dynamic.
 Circular Queue solves array wastage.

You might also like