Now that we have clearly defined the stack as an abstract data type, we will turn our attention to using Java to implement the stack. Recall that when we give an abstract data type a physical implementation, we refer to the implementation as a data structure.
As we described in Section 1.15, in Java, as in any object-oriented programming language, the implementation of choice for an abstract data type such as a stack is the creation of a new class. The stack operations are implemented as methods. Further, to implement a stack, which is a collection of elements, it makes sense to utilize the power and simplicity of the collections provided by Java. We will use an ArrayList.
Recall that the ArrayList class in Java provides an ordered collection mechanism and a set of methods. For example, if we have the list [2, 5, 3, 6, 7, 4], we need only to decide which end of the list will be considered the top of the stack and which will be the bottom (also referred to as the base of the stack). Once that decision is made, the operations can be implemented using the list methods such as add and remove.
The following stack implementation (Listing 3.5.1) assumes that the end of the list will hold the top element of the stack. As the stack grows (as push operations occur), new items will be added on the end of the list. pop operations will manipulate that same end.
import java.util.ArrayList;
import java.util.NoSuchElementException;
class Stack<T> {
/*
* The top of the stack is at the end
* of the ArrayList.
*/
ArrayList<T> items;
/*
* Create a new stack
*/
public Stack() {
this.items = new ArrayList<T>();
}
/*
* Returns true if there are no items on the stack;
* false otherwise.
*/
public boolean isEmpty() {
return (this.items.isEmpty());
}
/*
* Pushes given item on the top of the stack
*/
public void push(T item) {
this.items.add(item);
}
/*
* Removes the item on top of the stack and returns it.
* If the stack is empty, throws an exception.
*/
public T pop() {
if (this.isEmpty()) {
throw new NoSuchElementException("Stack is empty.");
}
return this.items.remove(items.size() - 1);
}
/*
* Returns the item on top of the stack without removing it.
* If the stack is empty, throws an exception.
*/
public T peek() {
if (this.isEmpty()) {
throw new NoSuchElementException("Stack is empty.");
}
return this.items.get(items.size() - 1);
}
/*
* Returns the number of items on the stack.
*/
public int size() {
return this.items.size();
}
/*
* Convert to string as an array from bottom to top
*/
public String toString() {
if (!this.items.isEmpty()) {
String arrString = this.items.toString();
// remove open and closing bracket
return "bottom ->" + arrString + "<- top";
} else {
return "<<empty stack>>";
}
}
}
Listing3.5.1.Implementing a Stack class using Java ArrayLists
Remember in our discussion of ArrayList in Subsection 1.9.1 that we put the data type in angle brackets? This allowed us to have an ArrayList<String>, ArrayList<Integer>, etc. We would also like to be able to create a Stack whose elements are of any data type. To do this, we specify in line 4 that a stack has a generic data type. The T is like a variable that, instead of holding an integer, double, or string value, holds a data type. Thus, when we create a Stack<String>, the data type String provides the value that fills in the generic T. The body of the class uses T anywhere that it needs the type of stack we are dealing with.
Now we must write a program that creates a Stack object and then uses it. Listing 3.5.2 shows the Stack class in action as we perform the sequence of operations from Section 3.4. We don’t need to import the Stack class as long as its source file is in the same directory as our test program. (The interactive code in Listing 3.5.2 has been set up properly for this to work.)
Listing3.5.2.Program to Test the Stack Class
It is important to note that we could have chosen to implement the stack using an ArrayList where the top is at the beginning instead of at the end. In this case, the previous pop and append methods would no longer work and we would have to index position 0 (the first item in the list) explicitly using remove and add. The implementation is shown in Listing 3.5.3.
import java.util.ArrayList;
import java.util.NoSuchElementException;
public class Stack<T> {
/*
* The top of the stack is at the beginning
* of the ArrayList.
*/
ArrayList<T> items;
/*
* Create a new stack
*/
public Stack() {
this.items = new ArrayList<T>();
}
/*
* Returns true if there are no items on the stack;
* false otherwise.
*/
public boolean isEmpty() {
return (this.items.isEmpty());
}
/*
* Pushes given item on the top of the stack
*/
public void push(T item) {
this.items.add(0, item);
}
/*
* Removes the item on top of the stack and returns it.
* If the stack is empty, throws an exception.
*/
public T pop() {
if (this.isEmpty()) {
throw new NoSuchElementException("Stack is empty.");
}
return this.items.remove(0);
}
/*
* Returns the item on top of the stack without removing it.
* If the stack is empty, throws an exception.
*/
public T peek() {
if (this.isEmpty()) {
throw new NoSuchElementException("Stack is empty.");
}
return this.items.get(0);
}
/*
* Returns the number of items on the stack.
*/
public int size() {
return this.items.size();
}
/*
* Convert to string as an array from top to bottom
*/
public String toString() {
if (!this.items.isEmpty()) {
String arrString = this.items.toString();
// remove open and closing bracket
return "top ->" + arrString + "<- bottom";
} else {
return "<<empty stack>>";
}
}
}
Listing3.5.3.Alternative Implementation of the Stack class
This ability to change the physical implementation of an abstract data type while maintaining the logical characteristics is an example of abstraction at work. However, even though the stack will work either way, if we consider the performance of the two implementations, there is definitely a difference. Recall that the add() and remove() operations for the end of the ArrayList were both \(O(1)\text{.}\) This means that the first implementation will perform push and pop in constant time no matter how many items are on the stack. The performance of the second implementation suffers in that the add(0) and remove(0) operations will both require \(O(n)\) for a stack of size n. Clearly, even though the implementations are logically equivalent, they would have very different timings when performing benchmark testing.
ExercisesSelf Check
1.
Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?
Stack<String> m = new Stack<>();
m.push("x");
m.push("y");
m.pop();
m.push("z");
m.peek();
"x"
Remember that a stack is built from the bottom up.
"y"
Remember that a stack is built from the bottom up.
"z"
Good job.
The stack is empty
Remember that a stack is built from the bottom up.
2.
Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?
Stack<String> m = new Stack<>();
m.push("x");
m.push("y");
m.push("z");
while (!m.isEmpty()) {
m.pop();
m.pop();
}
"x"
You may want to check out the docs for isEmpty
the stack is empty
There is an odd number of things on the stack but each time through the loop 2 things are popped.
an error will occur
Good Job.
"z"
You may want to check out the documentation for isEmpty
Write a method named reverseString that takes a string as input and uses a stack to reverse the characters in that string.
