Program On Deque That Implements A Linked List

A deque is a data structure that allows both deletion as well as insertion of elements to be done at both ends. Here’s a handy C program to implement deque using linked list.

Here’s an Program on deque that implements a linked list.

#include < stdio.h >
#include < conio.h >
#include < alloc.h >

struct node

{
int data ;

struct node *link ;

} ;

struct dqueue

{
struct node *front ;

struct node *rear ;
} ;

void initdqueue ( struct dqueue * ) ;

void addqatend ( struct dqueue *, int item ) ;

void addqatbeg ( struct dqueue *, int item ) ;

int delqatbeg ( struct dqueue * ) ;

int delqatend ( struct dqueue * ) ;

void display ( struct dqueue ) ;

int count ( struct dqueue ) ;

void deldqueue ( struct dqueue * ) ;

void main( )
{
struct dqueue dq ;

int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;

addqatbeg ( &dq, 10 ) ;

addqatend ( &dq, 12 ) ;

addqatbeg ( &dq, 9 ) ;

addqatend ( &dq, 13 ) ;

addqatbeg ( &dq, 8 ) ;

addqatend ( &dq, 14 ) ;

addqatbeg ( &dq, 7 ) ;

display ( dq ) ;

n = count ( dq ) ;

printf ( “\nTotal elements: %d”, n ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatbeg ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

i = delqatend ( &dq ) ;

printf ( “\nItem extracted = %d”, i ) ;

display ( dq ) ;

n = count ( dq ) ;

printf ( “\nElements Left: %d”, n ) ;

deldqueue ( &dq ) ;

getch( ) ;
}

/* initializes elements of structure */

void initdqueue ( struct dqueue *p )
{
p – > front = p – > rear = NULL ;
}

/* adds item at the end of dqueue */

void addqatend ( struct dqueue *p, int item )
{
struct node *temp ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) );

temp – > data = item ;

temp – > link = NULL ;

if ( p – > front == NULL )

p – > front = temp ;

else

p – > rear – > link = temp ;

p – > rear = temp ;
}

/* adds item at begining of dqueue */

void addqatbeg ( struct dqueue *p, int item )
{
struct node *temp ;

int *q ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) );

temp – > data = item ;

temp – > link = NULL ;

if ( p – > front == NULL )

p – > front = p – > rear = temp ;

else

{

temp – > link = p – > front ;

p – > front = temp ;
}
}
/* deletes item from begining of dqueue */

int delqatbeg ( struct dqueue *p )
{
struct node *temp = p – > front ;

int item ;

if ( temp == NULL )

{

printf ( “\nQueue is empty.” ) ;

return 0 ;
}

else

{
temp = p – > front ;

item = temp – > data ;

p – > front = temp – > link ;

free ( temp ) ;

if ( temp == NULL )

p – > rear = NULL ;

return ( item ) ;
}
}

/* deletes item from end of dqueue */

int delqatend ( struct dqueue *p )
{
struct node *temp , *rleft, *q ;

int item ;

temp = p – > front ;

if ( p – > rear == NULL )

{
printf ( “\nQueue is empty.” ) ;

return 0 ;
}

else

{
while ( temp != p – > rear )

{
rleft = temp ;

temp = temp – > link ;
}
q = p – > rear ;

item = q – > data ;

free ( q ) ;

p – > rear = rleft ;

p – > rear – > link = NULL ;

if ( p – > rear == NULL )

p – > front = NULL ;

return ( item ) ;
}
}
/* displays the queue */

void display ( struct dqueue dq )
{
struct node *temp = dq.front ;

printf ( “\nfront – > ” ) ;

while ( temp != NULL )
{
if ( temp – > link == NULL )
{
printf ( “\t%d”, temp – > data ) ;

printf ( ” < - rear" ) ;
}
else
printf ( "\t%d", temp - > data ) ;

temp = temp – > link ;
}
printf ( “\n” ) ;
}

/* counts the number of items in dqueue */

int count ( struct dqueue dq )
{
int c = 0 ;
struct node *temp = dq.front ;

while ( temp != NULL )
{
temp = temp – > link ;
c++ ;
}

return c ;
}

/* deletes the queue */

void deldqueue ( struct dqueue *p )
{
struct node *temp ;

if ( p – > front == NULL )
return ;

while ( p – > front != NULL )
{
temp = p – > front ;
p – > front = p – > front – > link ;
free ( temp ) ;
}
}