Close
Register
Close Window

Data Structures & Algorithms

Chapter 3 Linked List and Stack

Show Source |    | About   «  3.8. Stacks   ::   Contents   ::   4.1. Chapter Introduction: Sorting  »

3.9. Linked Stacks

3.9.1. Linked Stack Implementation

The linked stack implementation is quite simple. Elements are inserted and removed only from the head of the list. A header node is not used because no special-case code is required for lists of zero or one elements. Here is the complete linked stack implementation.

// Linked stack implementation
class LStack implements Stack {
  private Link top;               // Pointer to first element
  private int size;               // Number of elements

  // Constructors
  LStack() { top = null; size = 0; }
  LStack(int size) { top = null; size = 0; }

  // Reinitialize stack
  public void clear() { top = null; size = 0; }

// Put "it" on stack
  public boolean push(Object it) {  
    top = new Link(it, top);
    size++;
    return true;
  }

// Remove "it" from stack
  public Object pop() {           
    if (top == null) return null;
    Object it = top.element();
    top = top.next();
    size--;
    return it;
  }

  public Object topValue() {      // Return top value
    if (top == null) return null;
    return top.element();
  }

  // Return stack length
  public int length() { return size; }
  
  // Check if the stack is empty
  public boolean isEmpty() { return size == 0; }
}
// Linked stack implementation
class LStack<E> implements Stack<E> {
  private Link<E> top;            // Pointer to first element
  private int size;               // Number of elements

  // Constructors
  LStack() { top = null; size = 0; }
  LStack(int size) { top = null; size = 0; }

  // Reinitialize stack
  public void clear() { top = null; size = 0; }

// Put "it" on stack
  public boolean push(E it) {  
    top = new Link<E>(it, top);
    size++;
    return true;
  }

// Remove "it" from stack
  public E pop() {           
    if (top == null) { return null; }
    E it = top.element();
    top = top.next();
    size--;
    return it;
  }

  public E topValue() {      // Return top value
    if (top == null) { return null; }
    return top.element();
  }

  // Return stack length
  public int length() { return size; }
  
  // Tell if the stack is empty
  public boolean isEmpty() { return size == 0; }
}

Here is a visual representation for the linked stack.

3.9.1.1. Linked Stack Push

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

3.9.2. Linked Stack Pop

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

3.9.2.1. Comparison of Array-Based and Linked Stacks

All operations for the array-based and linked stack implementations take constant time, so from a time efficiency perspective, neither has a significant advantage. Another basis for comparison is the total space required. The analysis is similar to that done for list implementations. The array-based stack must declare a fixed-size array initially, and some of that space is wasted whenever the stack is not full. The linked stack can shrink and grow but requires the overhead of a link field for every element.

When implementing multiple stacks, sometimes you can take advantage of the one-way growth of the array-based stack by using a single array to store two stacks. One stack grows inward from each end as illustrated by the figure below, hopefully leading to less wasted space. However, this only works well when the space requirements of the two stacks are inversely correlated. In other words, ideally when one stack grows, the other will shrink. This is particularly effective when elements are taken from one stack and given to the other. If instead both stacks grow at the same time, then the free space in the middle of the array will be exhausted quickly.

   «  3.8. Stacks   ::   Contents   ::   4.1. Chapter Introduction: Sorting  »

Close Window