Chapter 6: Stack Implementations

Copyright Information

• Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved

Data Structures and Abstractions with Java™ 5th Edition

Chapter 6: Stack Implementations

Linked Implementation

• Each operation in a linked implementation involves the top of the stack:
  • push: adds an entry to the top of the stack
  • pop: removes an entry from the top of the stack
  • peek: retrieves the top entry without removing it
• The head of the linked list provides the easiest and fastest access, and is designated as the top of the stack.

Figure 6-1

• Description: A chain of linked nodes that implements a stack.

LinkedStack Class Outline

• Listing 6-1: Outline of a linked implementation of the ADT stack.
• Class Definition: public final class LinkedStack<T> implements StackInterface<T> {
  • private Node topNode; // References the first node in the chain
  • Constructor:
  • public LinkedStack()
    • Initializes topNode to null
  • Node Class Definition:
  • private class Node {
    • private T data; // Entry in stack
    • private Node next; // Link to next node
  • Implementations of node operations go here.

Figure 6-2

• Description: Illustration of adding a new node to the top of a linked stack.

Definition of Push

• Push Method:
  • public void push(T newEntry) {
  • Node newNode = new Node(newEntry, topNode);
  • topNode = newNode;
  • End Push.

Figure 6-3

• Description: The stack before and after pop deletes the first node in the chain.

Definitions of Peek and Pop

• Peek Method:
  • public T peek() {
  • if (isEmpty())
    • throw new EmptyStackException();
  • else
    • return topNode.getData();
  • End Peek.
• Pop Method:
  • public T pop() {
  • T top = peek(); // Might throw EmptyStackException
  • topNode = topNode.getNextNode();
  • return top;
  • End Pop.

Definitions of isEmpty and Clear

• isEmpty Method:
  • public boolean isEmpty() {
  • return topNode == null;
  • End isEmpty.
• Clear Method:
  • public void clear() {
  • topNode = null;
  • End Clear.

Array-Based Stack Implementation

• Each operation in an array-based implementation also involves the top of the stack:
  • push: adds an entry to the top of the stack
  • pop: removes an entry from the top of the stack
  • peek: retrieves the top entry without removing it
• The end of the array is the easiest to access and acts as the top of the stack.

Figure 6-4

• Description: Displays two array representations of a stack.

ArrayStack Class Outline

• Listing 6-2: Outline of an array-based implementation of the ADT stack.
• Class Definition: public final class ArrayStack<T> implements StackInterface<T> {
  • private T[] stack; // Array of stack entries
  • private int topIndex; // Index of top entry
  • private boolean integrityOK = false;
  • private static final int DEFAULT_CAPACITY = 50;
  • private static final int MAX_CAPACITY = 10000;
• Constructor:
  • Default Constructor:
  • public ArrayStack() { this(DEFAULT_CAPACITY); }
  • Parameterized Constructor:
  • public ArrayStack(int initialCapacity) {
    • integrityOK = false;
    • checkCapacity(initialCapacity);
    • Safe Cast:
    • @SuppressWarnings("unchecked") T[] tempStack = (T[])new Object[initialCapacity];
    • stack = tempStack;
    • topIndex = -1;
    • integrityOK = true;
  • End Constructor.

Adding to the Top

• Push Method:
  • public void push(T newEntry) {
  • checkIntegrity();
  • ensureCapacity();
  • stack[topIndex + 1] = newEntry;
  • topIndex++;
  • End Push.
• Ensure Capacity Method:
  • private void ensureCapacity() {
  • if (topIndex >= stack.length - 1) // If array is full, double its size
    • int newLength = 2 * stack.length;
    • checkCapacity(newLength);
    • stack = Arrays.copyOf(stack, newLength);
  • End ensureCapacity.

Figure