medium
2 min read
Deque
A deque, or double-ended queue, is a data structure that acts as both a stack and a queue. It allows you to add and remove elements from both the front and back...
Quick Actions
Insights
Difficultymedium
Reading Time2 min
A deque, or double-ended queue, is a data structure that acts as both a stack and a queue. It allows you to add and remove elements from both the front and back...
A deque, or double-ended queue, is a data structure that acts as both a stack and a queue. It allows you to add and remove elements from both the front and back of the data structure in a single operation. This is achieved by using two pointers, one pointing to the front element and the other pointing to the back element.
Deque is implemented using two arrays or two linked lists. The array implementation has the advantage of being faster on average, while the linked list implementation has the advantage of being more memory-efficient.
Example:
python
class Deque:
def init(self):
self.front = 0
self.rear = len(self.arr) - 1
def enqueue(self, data):
self.arr[self.rear] = data
self.rear += 1
def dequeue(self):
data = self.arr[self.front]
self.front += 1
return data
class Deque:
def init(self):
self.head = None
self.tail = None
def enqueue(self, data):
node = Node(data, self.head)
self.head = node
self.tail = node
def dequeue(self):
data = self.head.data
self.head = self.head.next
return data
class Node:
def init(self, data, next):
self.data = data
self.next = next
In this example, the deque is implemented using two arrays. The Enqueue method adds an element to the rear of the deque. The Dequeue method removes and returns the front element. The Node class is used to implement the doubly linked list implementation.
Hope this helps!