PYTHON LAB MANUAL
EXPERIMENT NO.10
NAME: Adwaita Patane and Dhriti Ayyalasomayajula
REGISTRATION NUMBERS: 231061003 & 231061021
AIM: To Implement Queues Using Linked List and Arrays in Python
SOFTWARE USED: Jupyter Notebook
THEORY:
A queue is a linear data structure that follows the First In, First Out (FIFO) principle.
The first element added to the queue is the first one to be removed.
Basic Queue Operations
1. Enqueue: Adds an element to the rear (end) of the queue.
2. Dequeue: Removes an element from the front of the queue.
3. Peek/Front: Returns the value of the front element without removing it.
4. IsEmpty: Checks whether the queue is empty.
5. Size: Returns the number of elements in the queue.
Types of Queues
1. Simple Queue: Follows the FIFO principle.
2. Circular Queue: The last element connects back to the first, reducing memory
wastage.
3. Priority Queue: Elements are dequeued based on priority, not arrival order.
4. Deque (Double-Ended Queue): Allows insertion and deletion from both ends.
Implementation
Queues can be implemented using:
1. Arrays:
• Uses two pointers (front and rear) to track the start and end of the queue.
• Fixed-size arrays can lead to overflow, but circular arrays can optimize space.
2. Linked List:
• Each node represents an element of the queue.
• Front and rear pointers track the start and end nodes.
• Efficient for dynamic memory allocation.
Applications
• Resource sharing: CPU scheduling, printer task queues.
• Network packet management: Handling data packets in networking.
• Real-world scenarios: Ticket counters, call center customer management.
• Breadth-first search (BFS): Used in graph traversal algorithms.
Advantages
• Dynamic queues (using linked lists) handle memory efficiently.
• Circular queues optimize space usage compared to simple queues.
Limitations
• Sequential access: Random access is not possible.
• Overhead in linked list queues due to pointer storage.
PROGRAM:
CONCUSION:
The queue implementations effectively illustrated the First In, First Out (FIFO)
principle using both arrays and linked lists. Array-based queues were simple but faced
challenges like fixed size and resizing overhead, whereas linked list-based queues
dynamically adjusted to varying memory requirements. Essential operations like
enqueue, dequeue, and peek highlighted their role in sequential data handling.
Applications in CPU scheduling, data buffering, and real-world scenarios such as ticket
counters showcased their utility. While arrays provided straightforward
implementations, linked lists excelled in dynamic environments. This experiment
emphasized queues as essential structures for ordered processing tasks.
