This is a program I wrote in Data Structures last semester that takes a string as its input, pushes it onto a stack, and then returns the string reversed. It contains a few bits of code rather than just a single, monolithic application like you’ve seen me write so far. So if you want to compile this, you will need all the pieces.
Once you’ve saved all four files in the same directory, you can compile SentenceReverser.java (which will, in turn, call the other three to be compiled.) But first, let’s look at the main program:
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 | // -------------------------------------------------------- // Programmer: Jonathan Landrum // Date: 6 October 2011 // Class: CSC 216 // -------------------------------------------------------- // Program: SentenceReverser.java // Purpose: Takes a sentence from the user and reverses // the order using a stack. // Assumptions: None. // -------------------------------------------------------- import java.util.Scanner; public class SentenceReverser { // ------------------------------------------------ // Main: // Introduces the program and takes input from // the user. // ------------------------------------------------ public static void main (String[] args) { // ------------------ // Variables // ------------------ Scanner scan = new Scanner(System.in); String input = ""; int stackSize; // ------------------ // Introduction // ------------------ System.out.println ("----------------------------------------"); System.out.println ("- JAVA STRING REVERSER -"); System.out.println ("----------------------------------------"); System.out.println (); System.out.println ("Input a line of text, and this program"); System.out.println ("will reverse it: "); System.out.println (); input = scan.nextLine(); System.out.println (); // ------------------ // Do all the things // ------------------ stackSize = input.length(); ArrayStack stack = new ArrayStack(stackSize); // Reverses the input for (int i = 0; i < input.length(); i++) { char c = input.charAt(i); stack.push(c); } // End reversal // Prints the output while (!stack.isEmpty()) { Object c = stack.pop(); System.out.print (c); } // End printout } // End main } // End SentenceReverser |
This program takes a string from the user, and then tries to build a stack object to push the data to. It uses ArrayStack.java to build the stack. A stack is like any stack in nature: Last in, First out. Like a stack of plates in your cupboard, the ones just washed are the ones that will be used next. Likewise, we are taking our string and pushing it onto a stack, so the last item in will be the last character the user typed. And that will, consequently, be the first item popped off the stack (since it’s on top). Thus, a sentence reverser. Here’s ArrayStack.java:
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 | public class ArrayStack<T> implements StackADT<T> { // ------------------ // Variables // ------------------ private final int DEFAULT_CAPACITY = 100; private int top; private T[] stack; // ------------------ // Constructors // ------------------ public ArrayStack() { top = 0; stack = (T[])(new Object[DEFAULT_CAPACITY]); } // End ArrayStack default constructor public ArrayStack (int initialCapacity) { top = 0; stack = (T[])(new Object[initialCapacity]); } // End ArrayStack modified constructor // ------------------ // Methods // ------------------ public void push (T element) { if (size() == stack.length) expandCapacity(); stack[top] = element; top++; } // End push public T pop() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("Stack"); top--; T result = stack[top]; stack[top] = null; return result; } // End pop public T peek() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("Stack"); return stack[top-1]; } // End peek public boolean isEmpty() { return (top == 0); } // End isEmpty public int size() { return top; } // End size public String toString() { String result = ""; for (int scan=0; scan < top; scan++) result = result + stack[scan].toString() + "\n"; return result; } // End toString private void expandCapacity() { T[] larger = (T[])(new Object[stack.length*2]); for (int index=0; index < stack.length; index++) larger[index] = stack[index]; stack = larger; } // End expandCapacity } // End ArrayStack |
It simply contains all the normal methods of a stack: A constructor (in this case, two, so we can specify how large of a stack we want, or if that doesn’t matter, just build us one of the default size), push (to get items on the stack), pop (to get items off of the stack), peek (to see what’s on top of the stack), isEmpty (to test if the stack is empty or not), size (to see how many items are on the stack), toString (to make a printout of the stack), and expandCapacity (to grow the stack as needed).
A couple things you may have noticed: First, pop() and peek() throw an Empty Collection Exception, which you have to define:
1 2 3 4 5 | public class EmptyCollectionException extends RuntimeException { public EmptyCollectionException (String collection) { super ("The " + collection + " is empty."); } // End constructor } // End EmptyCollectionException |
Second, you will notice in the header of our stack class that it implements StackADT. That is the abstract data type (ADT) for a generic stack, basically giving a blueprint for how to make a stack. This ADT can be used to build all kinds of stacks. In this case, we’ve built an array stack (hence the name “ArrayStack.java”). Here’s StackADT.java:
1 2 3 4 5 6 7 8 | public interface StackADT<T> { public void push (T element); public T pop(); public T peek(); public boolean isEmpty(); public int size(); public String toString(); } // End StackADT |
This is simply a blueprint or map to making a Stack. Once you have all four of these files compiled, you can use the Sentence Reverser program to do whatever you want that uses a stack. This is a nice starting point for 1.) Writing programs that use other programs as part of their normal operation, and 2.) Writing data structures to maintain and manipulate data sets.
~Jonathan