Multiple Stack in Data Structure

Sometimes a program requires two stacks containing the same type of items. If two stacks are stored in separate arrays, then one stack might overflow while there was considerable unused space in the other. Suppose there are two stacks Stack A and Stack B of size 3 and 10 respectively and following elements are to be inserted in the stacks.

To avoid this problem is to put all the space in one array and let one stack grow from one end of the array and the other stack start at the other end and growing in the opposite direction towards the first stack.

In this way, if one stack turn out to be large and the other small, then they will still both fit and the other small, then they will still both fit and there will no overflow until all the space is actually used.

For e.g. converting above mentioned stack-A and stack-B into multiple stack.

Insertion of a new element in stack A:

Algorithm: PUSHA (S, ITEM)

This algorithm inserts an element ‘ITEM’ onto stack A.

Step 1: [ Check the stack overflow. ]

If TOPA = TOPB – 1 , then

Write (‘Stack overflow’)

and Return.

[ End of If structure]

Step 2: [ Change the value of TOP. ]

TOPA := TOPA + 1

Step 3: [ Insert an element ]

S[TOPA] := ITEM

Step 4: [ Finished ]

Return.

Deletion of an element from stack A:

Algorithm: POPA (S, ITEM)

This algorithm deletes the top element from stack A and assigns its value to ‘ITEM’.

Step 1: [ Check the stack underflow. ]

If TOPA = 0, then

Write (‘Stack underflow’)

and Return.

[ End of If structure]

Step 2: [ Assign TOP element to ITEM. ]

ITEM := S[TOPA]

Step 3: [Change the value of TOP. ]

TOPA := TOPA – 1

Step 4: [ Finished ]

Return.

Insertion of a new element in stack B:

Algorithm: PUSHB (S, ITEM)

This algorithm inserts an element ‘ITEM’ onto stack B.

Step 1: [ Check the stack overflow. ]

If TOPB = TOPB + 1 , then

Write (‘Stack overflow’)

and Return.

[ End of If structure]

Step 2: [Change the value of TOP. ]

TOPB := TOPB – 1

Step 3: [ Insert an element ]

S[TOPB] := ITEM

Step 4: [ Finished ]

Return.

Deletion of an element from stack B:

Algorithm: POPB (S, ITEM)

This algorithm deletes the top element from stack B and assigns its value to ‘ITEM’.

Step 1: [ Check the stack underflow. ]

If TOP = MAX + 1, then

Write (‘Stack underflow’)

and Return.

[ End of If structure]

Step 2: [ Assign TOP element to ITEM. ]

ITEM := S[TOPB]

Step 3: [Change the value of TOP. ]

TOPB := TOPB + 1

Step 4: [ Finished ]

Return.