Dequeue:

DEQueue stands for double ended queue. In this, insertion and Deletion occur at both the ends i.e. front and rear of the queue.

The common operations on dequeue are:

§ insertFirst(): to add element at the end of a dequeue.

§ insertLast(): to delete element at the beginning of a dequeue.

§ deleteFirst(): to remove first element of the dequeue.

§ deleteLast(): to remove last element of the dequeue.

§ isFull(): isfull finds out whether the dequeue is full.

§ isEmpty(): isempty finds out whether the circular dequeue is empty.

§ create(): to create an empty dequeue

Program to implement a dequeue:

class node

{

public int x;

public node next;

}

class DEQueue

{

public node front,rear;

DEQueue()

{

front=rear=null;

}

void addFront (int v)

{

node temp=new node();

temp.x=v;

if(front==null)

front=rear=temp;

else

{

temp.next=front;

front=temp;

}

}

void addRear (int v)

{

node temp=new node();

temp.x=v;

temp.next=null;

if(front==null)

front=rear=temp;

else

{

rear.next=temp;

rear=temp;

}

}

int delFront()

{

int v=front.x;

node temp=front;

front=front.next;

temp=null;

return v;

}

int delRear()

{

int v=rear.x;

node ptr=front,temp;

while(ptr.next!=rear)

ptr=ptr.next;

temp=rear;

rear=ptr;

rear.next=null;

temp=null;

return v;

}

void show()

{

System.out.println("\nDouble Ended Queue Elements:");

for(node ptr=front;ptr!=rear;ptr=ptr.next)

System.out.println("\t"+ptr.x);

System.out.println("\t"+rear.x);

}

}

class DEQueueTest

{

public static void main(String as[])

{

DEQueue q1=new DEQueue();

q1.addFront(30);

q1.addFront(40);

q1.addRear(88);

q1.addRear(99);

q1.show();

q1.delFront();

q1.delRear();

q1.show();

}

}

/* Output */

Double Ended Queue Elements:

40

30

88

99

Double Ended Queue Elements:

30

88