The Way of the Java/Stacks
Stacks
[edit | edit source]Abstract data types
[edit | edit source]abstract data typeseeADT ADT encapsulation
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 specify the implementation of the operations. That's what makes it abstract.
Why is that useful?
[edit | edit source]itemize
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.
itemize
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.
client provider
The Stack ADT
[edit | edit source]stack collection ADT!Stack
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 a set of operations. Stacks can perform the following set of operations:
description
[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.
description
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.
The Java Stack Object
[edit | edit source]Stack class!Stack generic data structure data structure!generic
Java provides a built-in object type called Stack that implements the Stack ADT. You should make some effort to keep these two things---the ADT and the Java implementation---straight. Before using the Stack class, we have to import it from java.util.
Then the syntax for constructing a new Stack is
verbatim
Stack stack = new Stack ();
verbatim
Initially the stack is empty, as we can confirm with the empty method, which returns a boolean:
verbatim
System.out.println (stack.empty ());
verbatim
A stack is a generic data structure, which means that we can add any type of item to it. In the Java 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.
verbatim
LinkedList list = new LinkedList (); list.addFirst (3); list.addFirst (2); list.addFirst (1); list.print ();
verbatim
The output is (1, 2, 3). To put a Node object onto the stack, use the push method:
verbatim stack.push (list.head); verbatim
The following loop traverses the list and pushes all the nodes onto the stack:
verbatim
for (Node node = list.head; node != null; node = node.next)
stack.push (node);
verbatim
We can remove an element from the stack with the pop method.
verbatim
Object obj = stack.pop ();
verbatim
The return type from pop is Object! That's because the stack implementation doesn't really know the type of the objects it contains. When we pushed the Node objects, they were automatically converted to Objects. When we get them back from the stack, we have to cast them back to Nodes.
verbatim Node node = (Node) obj; System.out.println (node); verbatim
Unfortunately, the burden falls on the programmer to keep track of the objects in the stack and cast them back to the right type when they are removed. If you try to cast an object to the wrong type, you get a ClassCastException.
The following loop is a common idiom for popping all the elements from a stack, stopping when it is empty:
verbatim
while (!stack.empty ())
Node node = (Node) stack.pop ();
System.out.print (node + " ");
verbatim
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 Stack object instead of the run-time stack.
Wrapper classes
[edit | edit source]wrapper class class!wrapper object type primitive type
For every primitive type in Java, there is a built-in object type called a wrapper class. For example, the wrapper class for int is called Integer; for double it is called Double.
Wrapper classes are useful for several reasons:
itemize
You can instantiate wrapper classes and create objects that contain primitive values. In other words, you can wrap a primitive value up in an object, which is useful if you want to invoke a method that requires an object type.
Each wrapper class contains special values (like the minimum and maximum values for the type), and methods that are useful for converting between types.
itemize
Creating wrapper objects
[edit | edit source]wrapper class!instantiating
The most straightforward way to create a wrapper object is to use its constructor:
verbatim
Integer i = new Integer (17);
Double d = new Double (3.14159);
Character c = new Character ('b');
verbatim
Technically String is not a wrapper class, because there is no corresponding primitive type, but the syntax for creating a String object is the same:
verbatim
String s = new String ("fred");
verbatim
On the other hand, no one ever uses the constructor for String objects, because you can get the same effect with a simple String value:
verbatim
String s = "fred";
verbatim
Creating more wrapper objects
[edit | edit source]Some of the wrapper classes have a second constructor that takes a String as an argument and tries to convert to the appropriate type. For example:
verbatim
Integer i = new Integer ("17");
Double d = new Double ("3.14159");
verbatim
The type conversion process is not very robust. For example, if the Strings are not in the right format, they will cause a NumberFormatException. Any non-numeric character in the String, including a space, will cause the conversion to fail.
NumberFormatException exception!NumberFormat
verbatim
Integer i = new Integer ("17.1"); // WRONG!!
Double d = new Double ("3.1459 "); // WRONG!!
verbatim
It is usually a good idea to check the format of the String before you try to convert it.
Getting the values out
[edit | edit source]wrapper class!extracting value
Java knows how to print wrapper objects, so the easiest way to extract a value is just to print the object:
verbatim
Integer i = new Integer (17); Double d = new Double (3.14159); System.out.println (i); System.out.println (d);
verbatim
Alternatively, you can use the toString method to convert the contents of the wrapper object to a String
verbatim
String istring = i.toString(); String dstring = d.toString();
verbatim
Finally, if you just want to extract the primitive value from the object, there is an object method in each wrapper class that does the job:
verbatim
int iprim = i.intValue (); double dprim = d.doubleValue ();
verbatim
There are also methods for converting wrapper objects into different primitive types. You should check out the documentation for each wrapper class to see what is available.
Useful methods in the wrapper classes
[edit | edit source]wrapper class!methods
As I mentioned, the wrapper classes contain useful methods that pertain to each type. For example, the Character class contains lots of methods for converting characters to upper and lower case, and for checking whether a character is a number, letter, or symbol.
The String class also contains methods for converting to upper and lower case. Keep in mind, though, that they are functions, not modifiers (see Section immutable).
As another example, the Integer class contains methods for interpreting and printing integers in different bases. If you have a String that contains a number in base 6, you can convert to base 10 using parseInt.
verbatim
String base6 = "12345"; int base10 = Integer.parseInt (base6, 6); System.out.println (base10);
verbatim
Since parseInt is a class method, you invoke it by naming the class and the method in dot notation.
Base 6 might not be all that useful, but hexadecimal (base 16) and octal (base 8) are common for computer science related things.
Postfix expressions
[edit | edit source]postfix infix 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.
itemize
Starting at the beginning of the expression, get one term (operator or operand) at a time.
itemize
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.
itemize
When we get to the end of the expression, there should be exactly one operand left on the stack. That operand is the result.
itemize
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?
Parsing
[edit | edit source]parse token delimiter class!StringTokenizer StringTokenizer class
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, and the results---the individual chunks of the string---are called tokens.
Java provides a built-in class called a StringTokenizer that parses strings and breaks them into tokens. To use it, you have to import it from java.util.
In its simplest form, the StringTokenizer uses spaces to mark the boundaries between tokens. A character that marks a boundary is called a delimiter.
We can create a StringTokenizer in the usual way, passing as an argument the string we want to parse.
verbatim
StringTokenizer st = new StringTokenizer ("Here are four tokens.");
verbatim
The following loop is a standard idiom for extracting the tokens from a StringTokenizer.
verbatim
while (st.hasMoreTokens ())
System.out.println (st.nextToken());
verbatim
The output is
verbatim Here are four tokens. verbatim
For parsing expressions, we have the option of specifying additional characters that will be used as delimiters:
verbatim
StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/");
verbatim
The second argument is a String that contains all the characters that will be used as delimiters. Now the output is:
verbatim 11 22 33 verbatim
This succeeds at extracting all the operands but we have lost the operators. Fortunately, there is one more option for StringTokenizers.
verbatim
StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/", true);
verbatim
The third argument says, ``Yes, we would like to treat the delimiters as tokens. Now the output is
verbatim 11
22 + 33
verbatim
This is just the stream of tokens we would like for evaluating this expression.
Implementing ADTs
[edit | edit source]encapsulation ADT
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.
Array implementation of the Stack ADT
[edit | edit source]arraystack
implementation!Stack stack!array implementation
The instance variables for this implementation are an array of Objects, which 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:
verbatim public class Stack
Object[] array; int index;
public Stack ()
this.array = new Object[128];
this.index = 0;
verbatim
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.
verbatim
public boolean empty ()
return index == 0;
verbatim
It is 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.
verbatim
public void push (Object item)
array[index] = item;
index++;
public Object pop ()
index--;
return array[index];
verbatim
To test these methods, we can take advantage of the client code we used to exercise the built-in Stack. All we have to do is comment out the line import java.util.Stack. Then, instead of using the stack implementation from java.util the program will use the implementation we just wrote.
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.
Resizing arrays
[edit | edit source]resize
array!resizing ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds
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.
ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds
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 double it each time it overflows.
Here's the improved version of push:
verbatim
public void push (Object item)
if (full ()) resize ();
// at this point we can prove that index < array.length
array[index] = item;
index++;
verbatim
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.
verbatim
private boolean full ()
return index == array.length;
private void resize ()
Object[] newArray = new Object[array.length * 2];
// we assume that the old array is full
for (int i=0; i<array.length; i++)
newArray[i] = array[i];
array = newArray;
verbatim
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.
method!private private method
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.
precondition postcondition invariant
Glossary
[edit | edit source]ADT client provider wrapper class infix postfix parse token delimiter predicate postcondition
description
[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).
[wrapper class:] One of the Java classes, like Double and Integer that provide objects to contain primitive types, and methods that operate on primitives.
[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.
[token:] A set of characters that are treated as a unit for purposes of parsing, like the words in a natural language.
[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).