We know that a data structure is a collection of related information. When a data structure has a fixed size once it’s created we call it a static data structure; e.g., Java arrays. When a data structure has the ability to grow and shrink after it’s instantiated it is referred to as a dynamic data structure; the ArrayList is a good example of this. Although the ArrayList uses an array to store data internally, it can “expand” as needed to accommodate more elements.
The ArrayList class is a good example of something else called an abstract data type. An abstract data type (or ADT) hides the internal details of how data is stored and managed, and provides some convenient public methods to allow outside code to manipulate the data in controlled ways — this is related to the goal of encapsulation. In the case of an ArrayList, we don’t need to be concerned with the fact that it uses an array internally or how it does this. All we need to know are what public methods are available for us to use.
The Concept of a Stack
I’m sure you’ve been to a cafeteria where the plates are stacked on top of each other. As plates are washed they are placed on the top of the stack, and if you need a plate you take one off the top (only). People would stare if you tried to take a plate from the bottom or middle of the stack, and it would not make sense for freshly washed plates to be added to the middle or bottom of the stack!
In computer science, a stack is an abstract data type that holds items in a particular sequence. Because you can only add or remove items from the top of the stack, we say that it is processed in a Last-In, First-Out (LIFO) manner. In other words, the last element put on the stack will be the first one that gets removed. If you think about it, this means that elements are removed from a stack in the reverse order of their placement on it. In fact, one of the main uses of a stack is to reverse the order of something (e.g., an undo operation).
Stack ADT Interface
Today we are going to build a stack ADT that uses an array internally to store data. Since we’re using a fixed-size array, this will be a static data structure. The classic stack data structure is expected to support the following 6 operations:
- To place (“push“) an element on the top of the stack (must not be full).
- To remove (“pop“) an element from the top of the stack (must not be empty).
- To look (“peek“) at the top element, but not remove it.
- To check if the stack is empty (“isEmpty“).
- To check how many elements are in the stack (“size“).
- To clear all elements from the stack (“clear“).
We’ll begin by defining an interface for our stack ADT. An interface is a group of related methods with empty bodies:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public interface StackADT<T> { // Adds one element to the top of the stack. public void push(T element); // Removes and returns a reference to the top element from the stack. public T pop(); // Returns a reference to the top element, without removing it from the stack. public T peek(); // Returns true if the stack contains no elements, false otherwise. public boolean isEmpty(); // Returns the number of elements in the stack. public int size(); // Clears all elements from the stack public void clear(); // Returns a String representation of the stack. public String toString(); } |
In the code above we are simply declaring the methods that a stack ADT should support. This looks a lot like an abstract class containing all abstract methods! However, the abstract keyword is not required with interfaces because it’s considered redundant. While not a classic stack operation, I’ve specified a toString() method because it can be useful for debugging purposes. Finally, you’ll note that we’re going to use generic types <T> such that our stack can store any kind of object. We’ve seen this before with the ArrayList collection.
The StaticStack Class
Like an abstract class, an interface cannot be instantiated, but it’s also not inherited from! Instead, an interface is implemented. When a class implements an interface, all methods defined by that interface must be overridden or the class will not compile. It is good programming practice to include the @Override annotation when implementing interface methods.
Now, let’s implement this interface to create a StaticStack class that internally uses an array to store elements.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
class StaticStack<T> implements StackADT<T> { private int top; private T[] stackArray; private final int MAX_SIZE; // Creates an empty stack using the specified capacity. public StaticStack(int maxSize) { MAX_SIZE = maxSize; clear(); } // Adds the specified element on the top of the stack, or does nothing if full. @Override public void push(T element) { if ( top < stackArray.length-1 ) { top++; stackArray[top] = element; } } // Removes element on the top of the stack and returns a reference to it, or null (if empty). @Override public T pop() { if ( isEmpty() ) return null; T result = stackArray[top]; stackArray[top] = null; top--; return result; } // Returns a reference to the element on the top of the stack, or null (if empty). @Override public T peek() { if ( isEmpty() ) return null; return stackArray[top]; } // Returns true if the stack contains no elements, false otherwise. @Override public boolean isEmpty() { return (top == -1); } // Returns the number of elements in the stack. @Override public int size() { return (top+1); } // Clears all elements from the stack @Override @SuppressWarnings("unchecked") // Don't show warning, line 59 is safe! public void clear() { top = -1; stackArray = (T[])(new Object[MAX_SIZE]); } // Returns a String representation of the stack. @Override public String toString() { String result = "Stack Contains: "; for (T element : stackArray) { result += "["+element+"] "; } return result; } } |
Line 1 defines this class as a generic class <T> that implements the interface StackADT. The “T” that you see throughout the code will be replaced by a particular data type when we instantiate a StaticStack. The StackADT interface defined what methods we need to provide, but how (e.g., using a fixed-size array) we implement them is up to us.
In this case I’m using a fixed-size array, with an index called top to keep track of which element is the current top of the stack (or -1 meaning the stack is empty). Note that the bottom of the stack is always at index 0 and the stack grows down (i.e., the top index is incremented) as elements are pushed on. This implementation detail makes no difference to someone using our StaticStack class.
Line 59 is also interesting. Here we are instantiating an array of Object references and then explicitly casting it as an array of our generic type. This will generate a compile-time warning for an unchecked type conversion because the Java compiler cannot guarantee the type safety of this cast. This is a known and well-documented annoyance with Java generics. To turn off these compiler warnings for a single method, you can add the following annotation before the method signature.
|
1 |
@SuppressWarnings("unchecked") |
The rest of the code should be pretty straightforward for you at this point. Just remember that wherever you see a T it will be replaced with an reference type that a user specifies when they instantiate a StaticStack.
Testing the Stack
Finally, let’s create a test class to demonstrate how our StaticStack works:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.Scanner; class StaticStackTest { public static void main(String[] args) { String command; Scanner keyInput = new Scanner(System.in); // Define a static stack with a fixed size of 3. StaticStack<Integer> myStack = new StaticStack<>(3); while (true) { System.out.printf( "\nStack Empty? %b Stack Size? %d %s\n", myStack.isEmpty(), myStack.size(), myStack ); System.out.print( "Command >" ); command = keyInput.nextLine().toLowerCase().trim(); if ( command.startsWith( "push" ) ) { int value = Integer.parseInt( command.substring(5) ); myStack.push(value); System.out.println( "Pushed: " + value ); } else if ( command.startsWith( "pop" ) ) { System.out.println( "Popped: " + myStack.pop() ); } else if ( command.startsWith( "peek" ) ) { System.out.println( "Peeked: " + myStack.peek() ); } else if ( command.startsWith( "clear" ) ) { myStack.clear(); System.out.println( "Cleared!" ); } else if ( command.startsWith( "quit" ) ) { System.out.println( "Bye-Bye!"); break; } else { System.out.println( "I don't understand \""+command+"\". Please use: push #, pop, peek, clear, or quit" ); } } } } |
Line 8 is the most critical here. It instantiates a StaticStack object that will handle Integer objects. You can specify any reference type here and our StaticStack will be able to accommodate objects of that type. This is the power of generic classes!
You Try!
- Carefully read the code for the StackADT and StaticStack class. Sketch out an array on paper and trace through the StaticStack methods to better understand how they work. When an item is pushed onto the top of the StaticStack, where is it actually added in the array? As the designer of the StaticStack class why does this make sense? As a user of the StaticStack class does this matter?
- Using the StaticStack class to keep track of String objects, write a program that asks a user to enter a string, and displays each character of the string in reverse order. Don’t forget to allocate enough elements in the StaticStack to accommodate all of the characters in the string – it would make sense to instantiate the StaticStack after you get the input string.