Thursday, December 6, 2007

DeQueue Data Structure

DeQueue (or) Deque (Double ended Queue) :-
DeQueue is a data structure in which elements may be added to or deleted from the front or the rear.
Like an ordinary queue, a double-ended queue is a data structure it supports the following operations: enq_front, enq_back, deq_front, deq_back, and empty. Dequeue can be behave like a queue by using only enq_front and deq_front , and behaves like a stack by using only enq_front and deq_rear. .
The DeQueue is represented as follows.


DeQueue can be represented in two ways they are
1) Input restricted DeQueue 2) output restricted DeQueue

The out put restricted Dequeue allows deletions from only one end and input restricted Dequeue allow insertions at only one end.
The DeQueue can be constructed in two ways they are
2) Using array 2. using linked list
Algorithm to add an element into DeQueue :
Assumptions: pointer f,r and initial values are -1,-1
Q[] is an array
max represent the size of a queue
enq_front
step1. Start
step2. Check the queue is full or not as if (f <>
step3. If false update the pointer f as f= f-1
step4. Insert the element at pointer f as Q[f] = element
step5. Stop
enq_back
step1. Start
step2. Check the queue is full or not as if (r == max-1) if yes queue is full
step3. If false update the pointer r as r= r+1
step4. Insert the element at pointer r as Q[r] = element
step5. Stop
Algorithm to delete an element from the DeQueue
deq_front
step1. Start
step2. Check the queue is empty or not as if (f == r) if yes queue is empty
step3. If false update pointer f as f = f+1 and delete element at position f as element = Q[f]
step4. If ( f== r) reset pointer f and r as f=r=-1
step5. Stop
deq_back
step1. Start
step2. Check the queue is empty or not as if (f == r) if yes queue is empty
step3. If false delete element at position r as element = Q[r]
step4. Update pointer r as r = r-1
step5. If (f == r ) reset pointer f and r as f = r= -1
step6. Stop

0 Comments:

 
^ Scroll to Top