| Computer Science Contents............... | Data Structures | Electronics...... | Networks.... | MICRO Processors | Operating Systems |
|---|
| Data Strucutres | Linked Lists | Binary Trees | Expression Converstion's | Infix To Postfix | Infix To Prefix | Postfix To Prefix | Postfix To Infix | Postfix Expression Evaluation |
|---|
| Home............ | Linked List | Binary Trees | Arrays | Stacks | Queues | Graphs | Searching Methods | Sorting Method |
|---|
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 10void 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( ) ;
printf ( "\nitem popped out is : %d", n ) ;}/* pushes item on the stack */
void push ( int data )
{if ( pos == MAX - 1 )
printf ( "\nStack is full" ) ;
else
{
pos++ ;
stack[ pos ] = data ;
}
}
/* pops off the items from the stack */
int pop( )
{
int data ;
if ( pos == -1 )
{
printf ( "\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.
#include "alloc.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 ) ;
printf ( "No. of items in stack = %d" , count ( top ) ) ;
printf ( "\nItems extracted from stack : " ) ;
item = pop ( &top ) ;
printf ( "%d ", item ) ;
item = pop ( &top ) ;
printf ( "%d ", item ) ;
item = pop ( &top ) ;
printf ( "%d ", item ) ;
stack_display ( top ) ;
printf ( "No. of items in stack = %d" , 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 )
printf ( " 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 )
{
printf ( "\n" ) ;
/* traverse the entire linked list */
while ( q != NULL )
{
printf ( "%2d ", q -> data ) ;
q = q -> link ;
}
printf ( "\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 ;
}