DOUBLE STACK - ARRAY IMPLEMENTATION

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. 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.

doublestack



Code :

#include
#include
int s1[30],s2[30],capacity=5;
int top1=-1,top2=5;
int isfull()
{
return (top1==top2-1);
}
int isempty()
{
return (top1==-1 && top2==capacity);
}
void pushs1(int x)
{
if(!isfull())
s1[++top1]=x;
else
printf("\n Overflow");
}

void displays1()
{
int i;
printf("\n Stack 1 is\n");
for(i=top1;i>-1;i--)
printf("%d\t",s1[i]);
}

void displays2()
{
int i;
printf("\n Stack 2 is\n");
for(i=capacity-1;i>=top2;i--)
printf("%d\t",s2[i]);
}

void pushs2(int x)
{
if(!isfull())
s2[--top2]=x;
else
printf("\n Overflow");
}
int pops1()
{
if(top1==-1)
printf("\n Error");
else
{
int t;
t=s1[top1];
top1--;
return t;
}
return 0;
}

int pops2()
{
if(top2==capacity)
printf("\n Error");
else
{
int t;
t=s2[top2];
top2++;
return t;
}
return 0;
}
void makeempty()
{
top1=-1;
top2=5;
}
void main()
{
int ch,a=1,j;
while(a)
{
printf("\nOPTIONS :\n1.Push into stack 1 \n2.Push into stack 2 \n3.Topandpop stack 1 \n4.Topandpop stack 2 \n5.Makeempty \n6.Exit \n Enter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\n Enter value to push into stack 1 : ");
scanf("%d",&j);
pushs1(j);
displays1();
break;
case 2:printf("\n Enter value to push into stack 2 : ");
scanf("%d",&j);
pushs2(j);
displays2();
break;
case 3:j=pops1();
printf("\n Top of stack 1 : %d is popped",j);
displays1();
break;
case 4:j=pops2();
printf("\n Top of stack 2 : %d is popped",j);
displays2();
break;
case 5:makeempty();
printf(“\n Both stacks are emptied”);
break;
case 6:a=0;
exit(0);
default:printf("\nInvalid choice");
}
}
}

Goal of the code :

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

Variables used :

s1 - The array which contains elements of stack 1
s2 - The array which contains elements of stack 2
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
t -temporary variable to hold value momentarily

Functions used :


Functions


Use
isfull()

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

To check whether the array containing the stacks is empty
pushs1()

To insert element into stack 1
pushs2()

To insert element into stack 2
pops1()

To return and delete the top-most element in stack 1
pops2()

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

To empty both the stacks
displays1()

To display contents of stack 1
displays2()

To display contents of stack 2
main()

To implement the double stack



Implementation :

Initial condition :

capacity = 5
The array is allocated a default size of 5.
top1=-1
top2=5(capacity)

In main() :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.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

DOUBLE STACK - ARRAY IMPLEMENTATION

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. 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 DOUBLE STACK IMPLEMENTATION

(with structures)

Introduction :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

DOUBLE STACK - ARRAY IMPLEMENTATIONDOUBLE STACK IMPLEMENTATION
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

DOUBLE STACK - ARRAY IMPLEMENTATION

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. 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.

doublestack
(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

DOUBLE STACK - ARRAY IMPLEMENTATION

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. 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.

doublestack

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. 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.

doublestack

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

DOUBLE STACK - ARRAY IMPLEMENTATION

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. 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.

doublestackare 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.

doublestack

doublestack1

DOUBLE STACK - ARRAY IMPLEMENTATION

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. 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.

doublestack

*
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.
*
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 case :

The output of the code is :

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 1

Enter value to push into stack 1 : 1

Stack 1 is
1

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 1

Enter value to push into stack 1 : 2

Stack 1 is
2 1

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 2

Enter value to push into stack 1 : 9

Stack 2 is
9

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 2

Enter value to push into stack 1 : 8

Stack 1 is
9 8

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 3

Top of stack 1: 2 is popped
Stack 1 is
1

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 4

Top of stack 2: 8 is popped
Stack 2 is
9

OPTIONS :
1.Push into stack 1
2.Push into stack 2
3.Topandpop stack1
4.Topandpop stack 2
5.Make empty
6.Exit
Enter choice : 5

Both stacks are emptied.

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 3.

**********