Double ended queues are implemented along doubly linked lists.
A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and right pointers. The right pointer points to the next node at the right while the left pointer points to the previous node at the left. Program 9 described the linked list implementation of a Dequeue.
Program 9 : Linked list implementation of a Dequeue
# include "stdio.h"
#define NULL 0
struct dq {
int info;
int *left;
int *right;
};
typedef struct dq *dqptr;
dqptr p, tp;
dqptr head;
dqptr tail;
main()
{
int choice, I, x;
dqptr n;
dqptr getnode();
printf("\n Enter 1: Start 2 : Insertion at Front 3 : Insertion at Rear 4: Delete at Front 5: Delete at Back");
while (1)
{
printf("\n 1: Start 2 : Add at Front 3 : Add at Back 4: Delete at Front 5: Delete at Back 6 : exit");
scanf("%d", &choice);
switch (choice)
{
case 1:
create_list();
break;
case 2:
eq_front();
break;
case 3:
eq_back();
break;
case 4:
dq_front();
break;
case 5:
dq_back();
break;
case 6 :
exit(6);
}
}
}
create_list()
{
int I, x;
dqptr t;
p = getnode();
tp = p;
p->left = getnode();
p->info = 10;
p_right = getnode();
return;
}
dqptr getnode()
{
p = (dqptr) malloc(sizeof(struct dq));
return p;
}
dq_empty(dq q)
{
return q->head = = NULL;
}
eq_front(dq q, void *info)
{
if (dq_empty(q))
q->head = q->tail = dcons(info, NULL, NULL);
else
{
q-> head -> left =dcons(info, NULL, NULL);
q->head -> left ->right = q->head;
q ->head = q->head ->left;
}
}
eq_back(dq q, void *info)
{
if (dq_empty(q))
q->head = q->tail = dcons(info, NULL, NULL)
else
{
q-> tail -> right =dcons(info, NULL, NULL);
q->tail -> right -> left = q->tail;
q ->tail = q->tail ->right;
}
}
dq_front(dq q)
{
if dq is not empty
{
dq tp = q-> head;
void *info = tp -> info;
q ->head = q->head-> right;
free(tp);
if (q->head = = NULL)
q -> tail = NULL;
else
q -> head -> left = NULL;
return info;
}
}
dq_back(dq q)
{
if (q!=NULL)
{
dq tp = q-> tail;
*info = tp -> info;
q ->tail = q->tail-> left;
free(tp);
if (q->tail = = NULL)
q -> head = NULL;
else
q -> tail -> right = NULL;
return info;
}
}