Illustrate to implement deque using circular linked list?

Answer 1

#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 )

return ;

while ( p -> front != NULL )

{

temp = p -> front ;

p -> front = p -> front -> link ;

free ( temp ) ;

}

}

Answer 2

First, while a linked list is certainly a good container for a queue, it isn't a queue. It is a list. A list can have items randomly added and removed at any given location. A queue is a container where you push items into the queue by enqueuing an remove items by dequeuing. It may be better to think of a queue as a FIFO.

That said, a double linked list is linked forward and in reverse. So each element has a reference to the next item in the list and a link to the previous item as well.

When you enqueue items, you would for example insert an item at the start of the list. This item would have no previous element, but will point to the old first element as its next element.

When you dequeue from the list, you will "pop" the element that is referenced as the last element of the list. Then you'll set the next last item to be the item referenced by the item you popped as the old last item. You would then removed the reference tonthe next item from the new tail element.

Hope this helps!

- Darren