Queue (Section B1)
- UniDrill
- Feb 21
- 5 min read
QUEUE AND DEQUE DATA STRUCTURES: COMPLETE CUET STUDY NOTES
1. Introduction to Queue
A Queue is a fundamental linear data structure in computer science where elements are organized in a specific sequence. Unlike a stack, which follows the Last-In-First-Out (LIFO) principle, a queue operates on the First-In-First-Out (FIFO) principle.
In a queue, there are two distinct ends for processing data:
REAR (or Tail): The end where new elements are added.
FRONT (or Head): The end from which existing elements are removed.
The FIFO principle implies that the element that entered the queue first will be the first one to be removed. This is also commonly referred to as the First Come First Served (FCFS) approach.
1.1 Real-Life Analogies
To better understand the queue, the sources provide several everyday examples:
Morning Assembly: Students standing in a line for prayers; the student at the front of the line enters the hall first.
Bank Cash Counter: Customers form a queue at the teller; the person who arrived first is serviced first.
Fuel Pumps: Vehicles line up at a petrol station; the vehicle at the head of the line finishes first and exits.
One-Way Roads: In a single-lane one-way road, the vehicle that entered first must exit first.
2. Applications of Queue
The concept of a queue is vital in both real-world logistics and computer system management.
2.1 Real-Life Applications
Railway Reservation: When a ticket is on a "Waiting List" (e.g., W/L1), it is part of a queue. If a confirmed passenger cancels, the person at the FRONT of the waiting queue (W/L1) is removed and granted a confirmed seat.
Customer Support: When calling a service center, the Interactive Voice Response System (IVRS) places the call in a queue until a support person becomes available.
2.2 Computer Science Applications
Web Servers: Servers hosting high-traffic websites (like result portals) use queues to manage incoming requests. If a server can only handle 50 concurrent users but receives thousands of hits, it queues the requests and processes them one by one.
Operating Systems (OS): Multi-tasking operating systems must handle multiple "jobs" requesting processor time. Since a processor handles one task at a time, the OS lines them up in a queue and grants access on a FIFO basis.
Print Spooling: When multiple files are sent to a shared printer from different computers, the OS places these print commands in a queue and sends them to the printer one by one.
3. Operations on Queue
A standard queue supports two primary operations and several supporting ones to manage data flow efficiently.
3.1 Primary Operations
ENQUEUE (INSERT): This operation is used to insert a new element at the REAR end of the queue.
Exception (Overflow): If a queue has a fixed capacity and a user tries to add an element beyond that capacity, it results in an Overflow exception.
DEQUEUE (DELETE): This operation is used to remove an element from the FRONT of the queue.
Exception (Underflow): If a user attempts to remove an element from an empty queue, the system triggers an Underflow exception.
3.2 Supporting Operations
IS EMPTY: Used to check if the queue contains any elements. This check is essential before performing a DEQUEUE to avoid Underflow.
PEEK: This allows the user to view the element currently at the FRONT of the queue without actually removing it.
SIZE: Used to determine the total number of elements currently present in the queue.
IS FULL: Used in fixed-size queues to check if more elements can be added, preventing Overflow.
4. Implementation of Queue in Python
In Python, the list data type is a highly effective tool for implementing a queue structure. While using a list, we must designate one end as the FRONT and the opposite end as the REAR.
4.1 Mapping Queue Logic to Python Lists
Standard practice in Python uses the following mapping:
REAR (End of List): We use the append() method, which always adds an element to the end of the list.
FRONT (Beginning of List): We use the pop(0) method, which removes the element at index 0.
Note: Since Python lists are dynamic, we do not typically need to implement "Is Full" or handle "Overflow," as the list grows as long as memory is available.
4.2 Implementation Code Functions
Below are the modular functions for a queue as described in the sources:
# Function to create an empty queue
def createQueue():
return list()
# Function to check if the queue is empty
def isEmpty(myQueue):
if len(myQueue) == 0:
return True
else:
return False
# Function to ENQUEUE (Insert at Rear)
def enqueue(myQueue, element):
myQueue.append(element) # Adds to the end of the list [11]
# Function to DEQUEUE (Remove from Front)
def dequeue(myQueue):
if not isEmpty(myQueue):
return myQueue.pop(0) # Removes element at index 0 [12]
else:
print("Underflow: Queue is empty")
return None
# Function to PEEK (Read Front element)
def peek(myQueue):
if isEmpty(myQueue):
print('Queue is empty')
return None
else:
return myQueue # Returns element at index 0 [8]
# Function to get current SIZE
def size(myQueue):
return len(myQueue) [8]
5. Introduction to Deque (Double-Ended Queue)
A Deque (pronounced "deck") is a more flexible version of a queue. It is an ordered linear list where elements can be added or removed from either end (Front or Rear).
Because it lacks the strict entry/exit restrictions of a standard queue, a Deque can be used to implement both a stack and a queue.
5.1 Operations on Deque
A Deque supports four main data manipulation operations:
INSERTFRONT: Adds a new element at the head/front of the deque.
INSERTREAR: Adds a new element at the tail/rear (same as standard Enqueue).
DELETIONFRONT: Removes an element from the head/front (same as standard Dequeue).
DELETIONREAR: Removes an element from the tail/rear.
5.2 Applications of Deque
Palindrome Checking: To check if a string is a palindrome (reads the same forward and backward), the string is processed into a Deque. Characters are then removed from both ends simultaneously and matched; if they match until the Deque is empty or has one character left, the string is a palindrome.
Browser History: While a stack is typically used for history, a Deque is useful when the history list becomes too large. The most recent URLs are added to one end, and the oldest, least-visited URLs are removed from the other end to maintain a fixed size.
Undo/Redo: Similar to history, text editors use this structure to manage the list of recent changes.
6. Implementation of Deque in Python
Like a standard queue, a Deque is implemented in Python using the list data type.
6.1 Python List Methods for Deque
Insert at Front: Use insert(0, element).
Insert at Rear: Use append(element).
Delete from Front: Use pop(0).
Delete from Rear: Use pop() (without arguments, it removes the last item).
6.2 Implementation Code Functions
# Function to Insert at Front
def insertFront(myDeque, element):
myDeque.insert(0, element) # [18]
# Function to Insert at Rear
def insertRear(myDeque, element):
myDeque.append(element) # [18, 20]
# Function to Delete from Front
def deletionFront(myDeque):
if not isEmpty(myDeque):
return myDeque.pop(0) # [19, 21]
else:
print("Queue Underflow")
return None
# Function to Delete from Rear
def deletionRear(myDeque):
if not isEmpty(myDeque):
return myDeque.pop() # [19, 21]
else:
print("Deque Empty")
return None
# Function to Read Front (getFront)
def getFront(myDeque):
if not isEmpty(myDeque):
return myDeque # [19, 20]
else:
return None
# Function to Read Rear (getRear)
def getRear(myDeque):
if not isEmpty(myDeque):
return myDeque[len(myDeque)-1] # [20, 22]
else:
return None
7. Summary and Key Differences
Feature | Queue | Deque |
Logic | FIFO (First-In-First-Out) | Bi-directional (no strict rule) |
Insertion | REAR only (Enqueue) | Either Front or Rear |
Deletion | FRONT only (Dequeue) | Either Front or Rear |
Ends | Two distinct ends (different) | Two ends (same or different) |
Implementation | append() and pop(0) | insert(0), append, pop(0), pop |
Versatility | Limited to queueing logic | Can act as Stack OR Queue |
Comments