CSC236 Data Structures

Stacks

A stack is a container: it stores a set of objects, which are accessed in a specific way.
All elements in the stack are the same type.
A stack is a LIFO (last in first out) container. The objects in the stack are retrieved in the opposite of the order in which they were inserted. Stacks are used when there is a need to backtrack or reverse the order of items.
The stack data structure is similar to a stack of physical objects where you add an item to the top of the stack and remove an item from the top of the stack. It is not possible to add or remove except from the top. Some examples:

a stack of dishes or trays at a buffet: you can only remove the item at the top of the stack
a line of cars parked in a long driveway: the last car that parked is the first to exit, and so on

A stack is used in function calls, where the order of calls is the opposite of the order of returns.
The insert method for a stack is called push.
The delete method for a stack is called pop.
The end of the stack that is used for pushing and popping is called the top.
Many stack implementations also have a method that displays the item at the top of the stack.

Example

Suppose we have a stack of Strings. The following shows some stack calls. Draw a picture of the result after the first 4 statements, after the 6th statement, and then after the last statement.

   st.push("blue");
   st.push("red");
   st.push("green");
   str = st.top();
   st.pop();
   st.push("black");
   st.pop();
   st.pop();
   str = st.top();

Perspectives

We will study each of our data structures from different perspectives:

Abstract: This is the design perspective, which is concerned with what the ADT models, what is the interface, what are its responsibilities.
Application: This is the perspective of the application programmer who uses the ADT. We call the application the client or client code. In this perspective only the interface is important.
Implementation: This is the perspective of the programmer who designs and develops the internal representation of the class, and writes the methods to provide the public interface required for the ADT.

Stack Interface

We use the Java interface construct to specify the public interface of our data structures. Like the other data structures we will study, a stack is a collection, that is, an object that contains other objects. We use the Java generic feature to create an ADT that can contain any type of object needed by the client code.

We have discussed the main methods of the stack: push, pop, and top. You can't push onto a stack if there is no more room to add an element. You can't pop or look at the top if there's nothing in the stack. Our stack methods will throw exceptions in these cases.

The Stack interface from our textbook.

Stack Implementation: Array

To implement the stack we need to be able to store a collection of elements. The elements need to be kept in order so that we can access them according to the specification of the stack (LIFO).

One way to implement the stack is to use an array. Think about what is the best way to do so. Remember that all additions (push) and all removals (pops) are done at the top of the stack. Where in the array should the top of the stack be? This should be decided by what will result in the most efficient implementation of the stack operations.

   st.push("blue");
   st.push("red");
   st.push("green");
   st.push("yellow");

You can see that the best way to store the stack is to make location [0] the bottom of the stack. We need to keep track of where the top is located; for this we use another field, called topIndex. What is topIndex for the stack above? What happens to topIndex and the array after each of the following operations? Draw the array and show the new value for topIndex after each statement.

   st.pop();
   st.push("purple");
   st.pop();
   st.pop();
   st.push("red");
   st.push("green");
   st.push("yellow");

Suppose we call the array elements. How can we tell when the stack is full? What is the value of topIndex? How can we tell when the stack is empty? (What happens to topIndex if we pop out everything?) Does this help us decide how to initialize topIndex?

One more thing we need to decide is the type of the array. We need to be able to have stacks of many different type. Each stack is created to hold some type of object, determined by the needs of the application. We could make an array of Objects, but then every time we remove something we have to cast it back to it's actual class. Another option is to have an array of objects that implement an interface, like the example of Sortable objects. But this makes it awkward to use existing classes like String. Instead we will use generics. A generic class has a type parameter which will be instantiated when an object is created. So our stack class will be defined as:

public class ArrayBoundedStack<T> implements StackInterface<T> {
   protected final int DEFCAP = 100;
   protected T[] elements;
   protected int topIndex = -1;
   ...
}

When we create a stack we do it like this:

   ArrayBoundedStack<String> strStack = new ArrayBoundedStack<String>();
   ArrayBoundedStack<Circle> cStack = new ArrayBoundedStack<Circle>();

The constructor will create the array. We will have two constructors, one will create an array of the default size (100), one will have a parm for the size of the array. The obvious thing to write is:

   elements = new T[DEFCAP];
        or
   elements = new T[maxSize];

But Java doesn't allow the creation of generic arrays. Instead we have to create an array of Objects, and then cast it to an array of type T:

   elements = (T[]) new Object[DEFCAP];
        or
   elements = (T[]) new Object[maxSize];

Now we are ready to write the code for the Stack class.

The ArrayBoundedStack class from our textbook.