Question

Write code to implement a queue using arrays in which insertions and deletions can be made from either end of the structure (such a queue is called deque). Your code should be able to perform the following operations 

(i) Insert element in a deque 

(ii) Remove element from a deque 

(iii) Check if deque is empty 

(iv) Check if it is full 

(v) Initialize it

Answer 1

Here there are 4 operations 

1. q insert front 

2. q insert rear 

3. q delete front 

4. q delete rear

when front = rear = -1, queue is empty when (rear+1) mod size of queue = front queue is full. Here the queue is to be used circularly. 

(1) q insert front 

if (front==rear==-1) 

then front=rear=0 

q (front)=item 

else if(rear+1)mod sizeof q=front 

q is full, insertion not possible else front = (front + sizeof q-1) mod sizeof q

(2) q insert rear 

if (front==rear==-1) 

front=rear=0 

q(rear)=item 

else if (rear+1) mod sizeof queue + front 

queue is full, insertion not possible 

else rear = (rear+1) mode sizeof queue 

q(rear) = item

(3) q delete front 

if (front==rear==-1)

queue is empty

else if (front==rear)

k = q(front), front = rear= -1

return(k)

else k=q(front)

front = (front+1) mod sizeof queue

return (k)

(4) q delete rear

if (front==rear==-1)

queue is empty

else if (front==rear)

k = q(rear), front=rear=-1

return(k)

else

k=q(rear)

rear = (rear +size of queue -1) mod sizeof q 

return (k)