Algorithms Part 1 - Bags, Queues and Stacks

This is part 1 of the Algorithms series. In this series, I will write a summary of the book Algorithms by Robert Sedgewick and Kevin Wayne.

Introduction

You may wonder is this series good for me? If you are a developer or programmer with basic knowledge of Java or Kotlin or any other OOP language who feels an urge to improve his/her knowledge about Algorithms and Data Structures, you are at the right place! Should you read the entire book? It depends. If you want to be an Algorithm guru, of course you not only have to read this book, but also you need to read other books as well! However, to become familiar with algorithms and using them in your code, it is not necessary and this series would suffice. Be sure that we will provide the necessary content to understand the concept that we are covering(this time, Bags, Queues and Stacks). Without further ado, let's dive into world of Algorithms.

What we cover from the book in this chapter: LinkedList, Bag, Stack and Queue and their implementations.

What we do NOT cover the book in this chapter: Generics and Iterators, because we assume our readers have a good knowledge about these concepts. However, I will write another article about Iterators and will provide a link to that post here.

Bags, Queues and Stacks

This section involves understanding three fundamental collections of objects. These collections differ in how they remove the objects or examine the next object. The goal of studying these collections is to understand that the way objects are represented in a collection directly impacts the efficiency of the various operations. Let's first examine the APIs of each of these collections:

Bag, Queue and Stack API

The APIs are almost identical, with the addition of a remove function for Queue(dequeue() method) and Stack(pop() method).

Bag

Bag is a collection where order of iteration is unspecified and removing items is not supported -its purpose is to collect items and iterating through them.
We can use Stack or Queue to provide the same functionality, but to emphasize the fact that order of items is not important, we use Bag. The use-case is when we want to do some calculations on an input data(e.g. calculating average and other statistical functions) and the order of inputs is not important to the client.

Queue

A Queue (or a FIFO Queue) is a collection that is based on the first-in-first-out (FIFO) policy. A typical reason to use a queue in an application is to save items in a collection while at the same time preserving their relative order: they come out in the same order in which they were put in. For instance, if we want to read values from a file or console and save them in the order in which we read them, we can save them in a queue and then dequeue each one to process them.

Stack

A Stack (or a pushdown Stack) is a collection that is based on the last-in-first-out(LIFO) policy. When a client iterates through the items in a stack with the foreach construct, the items are processed in the reversed order in which they were added. A typical reason to use a stack is to save items in a collection while at the same time reversing their relative order.

One of the most important usages of the Stack is in the compilers and in the arithmetic expression evaluation. To process an arithmetic expression, we proceed from left to right and take the entities one at a time. We manipulate the stacks according to four possible cases:

1. push operands onto the operand stack
2. push operators onto the operator stack
3. ignore left parentheses
4. on encountering a right parentheses, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.
5. after the final parentheses has been processed, the one remaining value on the stack is the result of the expression.

Here is the code for the above arithmetic expression evaluation.
NOTE: It's different from the one in the book. It does not use the libraries mentioned in the book. Another thing to notice is that, in the book, StdIn.readString() method has been used. This method may cause the program to fall in an infinite loop because it waits for the user input. We have used the one that uses the arguments when running the program.

import java.util.Stack;

public class Evaluate {
    public static void main(String[] args) {
        Stack<String> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();
        //     ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
        //     ( ( 1 + sqrt ( 5.0 ) ) / 2.0 )
        for (String s : args) {

            if (s.equals("(")) ;
            else if (s.equals("+")) ops.push(s);
            else if (s.equals("-")) ops.push(s);
            else if (s.equals("*")) ops.push(s);
            else if (s.equals("/")) ops.push(s);
            else if (s.equals("sqrt")) ops.push(s);
            else if (s.equals(")")) {
                String op = ops.pop();
                double v = vals.pop();
                if (op.equals("+")) v = vals.pop() + v;
                else if (op.equals("-")) v = vals.pop() - v;
                else if (op.equals("*")) v = vals.pop() * v;
                else if (op.equals("/")) v = vals.pop() / v;
                else if (op.equals("sqrt")) v = Math.sqrt(v);
                vals.push(v);
            } else
                vals.push(Double.parseDouble(s));
        }
        System.out.println(vals.pop());

    }
}

This algorithm may seem complicated at first but it is easy to reason about. Any time the algorithm encounters a subexpression consisting of two operands separated by an operator, all surrounded by parentheses, it leaves the result of performing that operation on those operands on the operand stack. The result is the same as if that value had appeared in the input instead of the subexpression, so we can think of replacing the subexpression by the value to get an expression that would yield the same result. We can apply this argument again and again until we get a single value.

NOTE: The code above is a simple example of an interpreter: a program that interprets the computation specified by a given string and performs the computation to arrive at the result.

Implementing Collections

To begin with implementation details, we start with simple classic implementation, and then we will enhance them that will lead us to implementations of the APIs at the first of the article.

Fixed-Capacity Stack

To implement the fixed-capacity stack, an obvious choice is to use an array. The instance variable are an array a[] that hold the items in the stack and an integer N that counts the number of items in the stack. To remove an item, we decrement N and then return a[n]; to insert a new item, we set a[N] equal to the new item and then increment N. This implementation has these properties:

• the items in the array are in their insertion order
• the stack is empty when N is 0
• the top of the stack is at a[N - 1]

The primary performance characteristic of this implementation is that push and pop operations take time independent of the stack size.

Here is the implementation of the fixed-capacity stack:

public class FixedCapacityStack<T> {
    private T[] a;
    private int N;

    @SuppressWarnings("unchecked")
    public FixedCapacityStack(int capacity) {
        a = (T[]) new Object[capacity];
    }

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

    public void push(T item) {
        a[N++] = item;
    }

    public T pop() {
        return a[--N];
    }

    public int size() {
        return N;
    }

}

Here is a test client for the fixed-capacity stack:

public class FixedCapacityStackClient {
    public static void main(String[] args) {
        FixedCapacityStack<String> stack = new FixedCapacityStack<String>(10);
        for (int i = 0; i < 10; i++) {
            stack.push("item:" + i);
        }
        System.out.println("Is the stack empty? " + stack.isEmpty());
        System.out.println("Stack size? " + stack.size());

        for (int i = stack.size(); i > 0; i--) {
            System.out.println("size is: " + stack.size() + " and item is: " + stack.pop());
        }
        System.out.println("Is the stack empty? " + stack.isEmpty());
        System.out.println("Stack size? " + stack.size());
    }
}

This implementation is not suitable for every use case. At least, we want the stack size to be flexible. To do so, we resize the array in the stack. We will modify our implementation to dynamically adjust the size of the array a[] so that it is sufficiently large to hold all of the items and not so large to waste an excessive amount of space.
To have a full implementation of the stack with arrays, we should consider these steps:

• we should implement the Iterable interface to be able to iterate through each item in the stack
• we should implement a resize method so that it can increase/decrease the array size if needed
• double the array size if the array is full
• reduce the array size to half if number of items in the array is less than the quarter of the array size

import java.util.Iterator;

public class ArrayStack<T> implements Iterable<T> {

    private T[] items;
    private int N;

    // 1
    public ArrayStack() {
        this.items = (T[]) new Object[1];
    }

    // 2
    public ArrayStack(int capacity) {
        this.items = (T[]) new Object[capacity];
    }

    public void push(T item) {
        // 3
        if (N == items.length)
            resize(N * 2);
        items[N++] = item;
    }

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


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

    public int size() {
        return N;
    }

    private void resize(int maxCapacity) {
        T[] temp = (T[]) new Object[maxCapacity];
        for (int i = 0; i < N; i++) {
            temp[i] = items[i];
        }
        items = temp;
    }


    // 6
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            int index = N;

            @Override
            public boolean hasNext() {
                return index > 0;
            }

            @Override
            public T next() {
                return items[--index];
            }
        };
    }
}

• 1 & 2 -> we have defined two constructors for the stack. One with a default array size of 1. The other is provided for the user to specify an estimate for the capacity of the stack.
• 3 -> when pushing an item in the stack, if array is full, we are doubling the array size
• 4 -> when popping an item from the stack, we should set the array position to null to avoid loitering.
• 5 -> when popping an item from the stack, if the stack size is less than a quarter of the array size, we will shrink the array size to half
• 6 -> we implement the iterator interface to iterate through the items of the stack. This way, we can use foreach loops in Java and clients are not concerned with iteration.

We have a working implementation of the Stack. There are some issues with this implementation:

• More space is required than the actual size of the stack
• Time per operation is not independent of the size of the collection

To tackle these issues, we can use linked-lists to implement stack. It will solve the issues mentioned above. Let's see how we can implement stack using linked-list:

import java.util.Iterator;

public class Stack<T> implements Iterable<T> {

    private Node first;
    private int N;

    private class Node {
        T item;
        Node next;
    }


    public void push(T item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    public T pop() {
        T item = first.item;
        first = first.next;
        N--;
        return item;
    }


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

    public int size() {
        return N;
    }


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T item = current.item;
                current = current.next;
                return item;
            }
        };
    }
}

As we can see, this implementation is more flexible than the array one. It uses exactly the same memory space as needed by the stack(unlike the array implementation that the array needs more space than the stack). The operations on the stack are also not dependent on the stack size.

This was the full implementation of the stack. Now let's see Bag and Queue implementations. Keep in mind that we can implement Bag and Queue with array as well. But we will not cover those implementations because it's straight forward.

We'll start with queue:

import java.util.Iterator;

public class Queue<T> implements Iterable<T> {

    private Node first;
    // 1
    private Node last;
    private int N;

    private class Node {
        T item;
        Node next;
    }

    public void enqueue(T item) {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else oldLast.next = last;
        N++;
    }

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

    public int size() {
        return N;
    }

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


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T item = first.item;
                current = first.next;
                return item;
            }
        };
    }
}

• 1 -> we need last in the queue because every time we add something, we should add it to the end of it(remember that queue is first-in, first-out).

The other parts are the same as the Stack implementation. So, let's see the Bag implementation:

import java.util.Iterator;

public class Bag<T> implements Iterable<T> {

    private Node first;
    private int N;

    private class Node {
        T item;
        Node next;
    }

    public void add(T item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

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

    public int size() {
        return N;
    }


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T item = current.item;
                current = current.next;
                return item;
            }
        };
    }
}

As we can see, Bag implementation is the same as the Stack with two minor changes:

• we should remove the pop() method because Bag does not support removing items
• rename the push() method to add()