Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write functions for inserting and deleting at both the ends.
Ans:
struct Deque
{
int info;
struct Deque *left, *right;
}*head, *tail;
add(struct Deque *p, int x)
{
struct Deque *temp;
temp = malloc (sizeof(struct Deque), 1);
temp -> info = x;
if(p == head)
{
temp->right = head; temp->left = NULL; head->left = temp;
head = temp;
}
else if(p == tail)
{
temp->left = tail; temp->right = NULL; tail->right = temp; tail = temp;
}
}
delete(struct Deque *p, int x)
{
struct Deque *temp;
if(p == head)
{
temp = head;
head = head->right;
head->left = NULL; temp->right = NULL; free(temp);
}
else if(p == tail)
{
temp = tail;
tail = tail->left; tail->right = NULL; temp->left = NULL; free(temp);
}
}