dequeue in data structure

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

  1.  

    Input restricted de-queue  —

    this queue allows  insertion only at one end but allow deletion  at both ends .

  2. Output restricted de-queue  — 

     This  queue allow  insertion at both ends but deletions only  at one end.

Algorithm  for input restricted dequeue.

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

Algorithm for output restricted dequeue

 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

IN Python.

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.