Implements linked list as a stack.

C: Program implements linked list as a stack.

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

/* structure containing data part and linkpart */
struct node
{
    int data ;
    struct node *link ;
} ;

void push ( struct node **, int ) ;
int pop ( struct node ** ) ;
void delstack ( struct node ** ) ;

void main( )
{
    struct node *s = NULL ;
    int i ;

    clrscr( ) ;

    push ( &s, 14 ) ;
    push ( &s, -3 ) ;
    push ( &s, 18 ) ;
    push ( &s, 29 ) ;
    push ( &s, 31 ) ;
    push ( &s, 16 ) ;

    i = pop ( &s ) ;
    printf ( "\nItem popped: %d", i ) ;

    i = pop ( &s ) ;
     printf ( "\nItem popped: %d", i ) ;

    i = pop ( &s ) ;
    printf ( "\nItem popped: %d", i ) ;

    delstack ( &s ) ;

    getch( ) ;
}

/* adds a new node to the stack as linked list */
void push ( struct node **top, int item )
{
    struct node *temp ;
    temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

    if ( temp == NULL )
        printf ( "\nStack is full." ) ;

    temp -> data = item ;
    temp -> link = *top ;
    *top = temp ;
}

/* pops an element from the stack */
int pop ( struct node **top )
{
    struct node *temp ;
    int item ;

    if ( *top == NULL )
    {
        printf ( "\nStack is empty." ) ;
        return NULL ;
    }

    temp = *top ;
    item = temp -> data ;
    *top = ( *top ) -> link ;

    free ( temp ) ;
    return item ;
}

/* deallocates memory */
void delstack ( struct node **top )
{
    struct node *temp ;

    if ( *top == NULL )
        return ;

    while ( *top != NULL )
    {
        temp = *top ;
        *top = ( *top ) -> link ;
        free ( temp ) ;
    }
}

Implements array as a stack.

C: Program implements array as a stack.

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

#define MAX 10

struct stack
{
    int arr[MAX] ;
    int top ;
} ;

void initstack ( struct stack * ) ;
void push ( struct stack *, int item ) ;
int pop ( struct stack * ) ;

void main( )
{
    struct stack s ;
    int i ;

    clrscr( ) ;

    initstack ( &s ) ;

    push ( &s, 11 ) ;
    push ( &s, 23 ) ;
    push ( &s, -8 ) ;
    push ( &s, 16 ) ;
    push ( &s, 27 ) ;
    push ( &s, 14 ) ;
    push ( &s, 20 ) ;
    push ( &s, 39 ) ;
    push ( &s, 2 ) ;
    push ( &s, 15 ) ;
    push ( &s, 7 ) ;

    i = pop ( &s ) ;
    printf ( "\n\nItem popped: %d", i ) ;

    i = pop ( &s ) ;
    printf ( "\nItem popped: %d", i ) ;

    i = pop ( &s ) ;
    printf ( "\nItem popped: %d", i ) ;

    i = pop ( &s ) ;
    printf ( "\nItem popped: %d", i ) ;

    i = pop ( &s ) ;
    printf ( "\nItem popped: %d", i ) ;

    getch( ) ;
}

/* intializes the stack */
void initstack ( struct stack *s )
{
    s -> top = -1 ;
}

/* adds an element to the stack */
void push ( struct stack *s, int item )
{
    if ( s -> top == MAX - 1 )
    {
        printf ( "\nStack is full." ) ;
        return ;
    }
    s -> top++ ;
    s -> arr[s ->top] = item ;
}

/* removes an element from the stack */
int pop ( struct stack *s )
{
    int data ;
    if ( s -> top == -1 )
    {
        printf ( "\nStack is empty." ) ;
        return NULL ;
    }
    data = s -> arr[s -> top] ;
    s -> top-- ;
    return data ;
}

Tower of Hanoi

Working of Stack

Queue

Implements a priority queue using an array.

C: Program that implements a priority queue using an array.

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

#define MAX 5

struct data
{
    char job[MAX] ;
    int prno ;
    int ord ;
} ;

struct pque
{
    struct data d[MAX] ;
    int front ;
    int rear ;
} ;

void initpque ( struct pque * ) ;
void add ( struct pque *, struct data ) ;
struct data delete ( struct pque * ) ;

void main( )
{
    struct pque q ;
    struct data dt, temp ;
    int i, j = 0 ;

    clrscr( ) ;

    initpque ( &q ) ;

    printf ( "Enter Job description (max 4 chars) and its priority\n" ) ;
    printf ( "Lower the priority number, higher the priority\n" ) ;
    printf ( "Job     Priority\n" ) ;

    for ( i = 0 ; i < MAX ; i++ )
    {
        scanf ( "%s %d", &dt.job, &dt.prno ) ;
        dt.ord = j++ ;
        add ( &q, dt ) ;
    }
    printf ( "\n" ) ;

    printf ( "Process jobs prioritywise\n" ) ;
    printf ( "Job\tPriority\n" ) ;

    for ( i = 0 ; i < MAX ; i++ )
    {
        temp  = delete ( &q ) ;
        printf ( "%s\t%d\n", temp.job, temp.prno ) ;
    }
    printf ( "\n" ) ;

    getch( ) ;
}

/* initialises data members */
void initpque ( struct pque *pq )
{
    int i ;

    pq -> front = pq -> rear = -1 ;
    for ( i = 0 ; i < MAX ; i++ )
    {
        strcpy ( pq -> d[i].job, '\0' ) ;
        pq -> d[i].prno = pq -> d[i].ord = 0 ;
    }
}

/* adds item to the priority queue */
void add ( struct pque *pq, struct data dt )
{
    struct data temp ;
    int i, j ;

    if ( pq -> rear == MAX - 1 )
    {
        printf ( "\nQueue is full." ) ;
        return ;
    }

    pq -> rear++ ;
    pq -> d[pq -> rear] = dt ;

    if ( pq -> front == -1 )
        pq -> front = 0 ;

    for ( i = pq -> front ; i <= pq -> rear ; i++ )
    {
        for ( j = i + 1 ; j <= pq -> rear ; j++ )
        {
            if ( pq -> d[i].prno > pq -> d[j].prno )
            {
                temp = pq -> d[i] ;
                pq -> d[i] = pq -> d[j] ;
                pq -> d[j] = temp ;
            }
            else
            {
                if ( pq -> d[i].prno == pq -> d[j].prno )
                {
                    if ( pq -> d[i].ord > pq -> d[j].ord )
                    {
                        temp = pq -> d[i] ;
                        pq -> d[i] = pq -> d[j] ;
                        pq -> d[j] = temp ;
                    }
                }
            }
        }
    }
}

/* removes item from priority queue */
struct data  delete ( struct pque *pq )
{
    struct data  t ;
    strcpy ( t.job, "" ) ;
    t.prno = 0 ;
    t.ord = 0 ;

    if ( pq -> front == -1 )
    {
        printf ( "\nQueue is Empty.\n" ) ;
        return t ;
    }

    t = pq -> d[pq -> front] ;
    pq -> d[pq -> front] = t ;
    if ( pq -> front == pq -> rear )
         pq -> front = pq -> rear = -1 ;
    else
         pq -> front++ ;

    return  t ;
}

Priority Queue

Output Restricted Deque

Input Restricted Deque

Implements deque using an array.

C: Program that implements deque using an array.

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

#define MAX 10

void addqatbeg ( int *, int, int *, int * ) ;
void addqatend ( int *, int, int *, int * ) ;
int delqatbeg ( int *, int *, int * ) ;
int delqatend ( int *, int *, int * ) ;
void display ( int * ) ;
int count ( int * ) ;

void main( )
{
    int arr[MAX] ;
    int front, rear, i, n ;

    clrscr( ) ;

    /* initialises data members */
    front = rear = -1 ;
    for ( i = 0 ; i < MAX ; i++ )
        arr[i] = 0 ;

    addqatend ( arr, 17, &front, &rear ) ;
    addqatbeg ( arr, 10, &front, &rear ) ;
    addqatend ( arr, 8, &front, &rear ) ;
    addqatbeg ( arr, -9, &front, &rear ) ;
    addqatend ( arr, 13, &front, &rear ) ;
    addqatbeg ( arr, 28, &front, &rear ) ;
    addqatend ( arr, 14, &front, &rear ) ;
    addqatbeg ( arr, 5, &front, &rear ) ;
    addqatend ( arr, 25, &front, &rear ) ;
    addqatbeg ( arr, 6, &front, &rear ) ;
    addqatend ( arr, 21, &front, &rear ) ;
    addqatbeg ( arr, 11, &front, &rear ) ;

    printf ( "\nElements in a deque: " ) ;
    display ( arr ) ;

    n = count ( arr ) ;
    printf ( "\nTotal number of elements in deque: %d", n ) ;

    i = delqatbeg ( arr, &front, &rear ) ;
    printf ( "\nItem extracted: %d", i ) ;

    i = delqatbeg ( arr, &front, &rear ) ;
    printf ( "\nItem extracted:%d", i ) ;

    i = delqatbeg ( arr, &front, &rear ) ;
    printf ( "\nItem extracted:%d", i ) ;

    i = delqatbeg ( arr, &front, &rear ) ;
    printf ( "\nItem extracted: %d", i ) ;

    printf ( "\nElements in a deque after deletion: " ) ;
    display ( arr ) ;

    addqatend ( arr, 16, &front, &rear ) ;
    addqatend ( arr, 7, &front, &rear ) ;

    printf ( "\nElements in a deque after addition: " ) ;
    display ( arr ) ;

    i = delqatend ( arr, &front, &rear ) ;
    printf ( "\nItem extracted: %d", i ) ;

    i = delqatend ( arr, &front, &rear ) ;
    printf ( "\nItem extracted: %d", i ) ;

    printf ( "\nElements in a deque after deletion: " ) ;
    display ( arr ) ;

    n = count ( arr ) ;
    printf ( "\nTotal number of elements in deque: %d", n ) ;

    getch( ) ;
}

/* adds an element at the beginning of a deque */
void addqatbeg ( int *arr, int item, int *pfront, int *prear )
{
    int i, k, c ;

    if ( *pfront == 0 && *prear == MAX - 1 )
    {
        printf ( "\nDeque is full.\n" ) ;
        return ;
    }

    if ( *pfront == -1 )
    {
        *pfront = *prear = 0 ;
        arr[*pfront] = item ;
        return ;
    }

    if ( *prear != MAX - 1 )
    {
        c = count ( arr ) ;
        k = *prear + 1 ;
        for ( i = 1 ; i <= c ; i++ )
        {
            arr[k] = arr[k - 1] ;
            k-- ;
        }
        arr[k] = item ;
        *pfront = k ;
        ( *prear )++ ;
    }
    else
    {
        ( *pfront )-- ;
        arr[*pfront] = item ;
    }
}

/* adds an element at the end of a deque */
void addqatend ( int *arr, int item, int *pfront, int *prear )
{
    int i, k ;

    if ( *pfront == 0 && *prear == MAX - 1 )
    {
        printf ( "\nDeque is full.\n" ) ;
        return ;
    }

    if ( *pfront == -1 )
    {
        *prear = *pfront = 0 ;
        arr[*prear] = item ;
        return ;
    }

    if ( *prear == MAX - 1 )
    {
        k = *pfront - 1 ;
        for ( i = *pfront - 1 ; i < *prear ; i++ )
        {
            k = i ;
            if ( k == MAX - 1 )
                arr[k] = 0 ;
            else
                arr[k] = arr[i + 1] ;
        }
        ( *prear )-- ;
        ( *pfront )-- ;
    }
    ( *prear )++ ;
    arr[*prear] = item ;
}

/* removes an element from the *pfront end of deque */
int delqatbeg ( int *arr, int *pfront, int *prear )
{
    int item ;

    if ( *pfront == -1 )
    {
        printf ( "\nDeque is empty.\n" ) ;
        return 0 ;
    }

    item = arr[*pfront] ;
    arr[*pfront] = 0 ;

    if ( *pfront == *prear )
        *pfront = *prear = -1 ;
    else
        ( *pfront )++ ;

    return item ;
}

/* removes an element from the *prear end of the deque */
int delqatend ( int *arr, int *pfront, int *prear )
{
    int item ;

    if ( *pfront == -1 )
    {
        printf ( "\nDeque is empty.\n" ) ;
        return 0 ;
    }

    item = arr[*prear] ;
    arr[*prear] = 0 ;
    ( *prear )-- ;
    if ( *prear == -1 )
        *pfront = -1 ;
    return item ;
}

/* displays elements of a deque */
void display ( int *arr )
{
    int i ;

    printf ( "\n front->" ) ;
    for ( i = 0 ; i < MAX ; i++ )
        printf ( "\t%d", arr[i] ) ;
    printf ( " <-rear" ) ;
}

/* counts the total number of elements in deque */
int count ( int *arr )
{
    int c = 0, i ;

    for ( i = 0 ; i < MAX ; i++ )
    {
        if ( arr[i] != 0 )
            c++ ;
    }
    return c ;
}

Deque

Implements circular queue as an array.

C: Program that implements circular queue as an array.

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

#define MAX 10

void addq ( int *, int, int *, int * ) ;
int delq ( int *, int *, int * ) ;
void display ( int * ) ;

void main( )
{
    int arr[MAX] ;
    int i, front, rear ;

    clrscr( ) ;

    /* initialise data member */
    front = rear = -1 ;
    for ( i = 0 ; i < MAX ; i++ )
        arr[i] = 0 ;

    addq ( arr, 14, &front, &rear ) ;
    addq ( arr, 22, &front, &rear ) ;
    addq ( arr, 13, &front, &rear ) ;
    addq ( arr, -6, &front, &rear ) ;
    addq ( arr, 25, &front, &rear ) ;

    printf ( "\nElements in the circular queue: " ) ;
    display ( arr ) ;

    i = delq ( arr, &front, &rear ) ;
    printf ( "Item deleted: %d", i ) ;

    i = delq ( arr, &front, &rear ) ;
    printf ( "\nItem deleted: %d", i ) ;

    printf ( "\nElements in the circular queue after deletion: " ) ;
    display ( arr ) ;

    addq ( arr, 21, &front, &rear ) ;
    addq ( arr, 17, &front, &rear ) ;
    addq ( arr, 18, &front, &rear ) ;
    addq ( arr, 9, &front, &rear ) ;
    addq ( arr, 20, &front, &rear ) ;

    printf ( "Elements in the circular queue after addition: " ) ;
    display ( arr ) ;

    addq ( arr, 32, &front, &rear ) ;

    printf ( "Elements in the circular queue after addition: " ) ;
    display ( arr ) ;

    getch( ) ;
}

/* adds an element to the queue */
void addq ( int *arr, int item, int *pfront, int *prear )
{
    if ( ( *prear == MAX - 1 && *pfront == 0 ) || (  *prear + 1 == *pfront ) )
    {
        printf ( "\nQueue is full." ) ;
        return ;
    }

    if ( *prear == MAX - 1 )
        *prear = 0 ;
    else
        ( *prear )++ ;

    arr[*prear] = item ;

    if ( *pfront == -1 )
        *pfront = 0 ;
}

/* removes an element from the queue */
int delq ( int *arr, int *pfront, int *prear )
{
    int data ;

    if ( *pfront == -1 )
    {
        printf ( "\nQueue is empty." ) ;
        return NULL ;
    }

    data = arr[*pfront] ;
    arr[*pfront] = 0 ;

    if ( *pfront == *prear )
    {
        *pfront = -1 ;
        *prear = -1 ;
    }
    else
    {
        if ( *pfront == MAX - 1 )
            *pfront = 0 ;
        else
            ( *pfront )++ ;
    }
    return data ;
}

/* displays element in a queue */
void display ( int * arr )
{
    int i ;
    printf ( "\n" ) ;
    for ( i = 0 ; i < MAX ; i++ )
        printf ( "%d\t", arr[i] ) ;
    printf ( "\n" ) ;
}