Stacks & Queues: Implementation

For a nice, concise overview of stack and queues, read https://introcs.cs.princeton.edu/java/43stack/

Here is a video lecture for the material outlined below. If you prefer (or want supplemental) textbook readings, Bailey Chapter 10 covers this topic and the previous topic.

The video contains sections on

1. Fixed stack of strings (0:13)
2. Visualizing the fixed-size stack (3:38)
3. ArrayList stack (8:06)
4. Aside: Java generics (12:56)
5. Visualizing ArrayList stack (14:33)
6. Linked list stack (18:19)
7. Visualizing linke list stack (20:34)
8. Singly-linked list stack (21:58)
9. Linked list queue (27:33)
10. Array-based queue (32:12)
11. Double-ended queue (Deque) (38:40)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=1be72107-6db7-4b5e-a8f7-acb301717caa

We might use an array to implement a stack of fixed size. Here's an implementation that specifically holds strings:

public class FixedStackOfStrings {
    private String[] items;  // holds the items
    private int n;           // number of items in stack

    public FixedStackOfStrings(int capacity) {
        items = new String[capacity];
    }

    public boolean isEmpty() {
        return n == 0; 
    }

    public boolean isFull() {
        return n == items.length; 
    }

    public void push(String item) {
        items[n] = item;
        n++;
    }

    public String pop() {
        n--;
        String item = items[n];
        return item;
    }

    public static void main(String[] args) {
        FixedStackOfStrings stack = new FixedStackOfStrings(5);
        stack.push("tasty");
        stack.push("cakes");
        stack.pop();
        stack.push("salad");
    }
}

The main method would result in this sequence of states for the fields items and n:

FixedStackOfStrings stack = new FixedStackOfStrings(5);

      +------+------+------+------+------+
items | null | null | null | null | null |
      +------+------+------+------+------+
         ^
         |
         n
        (0)

stack.push("tasty");

      +---------+------+------+------+------+
items | "tasty" | null | null | null | null |
      +---------+------+------+------+------+
                    ^
                    |
                    n
                   (1)

stack.push("cakes");

      +---------+---------+------+------+------+
items | "tasty" | "cakes" | null | null | null |
      +---------+---------+------+------+------+
                              ^
                              |
                              n
                             (2)

stack.pop();

      +---------+---------+------+------+------+
items | "tasty" | "cakes" | null | null | null |
      +---------+---------+------+------+------+
                     ^
                     |
                     n
                    (1)

stack.push("sandwiches");

      +---------+---------+------+------+------+
items | "tasty" | "salad" | null | null | null |
      +---------+---------+------+------+------+
                              ^
                              |
                              n
                             (2)

Note how the field n is both the number of elements in the stack and the index of the first available spot in the array. Handy!

We can make our array-based stack more flexible by having it resize the internal array when it runs out of space. This is just like the technique we used to implement ArrayList: create a new array double the size of the old one and copy over the current elements of the array. In fact, since we implemented an ArrayList in a previous topic, let's just use that!

import java.util.ArrayList;
public class ArrayListStack<Item> {
    private ArrayList<Item> stack;

    public ArrayListStack() {
        stack = new ArrayList<>();
    }

    public int size() {
        return stack.size();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public void push(Item item) {
        stack.add(item);
    }

    public Item pop() {
        return stack.remove(size() - 1);
    }

    public Item peek() {
        return stack.get(size() - 1);
    }
}

We use the end of the ArrayList as the top of the stack because adding and removing from the end of an ArrayList are constant time operations. If you're curious about an array-based stack implementation that handles the resizing itself instead of using an ArrayList, see ResizingArrayStack.java.

One important property of a stack is that we only interact with one end of the structure, the top of the stack. This makes a linked list an excellent candidate for the internal stack data structure—it provides constant time operations on the head of the list, and we don't have to worry about wasted capacity or resizing like we do when using an array.

import java.util.LinkedList;
public class LinkedListStack<Item> {
    private LinkedList<Item> stack;

    public LinkedListStack() {
        stack = new LinkedList<>();
    }

    public int size() {
        return stack.size();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public void push(Item item) {
        stack.addFirst(item);
    }

    public Item pop() {
        return stack.removeFirst();
    }

    public Item peek() {
        return stack.getFirst();
    }
}

Now, Java's LinkedList class is a doubly-linked list. For the constant-time operations at the head of the list that we need, a singly-linked list would be sufficient, and use somewhat less space. Java doesn't provide a singly-linked list class, so we'd need to implement that ourselves:

public class SinglyLinkedStack<Item> {
    private int n;          // size of the stack
    private Node first;     // top of stack

    // helper linked list node class
    private class Node {
        private Item item;
        private Node next;
    }

    /**
     * Initializes an empty stack.
     */
    public SinglyLinkedStack() {
        first = null;
        n = 0;
    }

    /**
     * Is this stack empty?
     * @return true if this stack is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in the stack.
     * @return the number of items in the stack
     */
    public int size() {
        return n;
    }

    /**
     * Adds the item to this stack.
     * @param item the item to add
     */
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    /**
     * Removes and returns the item most recently added to this stack.
     * @return the item most recently added
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item pop() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = first.item;        // save item to return
        first = first.next;            // delete first node
        n--;
        return item;                   // return the saved item
    }


    /**
     * Returns (but does not remove) the item most recently added to this stack.
     * @return the item most recently added to this stack
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return first.item;
    }
}

Since the Queue ADT only provides operations to add to the end of the queue and remove from the beginning, a singly-linked list with a tail reference is an ideal data structure to use for implementation. We never remove from the end, so we never need the previous references a doubly-linked list provides.

public class SinglyLinkedQueue<Item> {
    private int n;          // size of the queue
    private Node front;     // front of the queue
    private Node end;       // end of the queue


    // helper linked list node class
    private class Node {
        private Item item;
        private Node next;
    }

    /**
     * Initializes an empty stack.
     */
    public SinglyLinkedQueue() {
        first = null;
        end = null;
        n = 0;
    }

    /**
     * Is this stack empty?
     * @return true if this stack is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in the stack.
     * @return the number of items in the stack
     */
    public int size() {
        return n;
    }

    /**
     * Adds the item to this stack.
     * @param item the item to add
     */
    public void add(Item item) {
        if (isEmpty()) {
            front = new Node();
            front.item = item;
            end = front;
        } else {
            end.next = new Node();
            end = end.next;
            end.item = item;
        }
        n++;
    }

    /**
     * Removes and returns the item most recently added to this stack.
     * @return the item most recently added
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item remove() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = first.item;        // save item to return
        first = first.next;            // delete first node
        n--;
        return item;                   // return the saved item
    }


    /**
     * Returns (but does not remove) the item most recently added to this stack.
     * @return the item most recently added to this stack
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return first.item;
    }
}

A related abstract data type to the Queue is the Double-Ended Queue (which is often shortened to Deque, pronouced like deck). A deque can have elements added and removed from both ends (hence double-ended). Java defines a Deque interface which includes the operations

public void addFirst(E item);
public void addLast(E item);
public E getFirst();
public E getLast();
public E removeFirst();
public E removeLast();

With these operations, a deque can act as both a queue and a stack. If these seem familiar from our definition of a LinkedList, it will be no surprise to learn that Java's LinkedList implements the Deque interface. Java also provides an array-based implementation with the ArrayDeque class (in fact, Java's documentation suggests using an ArrayDeque instead a Stack if you want stack-like behavior).

1. What data type would you choose to implement an "Undo" feature in a word processor?
2. Suppose that you implemented push in the linked list implementation of LinkedListStack with the following code. What is the mistake?

   public void push(Object value) {
      Node second = first;
      Node first = new Node();
      first.value = value;
      first.next = second;
      n++;
   }
   

3. Describe how we might efficiently implement a Queue as a pair of Stacks, called a “stack pair.” (Hint: Think of one of the stacks as the head of the queue and the other as the tail.)
4. Write a method called splitStack that accepts a stack of integers as a parameter and rearranges its elements so that all the negatives appear on the bottom of the stack and all the nonnegatives appear on the top. If after this method is called you were to pop numbers off the stack, you would first get all the nonnegative numbers and then get all the negative numbers. It does not matter what order the numbers appear in as long as all the negatives appear lower in the stack than all the nonnegatives. For example, if the stack stores [3, −5, 1, 2, −4], an acceptable result from your method would be [−5, −4, 3, 1, 2]. Use a single queue as auxiliary storage.
5. Write a program Parentheses.java that reads a string of parentheses, square brackets, and curly braces from standard input and uses a stack to determine whether they are properly balanced. For example, your program should print true for [()]{}{[()()]()} and false for [(])

• Questions?
• Form questions
• My reflections on the lab
  • Seems like a lot of people waited until Friday or later to start working on the lab
  • Doing this will make the labs harder than they need to be
  • Maybe you weren't sure how to get started (or things came up, that's understandable)
  • That's okay, this is new ideas, a new programming language—it's not easy
  • The important thing is to do in this case is to ask for help
  • If you've done the preparatory exercises and read the lab writeup, and you're not sure where to begin, "how should I get started on the lab" is a great question to ask (in class, on the check-in forum, on discord)
  • But this question will be more helpful to you the earlier you can ask it: more lab assistant hours you can go to, more opportunities to ask me questions, more time to discover other tricky parts of the assignment and get help or review relevant topics
  • Go over my implementation
    • Design process
      • What information do I need to keep track of?
      • What private fields should I use to do this?
      • Write a constructor to initialize these fields
      • What public methods do I need
        • Specified by TwoPlayerGame interface
        • These implement the game rules
      • Implement toString so the object can be printed out
      • Implement equals so the object can be checked for equality (not necessary for CoinStrip)
      • Implement a main method that creates a CoinStrip object and uses its public methods to play the game
    • Not many people followed the advice on data representation from writeup
      • I will try to make the lab writeups clearer and more concise
    • Code style
      • No extraneous blank lines
      • No chunks of commented-out code
      • Consistent indentation and formatting
• Partner survey for lab 3