Data Structures: Stacks and Queues

Photo credit — Heather Barnes

The next topic I will be discussing are stacks and queues. Stacks and queues are also list based data structures. Stacks are useful when you care about the most recently added element. Stacks are known as last in, first out (FIFO). Stacks also keep track of the order in which elements are saved into the stack. On the other hand, queues are a first in, first out (FIFO) data structure. We add elements to the back of the queue (known as enqueue) and take elements from the front of the queue (known as dequeue). A real life representation of a queue is waiting in a line. Both stacks and queues can be effectively implemented using a linked list which I will be discussing next.

Implementing a Stack using a Linked List

Stacks have two operations, push and pop. Push is adding an element to the top of the stack and pop is removing the top element from the stack. Push and pop both occur in constant time, O(1). We can implement a stack using a linked list as follows.

class Stack {
   constructor() {
      this.head = null;
      this.numElements = 0;
   }
}
class Node {
   constructor(value, next = null) {
      this.value = value;
      this.next = next;
   }
}

We keep track of the number of elements in the stack. We can implement the push method as follows. If there is no head node, the new node is set to be the head node. Otherwise, the pointer for the new node is set to the old head node and the new node is set to be the new node.

Stack.prototype.push = function(value) {
   let newNode = new Node(value)
   if(!this.head) {
      this.head = newNode;
   } else {
      newNode.next = this.head;
      this.head = newNode;
   }
   this.numElements += 1;
}

We can implement the pop method as follows. If the stack is empty, we return nothing. We store the value of the head node. Then, we assign the head node to be the next node in the list and update the number of elements in the stack. Then, we return the value of the node removed.

Stack.prototype.isEmpty = function() {
   return this.numElements === 0;
}
Stack.prototype.pop = function() {
   if(this.isEmpty()) {
      return null;
   }
   let value = this.head.value;
   this.head = this.head.next;
   this.numElements -= 1;
   return value;
}

Implementing a Queue using a Linked List

Queues have two operations, enqueue and dequeue. Enqueue is adding an element to the tail of the queue. Dequeue is removing an element from the front of the queue. A queue is implemented as follows. Notice that a tail pointer is defined which we will use in implementing the enqueue method.

class Queue {
   constructor() {
      this.head = null;
      this.tail = null;
      this.numElements = 0;
   }
}
class Node {
   constructor(value) {
      this.value = value;
      this.next = null;
   }
}

So, how would we implement the enqueue method? If there is no head node, we set the head node to the new node and set the tail node to the head node. Otherwise, the next pointer for the tail node is set to the new node and the new node becomes the new tail node.

Queue.prototype.enqueue = function(value) {
   let newNode = new Node(value);
   if(!this.head) {
      this.head = newNode;
      this.tail = this.head;
   } else {
      this.tail.next = newNode;
      this.tail = this.tail.next;
   }
   this.numElements += 1;
}

We implement the dequeue method as follows. If the queue is empty, we return nothing. Otherwise, we store the value of the head node and we assign the head node to be the next node in the list. Then, we decrement the number of elements in the queue and return the value of the node removed.

Queue.prototype.dequeue = function() {
   if(!this.isEmpty()) {
      return null;
   }
   let value = this.head.value;
   this.head = this.head.next;
   this.numElements -= 1;
   return value;
}

Conclusion

Stacks and queues are fairly simple data structures to implement using linked lists. Stacks are last in, first out (LIFO) data structures and are like stacking books on a table. Queues are first in, first out (FIFO) data structures and are like waiting in a line. Implementing stacks and queues using linked lists allow the operations of adding and removing elements to occur in constant time. This is in contrast to arrays which would involve reassignment of indices. Stacks and queues have applications in many algorithms and tree traversal. I would like to acknowledge the data structures and algorithms class from Udacity that I referenced.