24 68 CHAPTER 2 The Stack The stack is one of the most useful concepts in computer science. In this chapter, we shall examine this deceptively simple data structure and see why it plays such a promi- nent role in the areas of programming and programming languages. We shall define the abstract concept of a stack and show how it can be made into a concrete and valuable tool in problem solving. DEFINITION AND EXAMPLES A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the zop of the stack. We can picture astack as in Figure 2.1.1. Unlike an array, the definition of a stack provides for the insertion and deletion of items, and thus a stack is a dynamic, constantly changing object. The question there- fore arises, how does a stack change? The definition specifies that a single end of the stack is designated as the stack top. New items may be put on top of the stack (in which case the top of the stack moves upwards to correspond to the new highest element) or items which are at the top of the stack may be removed (in which case the top of the stack moves downwards to correspond to the new highest element). To answer the question “which way is up?” we must decide which end of the stack is designated as its afelalola|s Stack containing2.1. Definition and Examples 69 top—that is, at which end items are added or deleted. By drawing Figure 2.1.1 so that F is physically higher on the page than all the other items in the stack, we imply that Fis the current top element of the stack. If any new items are added to the stack, they are placed on top of F, and if any items are deleted, F is the first to be deleted. This is also indicated by the vertical lines that extend past the items on the stack in the direction of the stack top. Figure 2.1.2 is a motion picture of a stack as it expands and shrinks with the pas- sage of time. Figure 2.1.2(a) shows the stack as it exists at the time of the snapshot in Figure 2.1.1. In Figure 2.1.2(b), item G is added to the stack. According to the defini- tion, there is only one place on the stack where it can be placed—the top. The top ele~ ment on the stack is now G, As the motion picture progresses through frames c, d, and e,items H, I, and J are successively added onto the stack. Note that the last item insert- ed (in this case J) is at the top of the stack. Beginning with frame f, however, the stack begins to shrink, as first J, then I, H, G, and F are successively removed, At each point, the top element is removed, since a deletion can be made only from the top. Item G could not be removed from the stack before items /, J, and H! were gone. This illustrates the most important attribute of a stack, that the last element inserted is the first ele- ment deleted, Thus J is deleted before / because J was inserted after I. For this reason a stack is sometimes called a last-in, first-out (or LIFO) list. ‘Between frames j and k, the stack has stopped shrinking and begins to expand again as item K is added. However, this expansion is short-lived, as the stack then shrinks to only three items in frame n. Note that there is no way to distinguish between frame a and frame i by looking at the stack’s state at the two instances. In both cases, the stack contains the identical items in the same order and has the same stack top. No record is kept on the stack of the fact that four items had been pushed and popped in the meantime. Similarly, there is no way to distinguish between frames d and f or j and |. If a record is needed of the intermediate items having been on the stack, it must be kept elsewhere; it does not exist within the stack itself. In fact, we have actually taken an extended view of what is really observed in a stack. The true picture of a stack is given by a view from the top looking down, rather than from a side looking in. Thus, in Figure 2.1.2, there is no perceptible difference be- tween frames h and o. In each case the element at the top is G. While the stack at h and the stack at o are not equal, the only way to determine this is to remove all the ele~ ments on both stacks and compare them individually. While we have been looking at cross-sections of stacks to make our understanding clearer, it should be noted that this is an added liberty and there is no real provision for taking such a picture. Primitive Operations ‘The two changes which can be made to a stack are given special names. When an item is added to a stack, it is pushed onto the stack, and when an item is removed, it is popped from the stack. Given a stack s, and an item i, performing the operation sipush(i) adds the item / to the top of stack s. Similarly, the operation spop() removes the top element and returns it as a method value. Thus the assignment operation i= s.pop0: removes the element at the top of s and assigns its value to i.pes e jo einpid uonoW 717 FNL © @ ® 0 Oo oO ® 8 © © © @ ¥ v ¥ ¥ v v vo v ¥ v Vv v v v a g a a @ a q a a a a © a a 2 2 2 2 a 2 2 2 2 2 2 2 3 2 D he] a a a Cc @ a a @ @ @ a a a z z a a z a a a a Y a a af a a Z a a ad |e dor a 2. 3 a a a D || H H H H H te! 7 I T he t «| 70