Stacks and Queues

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

OMAR ELGABRY
Jan 6, 2017 · 9 min read

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 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

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 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

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

  • 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

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. Compiler
  2. Arithmetic Operation (Dijkstra’s two-stack algorithm)
  3. … and the list goes on.

Queues

Queue Implementation — Using Linked List

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 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

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

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

  • 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

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 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

public class ResizingArrayStack {
private String[] s;
private int N = 0;

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

— Push

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

— Pop

    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

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

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

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

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.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

OMAR ELGABRY

Written by

Software Engineer. Going to the moon 🌑. When I die, turn my blog into a story.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade