124 ABSTRACT DATA TYPES $6.2 Next to each representation,the figure shows a program extract (in Pascal-like notation)giving the corresponding implementation for a basic stack operation:pushing an element x onto the top. For the array representations,ARRAY_UP and ARRAY_DOWN,the instructions increase or decrease the top indicator (count or free)and assign x to the corresponding array element.Since these representations support stacks of at most capacity elements, robust implementations should include guards of the respective forms if count capacity then .. if free >0 then... which the figure omits for simplicity. For LINKED,the linked representation,pushing an element requires four operations: create a new cell n(done here with Pascal's new procedure,which allocates space for a new object);assign x to the new cell's ifem field;chain the new cell to the earlier stack top by assigning to its previous field the current value of last;and update last so that it will now be attached to the newly created cell. Although these are the most frequently used stack representations,many others exist. For example if you need two stacks of elements of the same type,and have only limited space available,you may rely on a single array with two integer top markers,count as in ARRAY_UP and free as in ARRAY_DOWN;one of the stacks will grow up and the other will grow down.The representation is full if and only if count=free. capacity Head-to-head Stack 2 representation for two stacks free CO111 representation Stack 1 The advantage,of course,is to lessen the risk of running out of space:with two arrays of capacity n representing stacks under ARRAY UP or ARRAY DOWN,you exhaust the available space whenever either stack reaches n elements;with a single array of size 2n holding two head-to-head stacks,you run out when the combined size reaches 2n,a less likely occurrence if the two stacks grow independently.(For any variable values p and g, max (p+q)<max (p)+max (g).) Each of these and other possible representations is useful in some cases.Choosing one of them as"the"definition of stacks would be a typical case ofoverspecification.Why should we consider ARRAY UP,for example,more representative than LINKED?The most visible properties of ARRAY_UP-the array,the integer count,the upper bound-are irrelevant to an understanding of the underlying structure.124 ABSTRACT DATA TYPES §6.2 Next to each representation, the figure shows a program extract (in Pascal-like notation) giving the corresponding implementation for a basic stack operation: pushing an element x onto the top. For the array representations, ARRAY_UP and ARRAY_DOWN, the instructions increase or decrease the top indicator (count or free) and assign x to the corresponding array element. Since these representations support stacks of at most capacity elements, robust implementations should include guards of the respective forms if count < capacity then … if free > 0 then … which the figure omits for simplicity. For LINKED, the linked representation, pushing an element requires four operations: create a new cell n (done here with Pascal’s new procedure, which allocates space for a new object); assign x to the new cell’s item field; chain the new cell to the earlier stack top by assigning to its previous field the current value of last; and update last so that it will now be attached to the newly created cell. Although these are the most frequently used stack representations, many others exist. For example if you need two stacks of elements of the same type, and have only limited space available, you may rely on a single array with two integer top markers, count as in ARRAY_UP and free as in ARRAY_DOWN; one of the stacks will grow up and the other will grow down. The representation is full if and only if count = free. The advantage, of course, is to lessen the risk of running out of space: with two arrays of capacity n representing stacks under ARRAY_UP or ARRAY_DOWN, you exhaust the available space whenever either stack reaches n elements; with a single array of size 2n holding two head-to-head stacks, you run out when the combined size reaches 2n, a less likely occurrence if the two stacks grow independently. (For any variable values p and q, max (p+q) ≤ max (p) + max (q).) Each of these and other possible representations is useful in some cases. Choosing one of them as “the” definition of stacks would be a typical case of overspecification. Why should we consider ARRAY_UP, for example, more representative than LINKED? The most visible properties of ARRAY_UP — the array, the integer count, the upper bound — are irrelevant to an understanding of the underlying structure. Head-to-head representation for two stacks representation count 1 capacity free Stack 2 Stack 1