Generic Stack and Queue using Linked List and resizing Array

Stacks and Queues are one of the most basic and important data structures widely used in computer science. Understanding the operational semantics of these data structures will reward anyone. Going a step ahead and understanding the inner workings of these structures will lighten with much more knowledge. Once the mechanics of these data structures are well understood, trying to build a custom one using other foundational data structures will be a challenge. Leaping one more step ahead to build a generic version of stack and queue using the same foundational structures will not be a very easy task to do, but if you do, it sure will adorn your cerebral cortex.

This post focusses on building a generic stack and queue using two foundational structures - linked list and array. So there are going to be 4 different types of implementation.
1) Build a stack using Linked List
2) Build a stack using resizing array
3) Build a queue using Linked list
4) Build a queue using resizing array

Generic Datastructure
Stack is a LIFO data structure and Queue is a FIFO data structure. To understand more about these, I would recommend to google. A generic data structure is more like a container for any type of java object. The data structure should not depend on the type of object that one needs to use with it. The object can be anything. It is not a healthy practice to build a data structure for every type of object that you want to use with it.

The semantics of a linked list is different from an array because linked list allows accessing any element traversing from the first element while an array allows random access based on the index of the element. Underlying rules like these, pose a challenge for a developer to construct a stack or queue using the foundational structures.

The below illustrated "isEmpty" and "iterator" methods are common for both Stacks and queues. As the name illustrates, isEmpty tells whether the structure is empty and the iterator method returns an iterator to run through the elements. The beauty is that a user does not need to understand the underlying data structure if he has to iterate through the elements.

Following is the code snippet for all the above mentioned data structures. Most part of the code is not that difficult to understand though I have some inline comments wherever I felt some explanation is necessary.

Stack using Linked List
A single linked list always has a series of elements chained together. Every element has data and a reference to the next element. The first element is called head and the last element in the chain is called tail. That in turn does not mean all the data structures that are built using linked list need to have 2 references internally maintained for head and tail. It is totally up to the data structure that is built out of linked list. Take for example, the stack needs to internally preserve just one reference which is "head", so that it can perform its day to day work. This is because both operations “push” and “pop” that are exposed from a stack happens from the top aka head element. Push adds a new element at the head and pop returns and removes the element at the head of the linked list.

/**
  * Returns true or false based on whether the stack is empty or not
  * @return boolean
  */
 public boolean isEmpty() {
  return (null == head);
 }

/**
  * Push data to stack
  * @param data
  * @return true if push was successful else false
  */
 public boolean push(T data) {
  if (null != data) {
   Element prevHead = head;
   head = new Element();
   head.data = data;
   head.next = prevHead;
   return true;
  } else {
   return false;
  }
 }
 
 /**
  * Pops data from stack
  * @return data if pop was successful else null
  */
 public T pop() {
  if (!isEmpty()) {
   T data = head.data;
   head = head.next;
   return data;
  } else {
   return null;
  }
 }

The following iterator helps to run through the elements in the stack

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

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

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

   @Override
   public void remove() {
   }
  };
}

Here is the github link to the code for Stack built using Linked List - Github - Stack using Linked List

Stack using resizing Array
Stack using array might look simple at the first sight. However, it is definitely not if you are implementing a self-resizing array. A self-resizing array is the one that can modify its size based on the usage. This ensures an optimum usage of memory based on the number of elements in the stack.

Push operation always happens at the end of the array. It is not a good idea to add the new element at the first index because a stack is a FIFO data structure. The new element needs to be added to the end of array and the actual number of elements in the stack is maintained internally in a variable. The stack needs to be resized to twice its capacity if it was found to be already full. This in turn means that for N elements added to the stack, the array needs to be resized logarithmic times.

 /**
  * Returns true if the stack is empty
  * @return
  */
 public boolean isEmpty() {
  return (n == 0);
 }

/**
  * Pushes object to stack. Resizes if needed.
  * Note that resize operation happens before push.
  * @param data
  * @return
  */
 public boolean push(T data) {
  if (null != data) {
   if (n == list.length) {
    resize(list.length * 2);
   }
   list[n++] = data;
   return true;
  } else {
   return false;
  }
 }

 /**
  * Resizes the existing stack by creating a new stack
  * and copying all the elements from existing stack.
  * 
  * In case of a growing stack, the source of data is small
  * In case of a shrinking stack, the new target is small
  * And so the copying operation has been restricted to number of elements
  * 
  * @param capacity
  */
 private void resize(int capacity) {
  T[] newlist = (T[]) new Object[capacity];
  for (int i = 0; i < n; i++) {
   newlist[i] = list[i];
  }
  list = newlist;
 }

Pop operation always happens from the last element as that is the most recently added element to the stack. After a pop is complete, the stack is resized to a half of its capacity if the utilization is found to be quarter or less than the current capacity.

 /**
  * Pops out from stack. Resizes if needed.
  * Note that resize operation happens after pop.
  * @return
  */
 public T pop() {
  if (!isEmpty()) {
   T data = list[--n];
   list[n] = null;
   if (n <= list.length/4 && n > 0) {
    // resize the stack if the utilization is lesser than or equal to quarter of the capacity
    // not needed to resize if number of elements in stack was 1 and that element was popped (the new n will be 0 then)
    resize(list.length/2);
   }
   return data;
  } else {
   return null;
  }
 }

The following iterator helps to run through the elements in the stack

 @Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   // as array data structure stores in the order of push but stack is a LIFO data structure
   // the iterator runs reverse
   private int i = (n-1);
   
   @Override
   public boolean hasNext() {
    return (i >= 0);
   }
   
   @Override
   public T next() {
    return list[i--];
   }

   @Override
   public void remove() {
    
   }
  };
 }

Here is the github link to the code for Stack built using Array - Github - Stack using Resizing Array

Queue using Linked List
Queues using linked list needs two references – "head" pointing to the first element of the queue and "tail" pointing to the last element of the queue. Enqueue adds an element to the end of the queue and dequeue returns and removes an element from the start of the queue.

The enqueue operation has a special case when the first element is added to an empty queue. When the queue has just one element, both head and tail need to point to the same element which will be the first element in the queue.

/**
  * Returns true or false based on whether the queue is empty or not
  * @return boolean
  */
 public boolean isEmpty() {
  return (null == head);
 }

/**
  * Enqueues or adds the element to the end of queue
  * If the queue is empty before enqueue, the head and tail of the queue will point to the new element enqueued
  * @param data
  * @return true if enqueue was successful else false
  */
 public boolean enqueue(T data) {
  if (data != null) {
   Element prevTail = tail;
   tail = new Element();
   tail.data = data;
   tail.next = null;
   if (isEmpty()) {
    head = tail;
   } else {
    prevTail.next = tail;
   }
   return true;
  } else {
   return false;
  }
 }

Dequeue has a special case as well. When the queue becomes empty after the last element is dequeued, the head and tail references should point to null.

/**
  * Dequeues element from the start of the queue and returns the element's data. Returns null if there are no elements in queue.
  * If the queue is empty after a successful dequeue, head and tail will be reset to null
  * @return
  */
 public T dequeue() {
  if (!isEmpty()) {
   T data = head.data;
   head = head.next;
   if (isEmpty()) {
    tail = head;
   }
   return data;
  }
  return null;
 }

The iterator is simple for a queue built using linked list. It has to run from the first element to the end.

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

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

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

   @Override
   public void remove() {
    
   }
  };
 }

Here is the github link to the code for Queue built using Linked List - Github - Queue using Linked List

Queue using resizing Array
Queue using array is possible using two indexes – headIndex and a tailIndex. headIndex points to the first valid element in the queue. Remember a dequeue operation removes the element from the head. So a dequeue operation can leave "holes" in the queue. tailIndex points to the last valid element in the queue. This in turn means that the length of the queue will be the tailIndex value. Not to forget that the underlying array has to be resized for an optimal usage of memory.
A push operation happens at the tailIndex. If the queue is full, the capacity is resized to twice

 /**
  * Returns true if queue is empty
  * @return
  */
 public boolean isEmpty() {
  return (0 == tailIndex);
 }

/**
  * Enqueues to queue, resizes if needed
  * @param data
  * @return
  */
 public boolean enqueue(T data) {
  if (data != null) {
   if (!isEmpty()) {
    // queue is full
    if ((tailIndex - headIndex) == list.length) {
     resize(2*list.length);
    }
   }
   // if the queue is empty or if the queue is not full
   list[tailIndex++] = data;
   return true;
  } else {
   return false;
  }
 }


 /**
  * Resizes the queue to the provided capacity
  * @param capacity
  */
 private void resize(int capacity) {
  T[] newlist = (T[]) new Object[capacity];
  int i = headIndex;
  int j = 0;
  for (; i < tailIndex; i++, j++) {
   newlist[j] = list[i];
  }
  headIndex = 0;
  tailIndex = j;
  list = newlist;
 }

A pop operation pops an element from the head of the queue. After the operation, if the utilization of the queue is found to be quarter the capacity or lesser, then the current capacity is resized to half. The queue need not be resized if the length of the queue is already 1. It is ok to have a space readily available for the first element of the queue.

/**
  * Dequeues from queue, resizes if needed
  * @return
  */
 public T dequeue() {
  if (!isEmpty()) {
   T data = list[headIndex];
   list[headIndex++] = null;
   if ( ((tailIndex - headIndex) <= list.length/4) && list.length > 1) {
    // resize the queue to half it's capacity, if the utilization is lesser than or equal to quarter of the capacity
    // do not resize if number of elements in queue was 1 and that element was dequeued (the new number of elements will be 0 then)
    resize(list.length/2);
   }
   return data;
  } else {
   return null;
  }
 }

The iterator for a queue built using array is not difficult as the iteration has to run from the element at headIndex to tailIndex.

@Override
 public Iterator<T> iterator() {
  return new Iterator<T>() {
   
   private int i = headIndex;
   
   @Override
   public boolean hasNext() {
    return (i < (tailIndex - headIndex));
   }

   @Override
   public T next() {
    return list[i++];
   }

   @Override
   public void remove() {
   }
  };
 }

Here is the github link to the code for Queue built using array - Github - Queue using Resizing Array

Feel free to download or browse through the entire source for this project from github repository - Github - Basic Datastructures