DEQUE USING LINKED LISTS
#include<stdio.h>
#include<stdlib.h>
struct dqnode
int data;
struct dqnode *next;
};
typedef struct dqnode DQNODE;
int item;
DQNODE *front=NULL,*rear=NULL;
//Inserting item at the front end
void push_dq(int item)
DQNODE *temp = (DQNODE*)malloc(sizeof(DQNODE));
temp->data = item;
temp->next = NULL;
if(front==NULL)
front = temp;
rear = temp;
else
temp->next = front;
front = temp;
}
}
//Removing item from the front end
int pop_dq()
int itm;
if(front==NULL)
printf("\nEmpty queue..No deletion possible...\n");
else if(front==rear)
itm = front->data;
front = NULL;
rear = NULL;
else
itm = front->data;
front = front->next;
return itm;
//Insert item at the rear
void inject(int item)
DQNODE *temp = (DQNODE*)malloc(sizeof(DQNODE));
temp->data = item;
temp->next = NULL;
//DQ empty
if(rear==NULL)
//Inserting first element
front = temp;
rear = temp;
else
rear->next = temp;
rear = temp;
//Delete item from rear end
int eject()
int itm;
DQNODE *temp = front;
if(rear==NULL)
printf("\nDeque is empty..Nothing to eject...\n");
return 0;
else if(rear==front)
itm = rear->data;
rear = NULL;
front = NULL;
}
else
itm = rear->data;
//traverse the list to find the second last item
while(temp->next!=rear)
temp = temp->next;
rear = temp;
rear->next = NULL;
return itm;
void display_dq()
int i;
DQNODE *temp = front;
if(front==NULL)
printf("\nDeque is empty");
else
printf("\nThe deque is ");
while(temp!=NULL)
printf("\t%d",temp->data);
temp = temp->next;
}
}
void main()
int ch;
do
printf("\nMenu\n1.Insert at front\n2.Insert at rear \n3.Delete from front\n4.Delete
from rear\n5.Display from front\n6.Exit\n");
printf("Enter choice : ");
scanf("%d", &ch);
switch(ch)
case 1: printf("\nEnter the item to insert :");
scanf("%d",&item);
push_dq(item);
break;
case 2: printf("\nEnter item to be inserted at front end : ");
scanf("%d",&item);
inject(item);
break;
case 3: printf("\nDeletion from front end");
item=pop_dq();
printf("\nDeleted %d",item);
break;
case 4: printf("\nDeletion from rear end");
item=eject();
printf("\nDeleted %d",item);
break;
case 5: //printf("\nThe deque is");
display_dq();
break;
case 6: exit(0);
}while(ch!=0);
