4.2 Pushdown Stack ADT | Algorithms in Java, Parts 1-4 (3rd Edition) (Pts.1-4)

Of the data types that support insert and remove for collections of items, the most important is called the pushdown stack.

A stack operates somewhat like a busy professor's "in" box: work piles up in a stack, and whenever the professor has a chance to get some work done, it comes off the top. A student's paper might well get stuck at the bottom of the stack for a day or two, but a conscientious professor might manage to get the stack emptied at the end of the week. As we shall see, computer programs are naturally organized in this way. They frequently postpone some tasks while doing others; moreover, they frequently need to return to the most recently postponed task first. Thus, pushdown stacks appear as the fundamental data structure in many computational applications.

Program 4.4 Pushdown-stack ADT interface

Using the same convention that we used in Program 4.3, we define an ADT for a pushdown stack that contains integers with method signatures, so that the stack representation and any other implementationdependent code can be kept private in implementations, thereby allowing us to change implementations without changing client code. The parameter to the Stack constructor specifies the maximum number of integers expected on the stack.

 class intStack // ADT interface    { // implementations and private members hidden      intStack(int)      int empty()      void push(int)      int pop()    }

Definition 4.2 A pushdown stack is an ADT that comprises two basic operations: insert (push) a new item, and remove (pop) the item that was most recently inserted.

That is, when we speak of a pushdown stack ADT, we are referring to both a description of the push and pop operations that is sufficiently well specified that a client program can make use of them as well as to some implementation of the operations enforcing the rule that characterizes a pushdown stack: items are removed according to a last-in, first-out (LIFO) discipline.

Figure 4.1 shows how a sample stack evolves through a series of push and pop operations. Each push increases the size of the stack by 1, and each pop decreases the size of the stack by 1. In the figure, the items in the stack are listed in the order that they are put on the stack so that it is clear that the rightmost item in the list is the one at the top of the stack the item that is to be returned if the next operation is pop. In an implementation, we are free to organize the items any way that we want, as long as we allow clients to maintain the illusion that the items are organized in this way.

Figure 4.1. Pushdown stack (LIFO queue) example

This list shows the result of the sequence of operations in the left column (top to bottom), where a letter denotes push and an asterisk denotes pop. Each line displays the operation, the letter popped for pop operations, and the contents of the stack after the operation, in order from least recently inserted to most recently inserted, left to right.

graphics/04fig01.gif

As we have discussed, in order to write programs that use the pushdown stack abstraction, we need first to define the interface. To this end, our convention is to declare a collection of public methods to be used in class implementations, as illustrated in Program 4.4. We keep all other class members private, so that Java will ensure that these methods are the only connection between client programs and implementations. This mechanism allows us to write programs that use these abstract operations. To enforce the abstraction, we use the class mechanism to hide the data structure and the implementation from the client. In Section 4.3, we consider examples of client programs that use the stack abstraction; in Section 4.4, we consider implementations.

The stack ADT interface of Program 4.4 defines stacks of integers, when we would like to be able to work with stacks of items of any type. Indeed, our example in Figure 4.1 uses stacks of characters, which would require that we define an interface like Program 4.4 for charStack classes where the parameter to push and the return value from pop are of type char. In order to separate our discussion of implementing and using stacks from our discussion of doing so in a generic way, we will defer discussion of the latter to Section 4.5.

In an ADT, the purpose of the interface is to serve as a contract between client and implementation. If both client and implementation use methods with the signatures in the interface, then we know that the calls in the client program and the method definitions in the implementation match. The interface otherwise contains no information about how the methods are to be implemented, or even how they are to behave. How can we explain what a stack is to a client program? For simple structures like stacks, one possibility is to exhibit the code, but this solution is clearly not effective in general. Most often, programmers resort to English-language descriptions in documentation that accompanies the code.

A rigorous treatment of this situation requires a full description, in some formal mathematical notation, of how the methods are supposed to behave. Such a description is sometimes called a specification. Developing a specification is generally a challenging task. It has to describe any program that implements the methods in a mathematical metalanguage, whereas we are used to specifying the behavior of methods with code written in a programming language. In practice, we describe behavior in English-language descriptions. Before getting drawn further into epistemological issues, we move on. In this book, we give detailed examples, English-language descriptions, and multiple implementations for most of the ADTs that we consider.

To emphasize that our specification of the pushdown stack ADT is sufficient information for us to write meaningful client programs, in Section 4.3 we consider (before thinking about any implementation) two client programs that use pushdown stacks.

Exercises

4.5 A letter means push and an asterisk means pop in the sequence
E A S * Y * Q U E * * * S T * * * I O * N * * *.

Give the sequence of values returned by the pop operations.

4.6 Using the conventions of Exercise 4.5, give a way to insert asterisks in the sequence E A S Y so that the sequence of values returned by the pop operations is (i) E A S Y ; (ii) Y S A E ; (iii) A S Y E ; (iv) A Y E S ; or, in each instance, prove that no such sequence exists.

4.7 Given two sequences, give an algorithm for determining whether or not asterisks can be added to make the first produce the second, when interpreted as a sequence of stack operations in the sense of Exercise 4.6.

Top