Stacks and Queues

Sounds familiar? but we’re going to take a closer look.

This series of articles inspired by Algorithms, Part I course from Princeton University & Algorithms, 4th Edition. The full series of articles can be found here.

They are collection of items. The difference is in where to insert an item?, and which item to be removed?. Stacks are last-in-first-out (LIFO), while queues are first-in-first-out (FIFO).

Stacks and Queues — algs4.cs.princeton.edu

Stacks

The main operations of a stack are push, pop, & isEmpty.

The terminology that we use is push to insert an item on the top of the stack, and pop to remove the most recently added one.

Stack Implementation — Using Linked List

We’ll start by the stack class. It has a reference variable called “first” points to the last inserted node.

public class LinkedStack {
    private Node first = null;   // the top of the stack
}

Then, we have an inner class called “Node” to represent each node within the stack. Each node has a value(maybe integer, string, ….) , and a reference to the next node.

private class Node {
    String item;
    Node next;
}

— Push

Push on stack — algs4.cs.princeton.edu

— Pop

Pop doesn’t just remove the most recently added item, it also returns it.

Pop from stack — algs4.cs.princeton.edu

The removed node is ready to be reclaimed by the garbage collector since no one referencing it.

— Is the stack empty?

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

Stack Implementation — Using Arrays

The stack class has an array of values(maybe integers, strings, ….), and an integer N that represents the number of items in the array.

public class ArrayStack {
    private String[] s;
    private int N = 0;
    
    public ArrayStack(int capacity){     
        s = new String[capacity];   // a cheat to keep it simple for now
    }
}

We need to pass the size of the array. This violates the idea of the stack which says it should be able to grow and shrink at any size. That’s why stacks not usually implement using a fixed size array.

— Implementing The Operations

A stack implemented using fixed size array — algs4.cs.princeton.edu

// Push an item to the end of the array
public void push(String item) { s[N++] = item; }
// Pop(and return) the item from the end of the array
public String pop()           { return s[--N]; }
// Is the stack empty?
public boolean isEmpty()      { return N == 0; }

Stack Consideration With Array Implementation

• Overflow: When the user tries to insert an item in a full stack. So, throw an exception, or use resizing array (it will be covered).
• Underflow: Throw exception if user tries to delete from an empty stack.
• Null items: Do we allow null items to be inserted? In this case yes, we do.
• Loitering: Holding a reference to an object when it’s no longer needed. When we remove an item(reference to an object) from the stack, we just decrement N, but, we don’t assign the item to null.

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

Now, the garbage collector can reclaim the object in the memory that was referenced by the removed item.

Stack Analysis— Linked List Vs Arrays

Time →With Linked List, the methods takes constant time, but it’s still not that efficient due to object declaration and dealing with links. While with Arrays, accessing the arrays is much faster; It takes O(1).

Memory →Linked Lists requires more memory because of the size of node objects(see figure below). While with arrays it requires less memory space.

The memory usage for our node object — algs4.cs.princeton.edu

Stack Applications

1. The back button in the web browser
2. Compiler
3. Arithmetic Operation (Dijkstra’s two-stack algorithm)
4. … and the list goes on.

Queues

The main operations of a queue are enqueue, dequeue, & isEmpty.

Queue Implementation — Using Linked List

The queue class has two reference variables; “first” points to the first inserted node, and “last” points to the last(most recently) inserted node.

public class LinkedQueue {
    private Node first = null, last = null;  
}

We also have an inner class called “Node” to represent each node within the queue (same as we did with stack implementation using linked list).

The terminology that we use is enqueue to insert an item, and dequeue to remove the first added one.

— Enqueue

Enqueue an item — algs4.cs.princeton.edu

If queue was empty before inserting an item, “first” should also reference to the newly created node, and therefore, “oldlast” will be null.

if(isEmpty()) first = last;
else          oldlast.next = last;

— Dequeue

Dequeue doesn’t just remove the first added item, it also returns it.

Dequeue an item — algs4.cs.princeton.edu

If queue is empty after removing an item, “last” should also reference to null.

if(isEmpty()) last = null;

— Is the queue empty?

return first == null;

Queue Implementation — Using Arrays

The queue class has an array of values(maybe integers, strings, ….), an integer N that represents the number of items in the array.

In addition to two integers, “head”(or first); points to the first inserted node in the array, and “tail”(or last); points to after the last inserted node.

Initially “head” and “tail” points to the first item in the array.

public class ArrayQueue {
    private String[] q;
    private int N = 0, head = 0, tail = 0;
    
    public ArrayQueue(int capacity){     
        q = new String[capacity];  // a cheat to keep it simple for now
    }
}

We need to pass the size of the array. This also violates the idea of the queue(same as with stacks).

— Implementing The Operations

A queue implemented using fixed size array — algs4.cs.princeton.edu

    // Enqueue an item
    public void enqueue(String item) { 
        q[tail++] = item; 
        N++;
    }
    // Dequeue(and return) the first inserted item
    public String dequeue() { 
        String item = q[head++];
        N--;
        return item;
    }
    // Is the queue empty?
    public boolean isEmpty()      { return N == 0; }
 }

Wrap-around

What if “tail” points to the end of the array, while array still have some null values(head is at index 6 for example). The next time we enqueue an item “tail” pointer will overflow! The same goes for “head” pointer. Both can overflow(as they move to the right), although array may still have empty slots.

So, one way to solve this is to wrap-around, meaning, whenever any pointer overflows(equals to array size), we reset it(point it to the first item in the array).

Wrap-around in a queue implemented with fixed size array — algs4.cs.princeton.edu

    public void enqueue(String item) { 
        q[tail++] = item; 
        N++;
        if (tail == q.length) tail = 0;    // wrap-around
    }
    public String dequeue() { 
        String item = q[head++];
        N--;
        if (head == q.length) head = 0;   // wrap-around
        return item;
    }

Queue Consideration With Array Implementation

It’s the same consideration already mentioned with Stack.

• Overflow & Underflow: We didn’t consider the situation when we insert in an item in a full queue, or remove an item from an empty queue.
• Null items: In this case, we allow user to insert null items.
• Loitering: We didn’t clear reference to objects that are no longer needed.

    public String dequeue() { 
        String item = q[head];
        q[head++] = null;                  // avoid loitering
        N--;
        if (head == q.length) head = 0;
        return item;
    }

Queue Analysis— Linked List Vs Arrays

Time →It’s same as with Stack using Linked Lists and Arrays.

Memory →It’s also same as with Stack using Linked Lists and Arrays. It just requires additional memory for the two pointers.

Resizing Arrays

In the previous array implementations, we pass the size of the array to the constructor.

In many situations we can’t know how big it’s, and this violates the idea of the stack and queue, which says it should be able to grow and shrink at any size.

So, we need to increase and decrease the size of the array. This requires to create a new array(resized) and copy the all the existing values into it.

Stack Implementation — Using Resizing Arrays

We will start by constructing an array with size 1.

public class ResizingArrayStack {
    private String[] s;
    private int N = 0;
    
    public ResizingArrayStack(){     
        s = new String[1];
    }
 }

— Push

When the array is full, create a new array of twice the size(repeated doubling), and copy the items, before actually inserting any new items.

    public void push(String item) { 
       // double size of array if full
       if (N == s.length) resize(2*s.length);
       s[N++] = item; 
     }

— Pop

After removing an item, If the array is 25% full out of total size, shrink the size of the array to it’s half by creating a new array with half the size, and copy all the old content.

    public String pop(){
        String item = s[--N];
        s[N] = null; 
        // shrink size of array to it's half if it's 1/4 full
        if(N > 0 && N == s.length/4) resize(s.length/2); 
        return item;
    }

— Resize

The resize method takes the size of the array as an argument, copy all existing values, and assign the stack array s[] to reference the resized array.

    // resize the underlying array to the given capacity
    private void resize(int capacity) {
        String[] copy = new String[capacity];
        for(int i = 0; i < N; i++)
            copy[i] = s[i];
        s = copy;
    }

One question may come into your mind, Why not to shrink the size of the array to it’s half when the array is 50% full?

Well, let’s say the size of array is 4, and N=4(array is full). Consider push, pop, push, pop, … sequence of operations. This sequence will double the size, shrink it, double it, shrink it, … . So, each operations will take time of N.

Too expensive in worst case — algs4.cs.princeton.edu

Queue Implementation — Using Resizing Arrays

We will start by constructing an array with size 1. In addition to the two pointers; “head ”and “tail”. We’ll grow and shrink the size of the queue the same as we did with stacks.

public class ResizingArrayQueue {
    private String[] q;
    private int N = 0, head = 0, tail = 0;
    
    public ResizingArrayQueue() {     
        q = new String[1]; 
    }
    public void enqueue(String item) { 
        // double size of array
        if (N == q.length) resize(2*q.length);
        q[tail++] = item; 
        N++;
        if (tail == q.length) tail = 0;
    }
    public String dequeue() { 
        String item = q[head];
        q[head++] = null;  
        N--;
        if (head == q.length) head = 0;
        // shrink size of array
        if (N > 0 && N == q.length/4) resize(q.length/2);
        return item;
    }
}

The resize method has some tricks, unlike in stacks. First, we copy all the existing items starting from “head ”pointer modulo the queue length(See “Wrap-around”). Second, reset the head and tail pointers to their correct positions in the resized array.

    // resize the underlying array
    private void resize(int capacity) {
        String[] copy = new String[capacity];
        for (int i = 0; i < N; i++) {
            copy[i] = q[(head + i) % q.length];
        }
        q = copy;
        head = 0;
        tail = N;
    }

Resizing Array Analysis

Time →The worst case is O(N) for inserting and deleting, because we may need to resize the array. The amortized case and best case is O(1) for both operations.

The average case takes a constant time for inserting (at the end) and deleting the last element.

Amortized time is the average time for sequence of operations in the worst case, and it’s not the same as average time.

The amortized time as result of inserting N items(N=8) in a resizing array with initial size of 1 = (1+2+4+1+8+1+1+1) / 8 ~= 2.

Memory →The memory usage is for the reference to an array, plus the array overhead, plus the memory needed to store the values. In addition to an integer N, and two integers head and tail (only in case of queue).

Trade-offs: Linked List Vs Resizing Array

I’m not going to include the array with fixed size in the comparison, as already mentioned that it violates the idea for both stacks and queues.

Linked List →It guarantees that every operation will take constant time in the worst case. But it uses extra time and space to deal with object creation and links.

Resized Arrays →Every operation takes O(1) amortized time, and less space needed.

The bottom line is, If you want to ensure that every operation will take a constant time, then use linked list.

However, If you just care about the total amount of time, then use resizing array, because although it may be slower when there are resizing operations, but the total time will be less, because individual operations are fast.