Stacks

Stacks and queues are two very common and popular data structures. These data structures are often implemented using arrays since most programming languages provide array as a predefined data type, and such an implementation is therefore quite easy. However, when implemented as an array these data structures suffer from the basic limitation of an array: that its size cannot be increased or decreased once it is declared. As a result one ends up reserving either too much space or too less space for an array and in turn for a stack or a queue. This difficulty is eliminated when we implement these data structures using linked lists. Before we do so let us formally define these data structures.

A stack is a data structure in which addition of new element or deletion of existing element always takes place at the same end. This end is often known as top of stack. This situation can be compared to a stack of plates in a cafeteria where every new plate added to the stack is added at the top. Similarly, every new plate taken off the stack is also from the top of the stack. There are several applications where stack can be put to use. For example, recursion, keeping track of function calls, evaluation of expressions etc. Unlike a stack, in a queue the addition of new element takes place at the end (called rear of queue), whereas deletion takes place at the other end (called front of queue). The following figure shows these two data structures. A stack is often called a Last-In-First-Out (LIFO) structure, whereas a queue is called a First-In-First-Out (FIFO) structure

Implementing A Stack Using An Array

The program given below implements the stack data structure using an array. In this program the elements are pushed into array stack[ ] through push( ) function. The parameters passed to push( ) are the base address of the array, the position in the stack at which the element is to be placed and the element itself. Care is taken by the push( ) function that the user does not try to place the element beyond the bounds of the stack. This is done by checking the value stored in pos. pop( ) function pops out the last element stored in the stack[ ]. Because, pos holds the position which has the last element in the stack.

/* To pop and push items in a stack */

#define MAX 10

void push ( int ) ;

int pop( ) ;

int stack[MAX] ;

int pos ;

void main( )

{

int n ;

clrscr( ) ;

pos = -1 ; /* stack is empty */

push ( 10 ) ;

push ( 20 ) ;

push ( 30 ) ;

push ( 40 ) ;

n = pop( ) ;

printf ( "\nitem popped out is : %d", n ) ;

n = pop( ) ;

cout<< "\nitem popped out is : “<< n ;

}

/* pushes item on the stack */

void push ( int data )

{

if ( pos == MAX - 1 )

cout<<”\nStack is full" ;

else

{

pos++ ;

stack[ pos ] = data ;

}

}

/* pops off the items from the stack */

int pop( )

{

int data ;

if ( pos == -1 )

{

cout<< "\nStack is empty" ;

return ( -1 ) ;

}

else

{

data = stack[ pos ] ;

pos-- ;

return ( data ) ;

}

}

Implementing Stack As A Linked List

In this program stack is implemented and maintained using linked list. This implementation is more sophisticated compared to the one that uses an array, the added advantage being we can push as many elements as we want. A new node is created by push( ) (using malloc( )) every time an element is pushed in the stack. Each node in the linked list contains two members, data holding the data and link holding the address of the next node. The end of the stack is identified by the the node holding NULL in its link part. The pop( ) function pops out the last element inserted in the stack and frees the memory allocated to hold it. stack_display( ) displays all the elements that stack holds. count( ) counts and returns the number of elements present in the stack.

#include "alloc.h"

#include<iostream.h>

struct node

{

int data ;

struct node *link ;

} ;

push ( struct node **, int ) ;

pop ( struct node ** ) ;

main( )

{

struct node *top ; /* top will always point to top of a stack */

int item ;

top = NULL ; /* empty stack */

push ( &top, 11 ) ;

push ( &top, 12 ) ;

push ( &top, 13 ) ;

push ( &top, 14 ) ;

push ( &top, 15 ) ;

push ( &top, 16 ) ;

push ( &top, 17 ) ;

clrscr( ) ;

stack_display ( top ) ;

cout<< "No. of items in stack = “<< count ( top) ;

cout<< "\nItems extracted from stack : " ;

item = pop ( &top ) ;

cout<<item;

item = pop ( &top ) ;

cout<<item;

item = pop ( &top ) ;

cout<<item;

stack_display ( top ) ;

cout<< "No. of items in stack = "<<count ( top) ;

}

/* adds a new element on the top of stack */

push ( struct node **s, int item )

{

struct node *q ;

q = malloc ( sizeof ( struct node ) ) ;

q -> data = item ;

q -> link = *s ;

*s = q ;

}

/* removes an element from top of stack */

pop ( struct node **s )

{

int item ;

struct node *q ;

/* if stack is empty */

if ( *s == NULL )

cout<<" stack is empty";

else

{

q = *s ;

item = q -> data ;

*s = q -> link ;

free ( q ) ;

return ( item ) ;

}

}

/* displays whole of the stack */

stack_display ( struct node *q )

{

cout<<endl ;

/* traverse the entire linked list */

while ( q != NULL )

{

cout<<q -> data;

q = q -> link ;

}

cout<<"\n" ;

}

/* counts the number of nodes present in the linked list representing a stack */

count ( struct node * q )

{

int c = 0 ;

/* traverse the entire linked list */

while ( q != NULL )

{

q = q -> link ;

c++ ;

}

return c ;

}