Data Structures & Algorithms
SECTION 4
OBJECTIVES: At the end of the session, the student is expected to be able to
1. discuss implementation issues pertaining to the sequential representation of multiple
stacks using a one-dimensional array (vector)
2. describe memory reallocation strategies for data structures sharing a fixed region of
memory
3. assess the sustainability of using multiple stacks to solve a given problem on the
computer
4. explain the notion of an avail list and describe the basic operations applied on it
5. explain how stacks are implemented as linked lists
DISCUSSION:
In applications which involve the concurrent use of two or more sequentially allocated
stacks, the use of a common vector for all the stacks results in the most efficient utilization of
memory. I particular, this makes it possible to systematically reallocate available memory should
overflow occur in a particular stack.
The figure below shows two stacks coexisting in a common vector S of size n. The
stacks are arranged such that they grow toward each other, with their bottoms anchored at
opposite ends of S. [ How would you initialize the pointers top1 and top2? What conditions
indicate that a stack is empty? That it is full? ]
top1 top2
S(1:n)
1 2 3 4 5 6 7 8 9 . . . . . . n-1 n
x x x x x x x x x x x x x x x x x x x
insertion - - > | | < - - insertion
deletion < - - | | - - > deletion
We initialize the stacks by setting top1 < - - 0 and top2 < - - n+1. Consequently, the
condition top1 = 0 means stack 1 is empty and the condition top2 = n+1 means stack 2 is
empty. The condition top2-top1 = 1 means stack 1 and 2 are full and an attempt to insert onto
either stack will result in an overflow condition. It is obvious that when overflow occurs, all cells
S(1) through S(n) are in use. Thus, the space allocated to S is utilized in an optimal way.
Section 4 Page 1 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
When three or more stacks coexist in a common vector S of size n, it no longer follows
that when overflow occurs in a particular stack that all n cells of S are in use. No matter how we
initially allocate the available space among the stacks and no matter in what directions we make
the stacks grow, it may still happen that one stack runs out of space while others still have
space to spare. To make optimal use of the space allocated to S, we should therefore allow for
the free cells to be reallocated among the stacks so that, at the very least, the stack that
overflows will get the space it needs. This can be accomplished by shifting stack boundaries.
The figure below shows a vector S of size n = 400 in which m = 3 stacks are coexist. The 400
cells are initially allocated equally among the 3 stacks by defining the base pointers B(i)
according to the formulas
B(i) = [n/m] • ( i – 1 ) 1≤ i ≤ m
B(m+1) = n
The base pointers indicate the boundaries, in terms of allocated space, among the
stacks. Thus, we see from the figure that stacks 1 and 2 are allocated 133 cells each and stack
3 gets 134 cells.
1 . . . . . . n = 400
S(1 : n)
Stack 1 Stack 2 Stack 3
B(1) = 0 B(2) = 133 B(3) = 266 B(4) = 400
To initialize the stacks, we set T(i) < - - B(i) , 1 ≤ i ≤ m . Thus the condition T(i) = B(i)
means that the stack I is empty. It is easily verified that the condition T(i) = B(i)
indicates that stack I is full. The figure below shows the three possible states of a stack.
T(1) = 133 T(2) = 204 T(3) = 266
1 . . . . . . n = 400
S(1 : n)
Stack 1 Stack 2 Stack 3
B(1) = 0 B(2) = 133 B(3) = 266 B(4) = 400
Section 4 Page 2 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
An attempt to insert onto a full stack, such as stack 1 in the figure above, results in an
overflow condition; an attempt to delete from an empty stack , such as stack 3 in the future
Procedures to implement the insertion and deletion operations must test for the occurrence of
these conditions. Specifically, when an overflow condition obtains, memory should be
reallocated to make room for the insertion.
The EASY procedure MSPUSH and MSPOP implement the insertion and deletion
operations on stacks represented as described. They are essentially the same as the
corresponding procedures for a sequentially allocated single stack.
procedure MSPUSH( S, B, T, m, n, I, x)
//Inserts x onto stack i //
array S(1 : n), B(1 : m+1), T( 1 : m)
if T(i) = B(i+1) then call MSTACKFUL
T(i) < - - T(i) +1
S(T(i)) < - - x
end MSPUSH
If stack i is full, procedure MSTACKFUL will attempt to reallocate memory to make
insertion onto stack i possible. If the attempt is successful, MSTACKFUL returns control to
MSPUSH for completion of the insertion operation. If reallocation is unsuccessful (because all n
cells are in use), MSTACKFUL returns control to the operating system via a stop
statement. We have deliberately omitted the argument list in MSTACKFUL because the
parameters passed to it will depend on the particular reallocation strategy to be implemented.
We will return to this reallocation issue after considering the deletion operation.
procedure MSPOP (S, B, T, m, n, i, x)
//deletes top element from stack i and stores in x//
array S(1 : n), B(1 : m+1), T( 1 : m)
if T(i) = B(i) then call MSTACKEMPTY
else [ x < - - S( T ( i ) ) ; T( i ) < - - T( i ) - 1 ]
end MSPOP
We will leave MSTACKEMPTY unspecified. The specific action it will take depends
largely on the particular application.
Reallocating Memory at the stack overflow
We will now consider the problem of reallocating memory when a particular stack, say
stack i, overflows. One simple procedure to obtain a free cell for stack i, is to scan the stacks
above (addresswise) stack i, for the nearest stack with available cells, say stack k. Shifting stack
Section 4 Page 3 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
i+1 through stack k one cell upwards will make one cell available to stack i. The following
segment of EASY code will perform this stack [verify]:
//Shift stack elements one cell upward//
for j < - - T(k) to T(i)+1 by –1 do
S(j+1) < - - S(j)
endfor
//Adjust top and base pointes//
for j < - - i+1 to k do
T(j) < - - T(j) + 1
B(j) < - - B(j) + 1
endfor
If all stacks above stack i are also full, then we scan the stacks below for the nearest stack with
free space, say stack k. Shifting stacks k+1 through i one cell downward will make one cell
available to stack i. The following segment of EASY code will perform this task [verify].
//Shifting stack elements one cell downward//
for j < - - B(k+1) +1 to T(i) do
S (j-1) < - - S(j)
endfor
//Adjust top and base pointers //
for j < - - k+1 to i do
B(j) < - - B(j) –1
T(j) < - - T(j) - 1
endfor
If all stacks below stack I are full, then all cells are in use and reallocation is not possible.
MSTACKFUL may then issue a message to this effect and terminate execution of the program.
The problem with this policy of performing a unit shift to obtain one free cell for an
overflowed stack is that successive insertions into such a stack will require repetitive cells to
MSTACKFUL. An alternative approach is to reallocate all of free memory at overflow such that
each stack will receive its share of free cells in proportion to its “need” for space, where “need”
is determined by some appropriate measure. This is the philosophy behind the Garwick’s
algorithm.
Garwick’s technique for reallocating memory at stack overflow may be summarized as follows:
1. Strip all the stacks of unused cells and consider all of these unused cells as comprising
the available for free space.
Section 4 Page 4 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
2. Reallocate one to ten percent of the available space equally among stacks.
3. Reallocate the remaining available space among the stacks in proportion to recent
growth.
For any stack j, recent growth is measured as the difference T(j) – OLDT(j), where OLDT(j)
is the value of T(j) at the end of last reallocation. It is obvious that a negative difference
means that stack j actually decreased in size since last reallocation and positive difference
means that the stack j increased in size since last reallocation. The bigger the (positive)
difference is, the bigger will be stack’s share of the available memory.
Knuth’s implementation of Garwick’s algorithm fixes at 10% of the available space the
portion to be distributed equally among the stacks, with the remaining 90% apportioned
according to recent growth. Standish suggests that in addition to recent growth, stack size
(or commulative growth) can also be used as a measure of “need” in distributing the
remaining 90%. The idea is, the bigger the stack, the more space it needs.
Procedure MSTACKFUL below follows Knuth’s implementation of Garwick’s algorithm.
Incorporating Standish’s suggestion that stack size be also used as a reallocation parameter
is straightforward is left as an exercise.
procedure MSTACKFUL(S, B, T, OLDT, m, n, i)
//Reallocates memory at overflow using Garwick’s algorithm//
array S(1:n), B(1: m+1), T(1:m ), OLDT(1:m), NEWB(1:m), D(1:m)
//Gather relevant information on stack usage //
freecells < -- n; incr < - - 0
T(i) < - - T(i) +1 //preempt one free cell for stack i//
for j < - - to m do //find recent growth for each stack//
freecells <- - freecells – (T(j) – B(j))
if T(j) > OLDT(j) then [ D(j) < - - T(j) - OLDT
incr < - - incr + D(j) ]
else D(j) < - - 0
endfor
//See if there are still available cells//
if freecells < 0 then [output ‘No more available space’; stop]
//Calculate allocation factors//
α < - - 0.10 * freecells/m
β < - - 0.90 * freecells/incr
//Compute new base addresses//
NEWB(1) < - - B(1); σ < - - 0
for j < - - 2 to m do
Section 4 Page 5 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
τ < - - σ + α +β * D (j-1)
NEWB(j) < - - NEWB (j-1) + T(j-1) – B(j-1) + ⎣ τ ⎦ - ⎣ σ⎦
σ <- - τ
endfor
//Revert top pointer of stack I to true value //
T(i) < -- T(i) +1
//Shift stacks whose elements are to be moved down//
for j<-- 2 to m do
if NEWB(j) < B(j) then [δ < - - B(j) – NEWB(j)
if B(j) <> T(j) then [for k < - - B(j) +1 to T(j) do
S(k-δ) < - - S(k)
endfor ]
B(j) < - - NEWB(j)
T(j) < - -T(j) - δ ]
endfor
//Shift stacks whose elements are to be moved up//
for j < - - m to 2 by –1 do
if NEWB(j) > B(j) then [ δ < - - NEWB(j) –B(j)
if B(j) <> T(j) then [for k < - - T(j) to B(j)+1 by –1 do
S(k+δ) < - - S(k)
endfor]
B(j) < - - NEWB(j)
T(j) < - - T(j) + δ ]
endfor
//Update OLDT array in preparation for next reallocation //
for j < - - 1 to m do
OLDT(j) < - - T(j)
endfor
end MSTACKFULL
We now consider an example to illustrate Garwick’s algorithm as implemented by procedure
MSTACKFULL. The figure below shows four stacks coexisting in a vector of size 400. An
attempt to insert an element onto stack 2 using MSPUSH results in an overflow and
MSTACKFULL is invoked.
T(1) = 85 T(2) = 210 T(3) = 240 T(4) = 376
OLDT - - > 96 174 262 344
D--> 0 36 0 32
85 90 30 76
B(1)=0 B(2) = 120 B(3) = 210 B(4) = 300 B(5) = 400
Stacks at overflow condition
Section 4 Page 6 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
1. Gather statistics on stack usage: The stack sizes T(j)-B(j) and the differences T(j) –
OLDT(j) are calculated and indicated in the figure. Note that a negative difference is
replaced by zero.
freecells = 400 – ( 85 + 90 + 1 + 30 + 76) = 118
incr = 36 + 1 + 32 = 39
The +1 in the above computations accounts for the cell that the overflowed stack is currently in
need of. This cell is assumed to be already given to the overflowed stack and already in use.
2. Calculate allocation factors
α = (0.10 * 118 )/4 = 2.95
β = ( 0.90 * 118 )/69 = 1.54
The quantity α represents the number of cells that each stack will get from the 10% of
available space allotted for equal distribution. The quantity β represents the number of cells that
a stack will get per unit increase in stack usage from the remaining 90% of free space. For
example, stack 2 will get, theoretically, 2.95 + 36 * 1.54 cells in all, but stack 1 will get 2.95 cells
only (why?). We say “theoretically” because the a stack may get an integral number of cells
only; how the fractional proportion is handled is described in 3.
3. Compute new base addresses: Memory reallocation involves essentially determining the
new stack boundaries, NEWB(j), j = 2, 3, … , m. These new boundaries are found by allocating
to each stack the number of cells it is currently using plus its share of the free cells as measured
by the parameters α and β. An important aspect of this step is to see to it that the fractional
portions are evenly distributed among the stacks. To this end, we define two real variables σ
and τ, as follows:
σ = free space theoretically allocated to stacks 1, 2, … , j-1
τ = free space theoretically allocated to stacks 1, 2, … , j
Then, we calculate the actual number of (whole), free cells allocated to stack j as the difference
⎣ τ ⎦ - ⎣ σ⎦
Section 4 Page 7 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
The following computations should help clarify the procedure.( Refer to the appropriate segment
of EASY code in MSTACKFULL.)
NEWB(1) = 0; σ = 0
j = 2: τ = 0 + 2.95 + 0(1.54) = 2.95
NEWB(2) = 0 + 85 + ⎣ 2.95 ⎦ - ⎣ 0⎦ = 87
σ = 2.95
j = 3: τ = 2.95 + 2.95 + 37(1.54) = 62.88
NEWB(3) = 87 + 91 + ⎣ 62.88 ⎦ - ⎣ 2.95⎦ = 238
σ = 62.88
j = 4: τ = 62.88 + 2.95 + 0(1.54) = 65.83
NEWB(4) = 238 + 30 + ⎣ 65.83 ⎦ - ⎣ 62.88⎦ = 271
σ = 65.83
As a check, we calculate NEWB(5) to see if it is 400. (This check is not included in procedure
MSTACKFULL.)
τ = 65.83 + 2.95 + 32 (1.54) = 118.06
NEWB(5) = 271 + 76 + ⎣ 118.06⎦ - ⎣ 65.83 ⎦ = 400 (O.K.)
All nodes are accounted for.
4. Shift stacks to their new boundaries: Careful consideration should be given to this step. It
is important that no data item is lost (for instance, overwritten) while the stacks are
moved. Study carefully the segments of EASY code in MSTACKFULL which perform this
shifting of the stacks to their new base addresses. Note that the stacks which are shifted
down are processed from left to right while those which are shifted up are processed
from right to left. The same method applies to the individual data items. Data items that
are moved down are processed in the order of increasing addresses (indices), and data
Section 4 Page 8 of 9
Jennifer Laraya-Llovido
Data Structures & Algorithms
items that are moved up are processed in the order of decreasing addressed. In this
manner, no data is overwritten. (Verify.)
The figure below shows the stacks upon termination of MSTACKFULL. Note that the
vectors T, B, and OLDT have all been updated and that there is now room in stack 2 for the
insertion operation to proceed upon return to MSPUSH.
T(1) = 85 T(2) = 177 T(3) = 268 T(4) = 347
OLDT - - > 85 177 268 347
85 90 30 76
B(1)=0 B(2) = 87 B(3) = 238 B(4) = 271 B(5) = 400
Stacks after memory reallocation
A few comments on Garwick’s technique:
1. If we know beforehand which stack will be the largest, then we should make this the first
stack since stack 1 is never moved during memory reallocation. Likewise, we can initially
allocate more space to this stack, rather than giving equal space to every stack.
2. When a program gets close to utilizing all of the preallocated space in S, it will call
MSTACKFULL more often, and, to make matters worse, MSTACKFULL now takes more
time to execute since more data items need to be shifted around. It is also quite likely
that such a program will eventually need more than what is available, causing
MSTACKFULL to terminate execution. Such futile effort at memory reallocation as
memory runs out can be avoided by coding MSTACKFULL to issue stop command when
freecells becomes less than a specified minimum value (not 0), say minfree, which the
user can specify.
3. While MSTACKFULL is written specifically for stacks, Garwick’s technique can also be
applied to reallocate space for other types of sequentially allocated data structures, such
as queues and sequential tables, or even for combinations of these different types of
structures coexisting in a fixed region of memory.
Section 4 Page 9 of 9
Jennifer Laraya-Llovido
