3. Stacks and Queues

3.1. Stacks

LIFO: Last In, First Out.
Restricted form of list: Insert and remove only at front of list.
Notation:
- Insert: PUSH
- Remove: POP
- The accessible element is called TOP.

3.2. Stack ADT

public interface Stack { // Stack class ADT
  // Reinitialize the stack.
  public void clear();

  // Push "it" onto the top of the stack
  public boolean push(Object it);

  // Remove and return the element at the top of the stack
  public Object pop();

  // Return a copy of the top element
  public Object topValue();

  // Return the number of elements in the stack
  public int length();
  
  // Return true if the stack is empty 
  public boolean isEmpty();
}

3.3. Array-Based Stack (1)

Issues:
- Which end is the top?
- Where does “top” point to?
- What are the costs of the operations?

3.4. Array-Based Stack (2)

class AStack implements Stack {
  private Object stackArray[];    // Array holding stack
  private static final int DEFAULT_SIZE = 10;
  private int maxSize;            // Maximum size of stack
  private int top;                // First free position at top

  // Constructors
  AStack(int size) {
    maxSize = size;
    top = 0;
    stackArray = new Object[size]; // Create stackArray
  }
  AStack() { this(DEFAULT_SIZE); }

3.5. Linked Stack

// 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; }

What are the costs of the operations?
How do space requirements compare to the array-based stack implementation?

3.6. Queues

FIFO: First in, First Out
Restricted form of list: Insert at one end, remove from the other.
Notation:
- Insert: Enqueue
- Delete: Dequeue
- First element: Front
- Last element: Rear