$6.2 IMPLEMENTATION VARIATIONS 123 Stack representations Several possible physical representations exist for stacks: Three possible capacity “Push”operation: representations count :count for a stack count representation [count:=x (ARRAY_UP) representation capacity “Push”operation: representation [free]:=x (ARRAY_DOWN) free:=free-1 free representation “Push”operation: item previous new(n） previous item n.item=x n.previous:=last previous item last n (LINKED) previous ifem The figure illustrates three of the most common representations.Each has been given a name for ease of reference: ARRAY UP:represent a stack through an array representation and an integer count whose value ranges from 0(for an empty stack)to capacity,the size of the array representation;stack elements are stored in the array at indices 1 up to count ARRAY DOWN:like ARRAY UP,but with elements stored from the end of the array rather than from the beginning.Here the integer is called free (it is the index of the highest free array position,or 0 if all positions are occupied)and ranges from capacity for an empty stack down to 0.The stack elements are stored in the array at indices capacity down to free +I. LINKED:a linked representation which stores each stack element in a cell with two fields:item representing the element,and previous containing a pointer to the cell containing the previously pushed element.The representation also needs last,a pointer to the cell representing the top.§6.2 IMPLEMENTATION VARIATIONS 123 Stack representations Several possible physical representations exist for stacks: The figure illustrates three of the most common representations. Each has been given a name for ease of reference: • ARRAY_UP: represent a stack through an array representation and an integer count whose value ranges from 0 (for an empty stack) to capacity, the size of the array representation; stack elements are stored in the array at indices 1 up to count. • ARRAY_DOWN: like ARRAY_UP, but with elements stored from the end of the array rather than from the beginning. Here the integer is called free (it is the index of the highest free array position, or 0 if all positions are occupied) and ranges from capacity for an empty stack down to 0. The stack elements are stored in the array at indices capacity down to free + 1. • LINKED: a linked representation which stores each stack element in a cell with two fields: item representing the element, and previous containing a pointer to the cell containing the previously pushed element. The representation also needs last, a pointer to the cell representing the top. Three possible representations for a stack representation (ARRAY_UP) “Push” operation: count := count + 1 count representation [count] := x capacity 1 representation (ARRAY_DOWN) “Push” operation: representation [free] := x free := free – 1 free capacity 1 (LINKED) “Push” operation: new (n) n ● item := x n ● previous := last last := n item item item item previous previous previous previous last