Chapter 19

Stacks

19.1 Abstract data types

The data types we have looked at so far are all concrete, in the sense that we have completely specified how they are implemented. For example, the Card class represents a card using two integers. As I discussed at the time, that is not the only way to represent a card; there are many alternative implementations.

An abstract data type, or ADT, specifies a set of operations (or methods) and the semantics of the operations (what they do) but it does not not specify the implementation of the operations. That's what makes it abstract.

Why is that useful?

It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time about how the operations are performed.
Since there are usually many ways to implement an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations.
Well-known ADTs, like the Stack ADT in this chapter, are often implemented in standard libraries so they can be written once and used by many programmers.
The operations on ADTs provide a common high-level language for specifying and talking about algorithms.

When we talk about ADTs, we often distinguish the code that uses the ADT, called the client code, from the code that implements the ADT, called provider code because it provides a standard set of services.

19.2 The Stack ADT

In this chapter we will look at one common ADT, the stack. A stack is a collection, meaning that it is a data structure that contains multiple elements. Other collections we have seen include arrays and lists.

As I said, an ADT is defined by the operations you can perform on it. Stacks can perform only the following operations:

constructor: Create a new, empty stack.
push: Add a new item to the stack.
pop: Remove and return an item from the stack. The item that is returned is always the last one that was added.
empty: Check whether the stack is empty.

A stack is sometimes called a "last in, first out," or LIFO data structure, because the last item added is the first to be removed.

19.3 The pstack Class

Although we have the pclasses that provide for a class called pstack that implements the Stack ADT. You should make some effort to keep these two things---the ADT and the pclass implementation---straight.

Then the syntax for constructing a new pstack is

pstack stack;

Initially the stack is empty, as we can confirm with the empty method, which returns a boolean:

cout << stack.empty ();

A stack is a generic data structure, which means that we can add any type of item to it. In the pclass implementation, though, we can only add object types. For our first example, we'll use Node objects, as defined in the previous chapter. Let's start by creating and printing a short list.

LinkedList list;
list.addFirst (3);
list.addFirst (2);
list.addFirst (1);
list.print ();

The output is (1, 2, 3). To put a Node object onto the stack, use the push method:

pstack.push (node);

The following loop traverses the list and pushes all the nodes onto the stack:

for (Node *node = list.head; node != null; node = node->next) {
pstack.push (node);
}

We can remove an element from the stack with the overloaded pop method.

pstack.pop ();
// or
pstack.pop (itemType &item);

The return type from pop is void. That's because the stack implementation doesn't need to keep the item around because it is to be removed from the stack.

The following loop is a common idiom for popping all the elements from a stack, stopping when it is empty:

while (!pstack.empty ()) {
cout << pstack.top() << ' ';
pstack.pop();
}

The output is 3 2 1. In other words, we just used a stack to print the elements of a list backwards! Granted, it's not the standard format for printing a list, but using a stack it was remarkably easy to do.

You should compare this code to the implementations of printBackward in the previous chapter. There is a natural parallel between the recursive version of printBackward and the stack algorithm here. The difference is that printBackward uses the run-time stack to keep track of the nodes while it traverses the list, and then prints them on the way back from the recursion. The stack algorithm does the same thing, just using a pstack object instead of the run-time stack.

19.4 Postfix expressions

In most programming languages, mathematical expressions are written with the operator between the two operands, as in 1+2. This format is called infix. An alternate format used by some calculators is called postfix. In postfix, the operator follows the operands, as in 1 2+.

The reason postfix is sometimes useful is that there is a natural way to evaluate a postfix expression using a stack.

Starting at the beginning of the expression, get one term (operator or operand) at a time.

If the term is an operand, push it on the stack.
If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack.

When we get to the end of the expression, there should be exactly one operand left on the stack. That operand is the result.

As an exercise, apply this algorithm to the expression 1 2 + 3 *.

This example demonstrates one of the advantages of postfix: there is no need to use parentheses to control the order of operations. To get the same result in infix, we would have to write (1 + 2) * 3. As an exercise, write a postfix expression that is equivalent to 1 + 2 * 3?

19.5 Parsing

In order to implement the algorithm from the previous section, we need to be able to traverse a string and break it into operands and operators. This process is an example of parsing

If we were to break the string up into smaller parts, we would need a specific character to use as a boundary between the chucks. A character that marks a boundary is called a delimiter.

So let's quickly build a parsing function that will store the various chunks of a pstring into a pvector<pstring>.

pvector<pstring> parse(pstring string, char delim) {

pvector<pstring> stringParsed;

if (string.length() == 0)
return stringParsed.resize(0);

for (int i = 0, j = 0; i < string.length(); i++)
{
if (string[i] != delim || string[i] != '\n')
stringParsed[j] += string[i];
else
{
cout << stringParsed[j] << endl;
j++;
stringParsed.resize(j+1);
}
}

return stringParsed;
}

The function above accepts a pstring to be parsed and a char to be used as a delimiter, so that whenever the delim character appears in the string, the chunk is saved as a new pstring element in the pvector<pstring>.

Passing a string through the function with a space delimiter would look like this:

pstring string = "Here are four tokens.";

pvector<pstring> = parse(string, ' ');

The output of the parser is:

Here
are
four
tokens.

For parsing expressions, we have the option of specifying additional characters that will be used as delimiters:

bool checkDelim(char ch, pstring delim) {

for (int i = 0; i < delim.length(); i++)
{
if (ch == delim[i])
return true;
}
return false;
}

pvector<pstring> parse(pstring string, pstring delim) {

pvector<pstring> stringParsed;

if (string.length() == 0)
return stringParsed.resize(0);

for (int i = 0, j = 0; i < string.length(); i++)
{
if (!checkDelim(string[i], delim) || string[i] != '\n')
stringParsed[j] += string[i];
else
{
cout << stringParsed[j] << endl;
j++;
stringParsed.resize(j+1);
}
}

return stringParsed;
}

An example of using the above functions can be seen below:Using the above functions would

pstring string = "11 22+33*";
pstring delim = " +-*/";
pvector<pstring> stringParsed = parse(string, delim);

The new function checkDelim checks for whether or not a given char is a delimiter. Now the output is:

11
22
33

19.6 Implementing ADTs

One of the fundamental goals of an ADT is to separate the interests of the provider, who writes the code that implements the ADT, and the client, who uses the ADT. The provider only has to worry about whether the implementation is correct---in accord with the specification of the ADT---and not how it will be used.

Conversely, the client assumes that the implementation of the ADT is correct and doesn't worry about the details. When you are using one of Java's built-in classes, you have the luxury of thinking exclusively as a client.

When you implement an ADT, on the other hand, you also have to write client code to test it. In that case, you sometimes have to think carefully about which role you are playing at a given instant.

In the next few sections we will switch gears and look at one way of implementing the Stack ADT, using an array. Start thinking like a provider.

19.7 Array implementation of the Stack ADT

The instance variables for this implementation is a templated array, which is why we will use the pvector class. It will contain the items on the stack, and an integer index which will keep track of the next available space in the array. Initially, the array is empty and the index is 0.

To add an element to the stack (push), we'll copy a reference to it onto the stack and increment the index. To remove an element (pop) we have to decrement the index first and then copy the element out.

Here is the class definition:

class Stack {

pvector<ITEMTYPE> array;
int index;

public:

Stack () {
array.resize(128);
index = 0;
}
};

The above code contains the type ITEMTYPE which is essentially just a quick way of saying, "INSERT DATATYPE HERE" because pvectors are templated and can handle various types. ITEMTYPE is not in actuality a type, just so you know. In the future, you can replace ITEMTYPE with any other data type, class, or struct.

As usual, once we have chosen the instance variables, it is a mechanical process to write a constructor. For now, the default size is 128 items. Later we will consider better ways of handling this.

Checking for an empty stack is trivial.

bool empty () {
return array.length() == 0;
}

It it important to remember, though, that the number of elements in the stack is not the same as the size of the array. Initially the size is 128, but the number of elements is 0.

The implementations of push and pop follow naturally from the specification.

void push (ITEMTYPE item) {
array[index] = item;
index++;
}

ITEMTYPE pop () {
index--;
return array[index];
}

To test these methods, we can take advantage of the client code we used to exercise pstack.

If everything goes according to plan, the program should work without any additional changes. Again, one of the strengths of using an ADT is that you can change implementations without changing client code.

19.8 Resizing arrays

A weakness of this implementation is that it chooses an arbitrary size for the array when the Stack is created. If the user pushes more than 128 items onto the stack, it will cause an ArrayIndexOutOfBounds exception.

An alternative is to let the client code specify the size of the array. This alleviates the problem, but it requires the client to know ahead of time how many items are needed, and that is not always possible.

A better solution is to check whether the array is full and make it bigger when necessary. Since we have no idea how big the array needs to be, it is a reasonable strategy to start with a small size and increase the size by 1 each time it overflows.

Here's the improved version of push:

void push (ITEMTYPE item) {
if (full()) resize ();

// at this point we can prove that index < array.length

array[index] = item;
index++;
}

Before putting the new item in the array, we check if the array is full. If so, we invoke resize. After the if statement, we know that either (1) there was room in the array, or (2) the array has been resized and there is room. If full and resize are correct, then we can prove that index < array.length, and therefore the next statement cannot cause an exception.

Now all we have to do is implement full and resize.

private:
bool full () {
return index == (array.length()-1);
}

void resize () {
array.resize(array.length()+1);
}

Both methods are declared private, which means that they cannot be invoked from another class, only from within this one. This is acceptable, since there is no reason for client code to use these functions, and desirable, since it enforces the boundary between the implementation and the client.

The implementation of full is trivial; it just checks whether the index has gone beyond the range of valid indices.

The implementation of resize is straightforward, with the caveat that it assumes that the old array is full. In other words, that assumption is a precondition of this method. It is easy to see that this precondition is satisfied, since the only way resize is invoked is if full returns true, which can only happen if index == array.length.

At the end of resize, we replace the old array with the new one (causing the old to be garbage collected). The new array.length is twice as big as the old, and index hasn't changed, so now it must be true that index < array.length. This assertion is a postcondition of resize: something that must be true when the method is complete (as long as its preconditions were satisfied).

Preconditions, postconditions, and invariants are useful tools for analyzing programs and demonstrating their correctness. In this example I have demonstrated a programming style that facilitates program analysis and a style of documentation that helps demonstrate correctness.

19.9 Glossary

abstract data type (ADT): A data type (usually a collection of objects) that is defined by a set of operations, but that can be implemented in a variety of ways.
client: A program that uses an ADT (or the person who wrote the program).
provider: The code that implements an ADT (or the person who wrote it).
private: A Java keyword that indicates that a method or instance variable cannot be accessed from outside the current class definition.
infix: A way of writing mathematical expressions with the operators between the operands.
postfix: A way of writing mathematical expressions with the operators after the operands.
parse: To read a string of characters or tokens and analyze their grammatical structure.
delimiter: A character that is used to separate tokens, like the punctuation in a natural language.
predicate: A mathematical statement that is either true or false.
postcondition: A predicate that must be true at the end of a method (provided that the preconditions were true at the beginning).