Output-Restricted Deque Program Using Array

In an output restricted deque, the deletion of elements is done at one end only, and allows insertion to be done at both the ends of a deque. Write a program to demonstrate output-restricted deque.

Here’s an Output-Restricted Deque Program Using Array.

#include < stdio.h >

#include < conio.h >

#include < alloc.h >

#define MAX 10

struct dqueue
{
int arr[MAX] ;

int front, rear ;
} ;

void initdqueue ( struct dqueue * ) ;

void addqatbeg ( struct dqueue *, int ) ;

void addqatend ( struct dqueue *, int ) ;

int delqatend ( struct dqueue * ) ;

void display ( struct dqueue ) ;

int count ( 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 ) ;

addqatend ( &dq, 15 ) ;

addqatbeg ( &dq, 6 ) ;

addqatend ( &dq, 16 ) ;

addqatbeg ( &dq, 5 ) ;

display ( dq ) ;

n = count ( dq ) ;

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

i = delqatend ( &dq ) ;

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

i = delqatend ( &dq ) ;

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

i = delqatend ( &dq ) ;

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

i = delqatend ( &dq ) ;

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

n = count ( dq ) ;

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

display ( dq ) ;

addqatbeg ( &dq, 5 ) ;

addqatbeg ( &dq, 4 ) ;

addqatbeg ( &dq, 3 ) ;

addqatbeg ( &dq, 2 ) ;

display ( dq ) ;

getch( ) ;
}

/* initializes elements of structure */

void initdqueue ( struct dqueue *p )
{
int i ;

p – > front = p – > rear = -1 ;

for ( i = 0 ; i < MAX ; i++ )

p - > arr[i] = 0 ;
}

/* adds item at begining of dqueue */

void addqatbeg ( struct dqueue *p, int item )
{
int c, i, k ;

if ( p – > front == 0 && p – > rear == MAX )

{

printf ( “\nQueue is full.\n” ) ;

return ;

}

if ( p – > front == -1 && p – > rear == -1 )

{

p – > front = p – > rear = 0 ;

p – > arr[p - > front] = item ;

return ;
}

if ( p – > rear != MAX )

{

c = count ( *p ) ;

k = p – > rear ;

for ( i = 1 ; i < = c ; i++ )

{
p - > arr[k] = p – > arr[k - 1] ;

k– ;
}

p – > arr[k] = item ;

p – > front = k ;

( p – > rear )++ ;

}

else

{

( p – > front )– ;

p – > arr[p - > front] = item ;

}

}

/* adds item at the end of dqueue */

void addqatend ( struct dqueue *p, int item )

{
int i, k ;

if ( p – > front == 0 && p – > rear == MAX )

{

printf ( “\nQueue is full.\n” ) ;

return ;

}

if ( p – > rear == -1 && p – > front == -1 )

{
p – > rear = p – > front = 0 ;

p – > arr[p - > rear] = item ;

( p – > rear )++ ;

return ;

}

if ( p – > rear == MAX )

{
k = p – > front – 1 ;

for ( i = p – > front – 1 ; i < p - > rear ; i++ )

{
k = i ;

if ( k == MAX – 1 )

p – > arr[k] = 0 ;

else

p – > arr[k] = p – > arr[i + 1] ;

}

( p – > rear )– ;

( p – > front )– ;

}

p – > arr[p - > rear] = item ;

( p – > rear )++ ;

}

/* deletes item from end of dqueue */

int delqatend( struct dqueue *p )

{

int item ;

if ( p – > front == -1 && p – > rear == -1 )

{

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

return 0 ;

}

( p – > rear )– ;

item = p – > arr[p - > rear] ;

p – > arr[p - > rear] = 0 ;

if ( p – > rear == 0 )

p – > rear = -1 ;

return item ;
}

/* displays the queue */

void display( struct dqueue dq )

{
int i ;

printf ( “\n front – > ” ) ;

for ( i = 0 ; i < MAX ; i++ )

printf ( "\t%d", dq.arr[i] ) ;

printf ( " < - rear " ) ;
}

/* counts the number of items in dqueue */

int count( struct dqueue dq )

{
int c, i ;

for ( i = c = 0 ; i < MAX ; i++ )

{

if ( dq.arr[i] != 0 )

c++ ;
}

return c ;
}