Page 154 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 9: Stacks

Notes
Figure 9.13: Implementation of Multiple Stacks using Arrays

But, in the case of more than 2 stacks, we cannot represent these in the same way because a one-
dimensional array has only two fixed points X(1) and X(m) and each stack requires a fixed point
for its bottom most element. When more than two stacks, say n, are to be represented sequentially,
we can initially divide the available memoryX(1:m) into n segments. If the sizes of the stacks are
known, then, we can allocate the segments to them in proportion to the expected sizes of the
various stacks. If the sizes of the stacks are not known, then, X(1:m) may be divided into equal
segments. For each stack i, we shall use BM (i) to represent a position one less than the position
in X for the bottom most element of that stack. TM(i), 1 i≤≤ n will point to the topmost element
of stack i. We shall use the boundary condition BM (i) = TM (i) if the ith stack is empty. If we grow
the ith stack in lower memory indexes than the i+1st stack, then, with roughly equal
/
initial segments we have BM (i) = TM (i) = mn (i − 1),1 i ≤ ≤ n , as the initial values of BM (i)
and TM (i).

Figure 9.14: Initial Configuration for n Stacks in X(1:m)

All stacks are empty and memory is divided into roughly equal segments.

Self Assessment

State whether the following statements are true or false:
10. When more than two stacks, say n, are to be represented sequentially, we can initially
divide the available memoryX(1:m) into n segments.
11. If the sizes of the stacks are known, then, we can allocate the segments to them in proportion
to the expected sizes of the various stacks.

9.5 Application of Stacks

Stacks are frequently used in evaluation of arithmetic expressions. An arithmetic expression
consists of operands and operators. Polish notations are evaluated by stacks. Conversions of

LOVELY PROFESSIONAL UNIVERSITY 147