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