Dequeue in data structure | restrictions | input | out put
what is Dequeue in data structure
A de-queue is kind of queue in which elements can be added or removed from the either end but not from the middle . the term de-queue is taken from double ended Q.
There are two types of de-queue
-
Input restricted de-queue —
this queue allows insertion only at one end but allow deletion at both ends .
-
Output restricted de-queue —
This queue allow insertion at both ends but deletions only at one end.
Step1 [check for under flow condition]
if front = -1 & rear = -1, then
output underflow & exit
Step2 [delete element at the front end ]
if [front] >= 0 then
then =Q[front]
Step3 [check queue for empty]
if front = rear, then
rear = -1
front = -1
else
front = front+1
Step4 [delete element at the rear end ]
if rear > = 0
item = Q[rear]
Step5 [check queue for empty ]
if front = rear, then
front = -1
rear = -1
else
rear = rear – 1
Step6 exit
Step1 [check for overflow condition]
If front = 0 & rear >= size -1
Output over flow & exit
Step2 : [check front pointer value]
If front >0, then
Front = front -1
Step3: [insert element at the front end ]
Q[front] = value
Step4 : [ check rear pointer value]
If rear < size-1
Rear = rear+1
Step5: [ insert element at the rear end]
Q[rear] = value
Step6 : exit
class OutputRestrictedDeque:
def init(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue_front(self, item):
# Enqueue an element at the front of the dequeue.
self.items.insert(0, item)
def enqueue_rear(self, item):
# Enqueue an element at the rear of the dequeue.
self.items.append(item)
def dequeue_front(self):
# Dequeue an element from the front of the dequeue.
if not self.is_empty():
return self.items.pop(0)
else:
return None # Dequeue is empty
def get_front(self):
# Get the front element without removing it.
if not self.is_empty():
return self.items[0]
else:
return None # Dequeue is empty
def get_rear(self):
# Get the rear element without removing it.
if not self.is_empty():
return self.items[-1]
else:
return None # Dequeue is empty
def size(self):
# Return the number of elements in the dequeue.
return len(self.items)
init: Initializes an empty dequeue.
is_empty: Checks if the dequeue is empty.
enqueue_front: Enqueues an element at the front of the dequeue.
enqueue_rear: Enqueues an element at the rear of the dequeue.
dequeue_front: Dequeues an element from the front of the dequeue.
get_front: Retrieves the front element without removing it.
get_rear: Retrieves the rear element without removing it.
size: Returns the number of elements in the dequeue.
What is the main advantage of using a deque over a stack or queue?
A deque can perform all the operations of both a stack and a queue, providing flexibility in managing data from both ends.
When should I use an input-restricted deque?
Input-restricted deques are useful when data needs to be enqueued in a specific order but can be dequeued from both ends.
Can a deque be implemented using a linked list?
Yes, linked lists provide a flexible implementation for deques, allowing dynamic resizing and efficient element management.
What are the real-world applications of deques?
DE queues find applications in task scheduling, browser history navigation, undo and redo functionality, printer queues, and solving sliding window problems, among others.
How do I choose between an array-based and linked list-based implementation of a deque?
The choice depends on your specific requirements. Array-based implementations offer fixed sizes, while linked lists provide flexibility for dynamic resizing. Consider your application’s needs when deciding.