Page 153 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes display(p);
break;
case 4:
exit(0);
} /*switch closed */
printf(“\n\n\t\t Do you want to run it again y/n”);
scanf(“%c”,&choice);
} while(choice==’y’);
} /*end of function main*/

Similarly, as we did in the implementation of stack using arrays, to know the working of this
program, we executed it thrice and pushed 3 elements (10, 20, 30). Then we call the function
display in the next run to see the elements in the stack.
In this program, initially, we defined a structure called node. Each node contains two portions,
data and a pointer that keeps the address of the next node in the list. The Push function will insert
a node at the front of the linked list, whereas pop function will delete the node from the front of
the linked list. There is no need to declare the size of the stack in advance as we have done in the
program where in we implemented the stack using arrays since we create nodes dynamically as
well as delete them dynamically. The function display will print the elements of the stack.

Task Analyze the problems that takes place in the sequential implementation of stacks.

Self Assessment

Fill in the blanks:

8. ................... will display the elements of the stack.
9. In the case of a ................... stack, we shall push and pop nodes from one end of a linked list.

9.4 Multi Stacks

Until now, we have discussed the representation of a single stack. Now we will discuss the
concept of data representation for several stacks. Let us see an array X whose dimension is m.
For convenience, we shall assume that the indexes of the array commence from 1 and end at m.
If we have only 2 stacks to implement in the same array X, then the solution is simple.
Suppose A and B are two stacks. We can define an array stack A with n elements and an array
1
stack B with n elements.
2
!
Caution Overflow may occur when either stack A contains more than n elements or stack
1
B contains more than n elements.
2
Suppose, instead of that, we define a single array stack with n = n + n elements for stack A and
1 2
B together. See the Figure 9.13 below. Let the stack A “grow” to the right, and stack B “grow” to
the left. In this case, overflow will occur only when A and B together have more than n = n + n
1 2
elements. It does not matter how many elements individually are there in each stack.

146 LOVELY PROFESSIONAL UNIVERSITY