The Stack ADT

Section 16.4 The Stack ADT

A stack is a special type of list that allows insertions and removals to be performed only to the front of the list. Therefore, it enforces last-in–first-out (LIFO) behavior on the list. Think of a stack of dishes at the salad bar. When you put a dish on the stack, it goes onto the top of the stack. When you remove a dish from the stack, it comes from the top of the stack (Figure 16.4.1).

🔗

Figure 16.4.1. A stack is a list that permits insertions and removals only at its top.
🔗

The stack operations are conventionally called push, for insert, and pop, for remove, respectively. Thus, the stack ADT stores a list of data and supports the following operations:

🔗

Push—inserts an object onto the top of the stack.
Pop—removes the top object from the stack.
Empty—returns true if the stack is empty.
Peek—retrieves the top object without removing it.

🔗

Stacks are useful for a number of important computing tasks. For example, during program execution, method call and return happens in a LIFO fashion. The last method called is the first method exited. Therefore, a stack structure known as the run-time stack is used to manage method calls during program execution. When a method is called, an activation block is created, which includes the method’s parameters, local variables, and return address. The activation block is pushed onto the stack. When that method call returns, the return address is retrieved from the activation block and the whole block is popped off the stack. The Exception.printStackTrace() method uses the run-time stack to print a trace of the method calls that led to an exception.

🔗

Subsection 16.4.1 The `Stack`Class

Given our general definition of List and Node, it is practically trivial to define the stack ADT as a subclass of List(Figure 16.4.2). As a subclass of List, a Stack will inherit all of the public and protected methods defined in List. Therefore, we can simply use the insertAtFront() and removeFirst() methods for the push and pop operations, respectively (Listing 16.4.3).

🔗

Figure 16.4.2. As a subclass of `List`, a `Stack` inherits all of its public (+) and protected (#) elements. Therefore `push()` can be defined in terms of `insertAtFront()` and `pop()` can be defined in terms of `removeFirst()`.
🔗

Because the isEmpty() method is defined in List, there’s no need to override it in Stack. In effect, the push() and pop() methods merely rename the insertAtFront() and removeFirst() methods. Note that the Stack() constructor calls the superclass constructor. This is necessary so that the list can be initialized.

🔗

public class Stack extends List {
     public Stack() {
         super();          // Initialize the list
     }
     public void push( Object obj ) {
         insertAtFront( obj );
     }
     public Object pop() {
         return removeFirst();
     }
} // Stack

Listing 16.4.3. The StackADT.

🔗

Do we have to make any changes to the List class in order to use it this way? Yes. We want to change the declaration of head from private to protected, so it can be accessed in the Stack class. And we want to declare List’s public access methods, such as insertAtFront() and removeFirst(), as protected. That will allow them to be used in Stack, and in any classes that extend List, but not by other classes. This is essential. Unless we do this we haven’t really restricted the stack operations to push and pop and, therefore, we haven’t really defined a stack ADT. Remember, an ADT defines the data and the operations on the data. A stack ADT must restrict access to the data to just the push and pop operations.

🔗

Principle 16.4.4. Protected Elements.

An object’s protected elements are hidden from all other objects except instances of the same class or its subclasses.

🔗

Principle 16.4.5. EFFECTIVE DESIGN: Information Hiding.

Use the private and protected qualifiers to hide an ADT’s implementation details from other objects. Use public to define the ADT’s interface.

🔗

Exercises Self-Study Exercise

1. Stack Reverse String.

The complete implementation of the Stack ADT as a subclass of List is given here. Complete the main method by implementing an algorithm that uses a stack to reverse a string. (Note: the Character(char) constructor has been deprecated. To create a Character object, you can use the static method Character.valueOf(char) instead.)

🔗

public class Stack extends List {
    public Stack() {
        super(); // Initialize the list
    }

public void push(Object obj) {
        insertAtFront(obj);
    }

public Object pop() {
        return removeFirst();
    }

// Complete the main method to use a Stack reverse a string 
    public static void main(String argv[]) {
        Stack stack = new Stack();
        String string = "Hello this is a test string";
        System.out.println("String: " + string);
        String reversed = "";

System.out.println("Reversed String: " + reversed);
    } // main()

} // Stack

class List {
    protected Node head;

public List() {
        head = null;
    }

public boolean isEmpty() {
        return head == null;
    }

public void print() {
        if (isEmpty())
            System.out.println("List is empty");
        Node current = head;
        while (current != null) {
            System.out.println(current.toString());
            current = current.getNext();
        }
    } // print()

protected void insertAtFront(Object obj) {
        Node newnode = new Node(obj);
        newnode.setNext(head);
        head = newnode;
    }

protected void insertAtRear(Object obj) {
        if (isEmpty())
            head = new Node(obj);
        else {
            Node current = head; // Start at head of list
            while (current.getNext() != null) // Find the end of the list
                current = current.getNext();
            current.setNext(new Node(obj)); // Create and insert newNode
        }
    } // insertAtRear()

protected Object removeFirst() {
        if (isEmpty()) // Empty List
            return null;
        Node first = head;
        head = head.getNext();
        return first.getData();
    } // removeFirst()

protected Object removeLast() {
        if (isEmpty()) // empty list
            return null;
        Node current = head;
        if (current.getNext() == null) {// Singleton list
            head = null;
            return current.getData();
        }
        Node previous = null; // All other cases
        while (current.getNext() != null) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(null);
        return current.getData();
    } // removeLast()
} // List

Hint.

Your algorithm should loop through the string pushing each character onto the stack. Once all the characters have been pushed, use another loop to pop all the characters until the stack is empty.

🔗

2. Stack Peek.

Using the code on the previous exercise, define and test the peek() method for the Stack class. It should take no parameters and return an Object. It should return the Object on the top of the stack.

🔗

You have attempted 1 of 2 activities on this page.

🔗

Prev Top Next

Section 16.4 The Stack ADT

Subsection 16.4.1 The StackClass

Principle 16.4.4. Protected Elements.

Principle 16.4.5. EFFECTIVE DESIGN: Information Hiding.

Exercises Self-Study Exercise

1. Stack Reverse String.

2. Stack Peek.

Subsection 16.4.1 The `Stack`Class