7.1 Definition of a Queue and its Properties
Queue is an abstract data structure that represents an ordered collection of elements organized by the "first in, first out" principle (FIFO). You can think of a queue like a line of people at a store: the first person in line gets served first.
Properties of a Queue:
- FIFO (First In, First Out): The first added element will be the first one removed.
- Limited Operations: A queue supports a limited set of operations: adding (enqueue), removing (dequeue), and peeking at the element in the front position.
- One-way Access: Access to elements is only possible from the front and rear ends.
- Simplicity in Implementation: A queue can easily be implemented using an array or a linked list.
FIFO operation principle:
- Adding an Element (enqueue): A new element is added to the end of the queue.
- Removing an Element (dequeue): The first added element is removed from the front of the queue.
- Peeking at the Front Element: Allows you to see the front element of the queue without removing it.
Elements in a queue are added from one end (rear) and removed from the other end (front). So, the first added element is the first to be removed.
7.2 Basic Operations
Basic operations: enqueue, dequeue, peek
Operation enqueue: Adds a new element to the end of the queue.
Time complexity: O(1).
from collections import deque
queue = deque()
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
print(queue) # Output: deque([10, 20])
Operation dequeue: Removes and returns an element from the front of the queue.
Time complexity: O(1).
from collections import deque
queue = deque()
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
print(queue) # Output: deque([10, 20])
front_element = queue.popleft() # dequeue
print(front_element) # Output: 10
print(queue) # Output: deque([20])
Operation peek: Returns the element at the front of the queue without removing it.
Time complexity: O(1).
from collections import deque
queue = deque()
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
print(queue) # Output: deque([10, 20])
front_element = queue[0] # peek
print(front_element) # Output: 10
7.3 Examples of Using Queues
Let's look at some examples of queue usage.
1 Printer Job Management
Queues are used for managing printer jobs, where documents are added to the queue and printed in the order they arrive.
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_job(self, job):
self.queue.append(job)
def print_job(self):
if self.queue:
job = self.queue.popleft()
print(f"Printing: {job}")
# Usage example:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job() # Output: Printing: Document1.pdf
printer_queue.print_job() # Output: Printing: Document2.pdf
2 Web Server Request Handling
Queues are used to manage client requests arriving at a web server. Requests are processed in the order they arrive.
class RequestQueue:
def __init__(self):
self.queue = deque()
def add_request(self, request):
self.queue.append(request)
def process_request(self):
if self.queue:
request = self.queue.popleft()
print(f"Processing request: {request}")
# Usage example:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request() # Output: Processing request: GET /index.html
request_queue.process_request() # Output: Processing request: POST /submit-form
3 Message Queue in Messaging Systems
Queues are used to manage messages in messaging systems (e.g., message brokers). Messages are processed in the order they arrive.
class MessageQueue:
def __init__(self):
self.queue = deque()
def send_message(self, message):
self.queue.append(message)
def receive_message(self):
if self.queue:
message = self.queue.popleft()
print(f"Received message: {message}")
# Usage example:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message() # Output: Received message: Hello
message_queue.receive_message() # Output: Received message: World
GO TO FULL VERSION