Earlier in this chapter the notion of a stack was introduced and used in the nonrecursive implementations of towers and next. Stacks are useful in situations requiring the retention and recall of information in a specific order梟amely, when information is removed in a last-in, first-out order (LIFO for short). Removing tennis balls from a can is LIFO. In programming, stacks are useful when a program must postpone obligations, which must later be fulfilled in reverse order from that in which they were incurred.
Information is kept in order in a stack. Additional information may be inserted on the stack, but only at the front or top end. Thus the information at the top of the stack always corresponds to the most recently incurred obligation. Information may be recalled from the stack, but only by removing the current top piece of information. The stack acts like a pile of playing cards to which we can only add a card at the top and from which we can only remove the top card. Of course, this is not what is meant by a "stacked deck."
The stack, with the operations of front-end insertion and deletion, initialization, and an empty check, is a data abstraction. Stacks used to be called "pushdown stacks"; insertion of data onto the stack was referred to as "pushing" the stack, and deleting data was known as "popping" the stack. So far we have written programs that treat the stack with the four operations as a data abstraction. Stacks will be used frequently in algorithms developed throughout the rest of this book, and it is now time to consider this implementation. Of the many implementations possible for the stack, the following subsections illustrate the three most straightforward.
4.5.1 Array Implementation of a Stack
4.5.2 List Implementation of the Stack with an Array of Records
4.5.3 List Implementation of the Stack with Records in Dynamic Memory