Wikibooks

The Way of the Java/Stacks

< The Way of the Java
This page may need to be reviewed for quality.

Stacks

edit

Abstract data types

edit 
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

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 
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 
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 
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 
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

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 
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 
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 
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 
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 
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

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

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 
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).

Retrieved from "https://en.wikibooks.org/wiki/The_Way_of_the_Java/Stacks"