so far we now have been concerned only with the


So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X whose dimension is m. For convenience, we will assume that the indexes of array commence from 1 and end at m. If we contain only 2 stacks to implement in the similar array X, then the solution is simple.

Assume A and B are two stacks. We may define an array stack A with n1 elements and an array stack B along with n2 elements. Overflow might occur when either stacks A contains more than n1 elements or stack B have more than n2 elements.

Assume, rather than that, we define a single array stack along n = n1 + n2 elements for stack A & B together. Let the stack A "grow" to the right, and stack B "grow" to the left. In this case, overflow will takes place only when A and B together have more than n = n1 + n2 elements. It does not matter how several elements individually are there in each stack.

However, in the case of more than 2 stacks, we cannot represent these in the similar way since a one-dimensional array has two fixed points X(1) and X(m) only and each of stack needs a fixed point for its bottom most element. While more than two stacks, say n, are to be sequentially represented, initially we can divide the obtainable memory X(1:m) into n segments. If the sizes of stacks are known, then, we can assign the segments to them in proportion to the probable sizes of the several stacks. If the sizes of the stacks are not known, then, X(1:m) might be divided into equal segments. For each stack i, we will 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 will 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 i+1st stack, then, with roughly equal initial segments we have

BM (i) = TM (i) =   m/n (i - 1), 1 < i < n, as the initial values of BM (i) & TM (i).

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

Figure illustrates an algorithm to add an element to the ith stack. Figure illustrates an algorithm to delete an element from the ith stack.

ADD(i,e)

Step1: if TM (i)=BM (i+1)

Print "Stack is full" and exit

Step2: [Increment the pointer value through one]

TM (i)← TM (i)+1

X(TM (i))← e

Step3: Exit

//remove the topmost elements of stack i.

DELETE(i,e)

Step1: if TM (i)=BM (i)

Print "Stack empty" and exit

Step2: [remove the topmost item]

e←X(TM (i))

TM (i)←TM(i)-1

Step3: Exit

Request for Solution File

Ask an Expert for Answer!!
Computer Engineering: so far we now have been concerned only with the
Reference No:- TGS0263933

Expected delivery within 24 Hours