DOUBLE STACK IMPLEMENTATION

(with structures)

Introduction :

Double stack means two stacks which are implemented using a single array. To prevent memory wastage, the two stacks are grown in opposite direction.

Structure has the following advantages.

*

Clarity

As programs get bigger, they get more confusing if they're not structured. Restricting programming logic to structures that have only one point of exit and entry makes it much easier to track the 'flow' of logic.

*

Efficiency

*

Maintenance
Programs that follow a consistent set of clearly defined structures (having single points of entry and exit) are much easier to read and debug. Especially when maintenance issues arise long after the program is written.

In this program, the pointer tops1 and tops2 points to top-most element of stack 1 and stack 2 respectively. Initially, tops1 is initialized as -1 and tops2 is initialized the capacity. As the elements are pushed into stack 1, tops1 is incremented. Similarly, as the elements are pushed into stack 2, tops2 is decremented. So, the array is full when tops1=tops2-1. Beyond this, pushing an element into any stack will lead to overflow condition. The pictorial representation of double stack is shown below.

doublestack1



Code :

#include
#include
#define minstacksize 5
typedef struct stackrecord
{
int *a;
int top1,top2,capacity;
}*stack;
void makeempty(stack s, int n)
{
if(n==1)
s->top1=-1;
else
s->top2=s->capacity;
}
stack createstack(int max)
{
stack s;
if(max
{
printf("\n Stack size is too small");
return NULL;
}
else
{
s=(stack)malloc(sizeof(stack));
if(s==NULL)
{
printf("\n Out of space");
return NULL;
}
s->a=(int*)malloc(max*sizeof(int));
if(s->a==NULL)
{
printf("\n Out of space");
return NULL;
}
s->capacity=max;
makeempty(s,1);
makeempty(s,2);
return s;
}
}
void display(stack s,int n)
{
int i;
if(n==1)
{
printf("\n Stack 1 :\n");
for(i=s->top1;i>=0;i--)
printf("%d\t",s->a[i]);
}
else
{
printf("\n Stack 2 :\n");
for(i=s->top2;icapacity-1;i++)
printf("%d\t",s->a[i]);
}
}
void dispose(stack s)
{
if(s!=NULL)
{
free(s->a);
free(s);
}
}
int isfull(stack s)
{
return (s->top1==s->top2-1);
}
int isempty(stack s,int n)
{
return (n==1?s->top1==-1:s->top2==s->capacity);
}
void push(stack s,int n,int x)
{
if(isfull(s))
printf("\n Overflow");
else
{
if(n==1)
s->a[++s->top1]=x;
else
s->a[--s->top2]=x;
}
}
void pop(stack s,int n)
{
if(isempty(s,n))
printf("\n Underflow");
else
{
if(n==1)
s->top1--;
else
s->top2++;
}
}
int top(stack s,int n)
{
if(isempty(s,n))
{
printf("\n Underflow");
return -1;
}
else
{
if(n==1)
return (s->a[s->top1]);
else
return (s->a[s->top2]);
}
}
int topandpop(stack s,int n)
{
if(isempty(s,n))
{
printf("\n Underflow");
return -1;
}
else
{
if(n==1)
return(s->a[s->top1--]);
else
return (s->a[s->top2++]);
}
}

void main()
{
stack s;
s=createstack(10);
int ch,a=1,j,n;
while(a)
{
printf("\n Options :\n1.Push\n2.Topandpop\n3.Pop\n4.Top\n5.Exit\n Enter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\n Enter the stack :");
scanf("%d",&n);
printf("\n Enter value to be inserted : ");
scanf("%d",&j);
push(s,n,j);
display(s,n);
break;
case 2:printf("\n Enter the stack : ");
scanf("%d",&n);
printf("\n Top of stack %d is %d",n,topandpop(s,n));
display(s,n);
break;
case 3:printf("\n Enter the stack : ");
scanf("%d",&n);
pop(s,n);
display(s,n);
break;
case 4:printf("\n Enter the stack : ");
scanf("%d",&n);
printf("\n Top of stack %d is %d",n,top(s,n));
display(s,n);
break;
case 5:printf("\n End");
exit(0);
default:printf("\n Invalid choice");
}
}
dispose(s);
}




Goal of the code :

The aim of this code is to implement two stacks with a single array using structures.

Variables used :

a - The array which contains elements of the double-stack

capacity- The maximum size of the array implementing the 2 stacks

top1 - This points to the top-most element of stack 1

top2 - This points to the top-most element of stack 2

i - Counter variable

s - This points to the stack

n - The variable which holds the stack number (i.e. 1 or 2 indicating stack 1 or stack 2 )

Functions used :

Functions


Use
isfull()

To check whether the array containing the stacks is full
isempty()

To check whether the stack is empty
push

To insert an element into stack
pop()

To delete the top-most element of the stack
top()

To return the top-most element of the stack
topandpop()

To return and delete the top-most element of the stack
makeempty()

To empty the stack
display()

To display contents of stack
main()

To implement the double stack

Implementation :

Initial conditions :

capacity = 10

The array is allocated a default size of 10.

top1 = -1

top2 = 10 (capacity)

In main() :

*
List of options is displayed as menu and the user's choice is stored in the variable 'ch'.
*
Using switch-case the control is directed to the specified function.
*
For all the function, the stack to be worked upon is got as input from user and stored in 'n' variable.
*
In case of push, the value to be inserted is got from the user.
*
In case of pop, the top-most element is printed.
*
In each case, the stack which is being worked upon is displayed.

Test cases :

The output of the code is as below.

OPTIONS :
1.Push
2.Topandpop
3.Pop
4.Top
5.Exit
Enter choice : 1

Enter the stack : 1

Enter the value to be inserted : 1

Stack 1 :
1

OPTIONS :
1.Push
2.Topandpop
3.Pop
4.Top
5.Exit
Enter choice : 1

Enter the stack : 2

Enter the value to be inserted : 8

Stack 2 :
8

OPTIONS :
1.Push
2.Topandpop
3.Pop
4.Top
5.Exit
Enter choice : 4

Enter the stack : 1

Top of stack 1 is 1

Stack 1 :
1

OPTIONS :
1.Push
2.Topandpop
3.Pop
4.Top
5.Exit
Enter choice : 2

Enter the stack : 2

Top of stack 2 is 8

Stack 2 :


OPTIONS :
1.Push
2.Topandpop
3.Pop
4.Top
5.Exit
Enter choice : 3

Enter the stack : 1

Stack 1 :


OPTIONS :
1.Push
2.Topandpop
3.Pop
4.Top
5.Exit
Enter choice : 5

End

Compatibility :

Compatible with all computers which is capable of running gcc-4.4.0. The program has been tested with the above version of gcc as of June 6.

***********