Stacks, Queues, & Deques

STACKS

A stack is a crippled list. You may manipulate only the item at the top of the stack. The main operations: you may push a new item onto the top of the stack; you may pop the top item off the stack; you may examine the top item of the stack. A stack can grow arbitrarily large.

public interface Stack {
    public int size();
    public boolean isEmpty();
    public void push(Object item);
    public Object pop();
    public Object top();
}

In any reasonable implementation, all these methods run in $O(1)$ time. A stack is easily implemented as a singly-linked list, using just the front(), insertFront(), and removeFront() methods.

Why talk about Stacks when we already have Lists? Mainly so you can carry on discussions with other computer programmers. If somebody tells you that an algorithm uses a stack, the limitations of a stack give you a hint how the algorithm works.

Sample application: Verifying matched parentheses in a String like {[(){[]}]()}. Scan through the String, character by character.

• When you encounter a lefty--’{’, ’[’, or ’(’--push it onto the stack.
• When you encounter a righty, pop its counterpart from atop the stack, and check that they match.

If there’s a mismatch or null returned, or if the stack is not empty when you reach the end of the string, the parentheses are not properly matched.

Stack in Algorithms

Stack: linked-list implementation in Java

public class LinkedStackOfStrings {
    private Node first = null;

    private class Node {
        String item;
        Node next;
    }

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

    public void push(String item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public String pop() {
        String item = first.item;
        first = first.next;
        return item;
    }
}

Every operation takes constant time in the worst case.

A stack with N items uses ~ 40 N bytes.

This accounts for the memory for the stack

Stack: array implementation

• Use array s[] to store N items on stack.
• push(): add new item at s[N].
• pop(): remove item from s[N-1].

public class FixedCapacityStackOfStrings {

    private String[] s;
    private int N = 0;

    public FixedCapacityStackOfStrings(int capacity) { // a cheat (stay tuned)
        s = new String[capacity];
    }

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

    public void push(String item) {
        s[N++] = item; // use to index into array; then increment N
    }

    public String pop() {
        return s[--N]; // decrement N; then use to index into array
    }

}

Loitering. Holding a reference to an object when it is no longer needed.

public String pop() {
    return s[--N];
}
// loitering

public String pop() {
    String item = s[--N];
    s[N] = null;
    return item;
}
// this version avoids "loitering": garbage collector can reclaim memory only if no outstanding references

Stack: resizing-array implementation

public ResizingArrayStackOfStrings() {
    s = new String[1];
}

public void push(String item) {
    if (N == s.length)
        resize(2 * s.length);
    s[N++] = item;

}

public String pop() {
    String item = s[--N];
    s[N] = null;
    if (N > 0 && N == s.length / 4)
        resize(s.length / 2);
    return item;
}

private void resize(int capacity) {
    String[] copy = new String[capacity];
    for (int i = 0; i < N; i++)
        copy[i] = s[i];
    s = copy;
}

Generic stack: linked-list implementation

public class Stack<Item> {
    private Node first = null;

    private class Node {
        Item item;
        Node next;
    }

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

    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public Item pop() {
        Item item = first.item;
        first = first.next;
        return item;
    }
}

public class FixedCapacityStack<Item> {

    private Item[] s;
    private int N = 0;

    public FixedCapacityStack(int capacity) { // a cheat (stay tuned)
        s = new Item[capacity];
    }

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

    public void push(Item item) {
        s[N++] = item; // use to index into array; then increment N
    }

    public Item pop() {
        return s[--N]; // decrement N; then use to index into array
    }
}

QUEUES

A queue is also a crippled list. You may read or remove only the item at the front of the queue, and you may add an item only to the back of the queue. The main operations: you may enqueue an item at the back of the queue; you may dequeue the item at the front; you may examine the front item. Don’t be fooled by the diagram; a queue can grow arbitrarily long.

Sample Application: Printer queues. When you submit a job to be printed at a selected printer, your job goes into a queue. When the printer finishes printing a job, it dequeues the next job and prints it.

public interface Queue {
    public int size();
    public boolean isEmpty();
    public void enqueue(Object item);
    public Object dequeue();
    public Object front();
}

In any reasonable implementation, all these methods run in $O(1)$ time. A queue is easily implemented as a singly-linked list with a tail pointer.

Queue in Algorithms

public class LinkedQueueOfStrings {
    private Node first, last;

    private class Node { /* same as in StackOfStrings */
        String item;
        Node next;
    }

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

    public void enqueue(String item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty())
            first = last;
        else
            oldlast.next = last;
    }

    public String dequeue() {
        String item = first.item;
        first = first.next;
        if (isEmpty())
            last = null;
        return item;
    }
}

DEQUES

A deque (pronounced "deck") is a Double-Ended Queue. You can insert and remove items at both ends. You can easily build a fast deque using a doubly-linked list. You just have to add removeFront() and removeBack() methods, and deny applications direct access to listnodes. Obviously, deques are less powerful than lists whose listnodes are accessible.

Postscript: A Faster Hash Code (not examinable)

Here’s another hash code for Strings, attributed to one P. J. Weinberger, which has been thoroughly tested and performs well in practice. It is faster than the one above, because it relies on bit operations (which are very fast) rather than the % operator (which is slow by comparison). You will learn about bit operations in CS 61C. Please don’t ask me to explain them to you.

static int hashCode(String key) {
    int code = 0;
    for (int i = 0; i < key.length(); i++) {
        code = (code << 4) + key.charAt(i);
        code = (code & 0x0fffffff) ^ ((code & 0xf0000000) >> 24);
    }
    return code;
}