Introduction to Double-Ended Queue (Deque)

A double-ended queue, often abbreviated as deque, is a linear data structure that allows insertion and deletion of elements from both ends. This flexible nature of deques makes it a powerful and versatile tool that can be employed in various applications.

Basic Operations of Double-Ended Queue

Here we explore the fundamental operations that can be performed on a deque. We will use Python’s collections.deque for our examples.

Creating a Deque

  from collections import deque
# Create an empty deque d = deque()
# Create a deque with initial elements d = deque([1, 2, 3, 4])  

Appending Elements

  # Append to the right d.append(5)
# Append to the left d.appendleft(0)  

After appending, the deque becomes: deque([0, 1, 2, 3, 4, 5])

Removing Elements

  # Remove from the right d.pop()
# Remove from the left d.popleft()  

After removing, the deque becomes: deque([1, 2, 3, 4])

Accessing Elements

  # Access an element by index first_element = d[0]
# Access the first and last elements directly first_element = d[0] last_element = d[-1]  

Currently, first_element is 1, and last_element is 4.

Extending Deque

  # Extend deque on the right d.extend([5, 6, 7])
# Extend deque on the left d.extendleft([-3, -2, -1])  

After extending, the deque becomes: deque([-1, -2, -3, 1, 2, 3, 4, 5, 6, 7])

Rotate Deque

  # Rotate to the right d.rotate(1)
# Rotate to the left d.rotate(-1)  

After rotating to the right, the deque becomes: deque([7, -1, -2, -3, 1, 2, 3, 4, 5, 6]) and to the left: deque([-1, -2, -3, 1, 2, 3, 4, 5, 6, 7])

Counting Elements

  # Count occurrences of an element count = d.count(1)  

The count of 1 in the deque is: 1.

Deque Use Case Example

Let’s create a simple application to simulate a queue at a supermarket checkout counter.

  from collections import deque
class SupermarketQueue: def __init__(self): self.queue = deque()
def join_queue(self, customer): self.queue.append(customer) print(f'Customer {customer} joined the queue.')
def serve_customer(self): if self.queue: served = self.queue.popleft() print(f'Customer {served} has been served.') else: print('No customers in the queue.')
def queue_status(self): print('Current Queue:', list(self.queue))
# Usage supermarket_queue = SupermarketQueue() supermarket_queue.join_queue('Alice') supermarket_queue.join_queue('Bob') supermarket_queue.join_queue('Carol') supermarket_queue.queue_status() supermarket_queue.serve_customer() supermarket_queue.queue_status() supermarket_queue.serve_customer() supermarket_queue.serve_customer() supermarket_queue.serve_customer()  

In this example, customers Alice, Bob, and Carol join the queue. The queue status is checked, and customers are served in the order they arrived, demonstrating a simple use of deque operations in a practical scenario.

Hash: 94fd2acbc8c94cf174e4c55d31a26d1fd4b22f669c22c5aed0af0dc96c86e276