Queues and stacks are the simplest data structures that are built on the fundamental data structure, the array. A queue works based on the first-in, first-out (FIFO) principle, where an element is inserted to the end of the list and is removed from the front. Unlike a queue, a stack on the last-in, first-out (LIFO) principle. An element added to a list of elements will be the first to be removed.

Both data structures have the same time and space complexity.

Time complexity

• Insertion: O(1)
• Removal: O(1)
• Search and access: O(n) Space complexity O(n)

Queue implementation

We'll start with a simple and clean solution:

function Queue() {
  this.items = [];
};
Queue.prototype.enqueue = function(item) {
  this.items.push(item);
}
Queue.prototype.dequeue = function(item) {
  return this.items.shift(item)
}
Queue.prototype.size = function(item) {
  return this.items.length;
}
Queue.prototype.isEmpty = function () {
  return this.items.length == 0;
};

The above implementation does the job perfectly, however, can you spot what is wrong with the above solution?

We are using the shift native function which removes the first element in the array. This will move all elements in the array by one index for a total of n-times. The average and worst time complexity for this implementation is O(n).

So how can we improve this so the time complexity for insertion and removal is in constant time?

Our answer is a linked list. A linked list is a linear sequence of elements, where every element contains a reference to the next element.

Here is the implementation:

// The node which will take a value and the reference for the next node
function Node(value, next = null) {
  this.value = value
  this.next = next
}

function Queue() {
  this.head = null
  this.tail = null
  this.size = 0
}

Queue.prototype.isEmpty = function() {
  return this.size === 0
}

Queue.prototype.enqueue = function(value) {
  const node = new Node(value)

  if (!this.tail) {
    // head and tail will have the same initial node
    this.head = this.tail = node
  } else {
    // adds a node to end and move the tail to the next node
    this.tail.next = node
    this.tail = node
  }
  this.size++
}

Queue.prototype.dequeue = function() {
  if (!this.head) {
    return;
  }
  
  // removes the head and move the next mode to the front
  const last = this.head
  this.head = this.head.next;
  this.size--

  // set the tail to null if the head is null
  if (this.head == null) 
    this.tail = null; 

  return last.value;
}

We can now insert and remove elements in constant time!

Let's throw in a bonus search function:

Queue.prototype.search = function(value) {
  let found;
  
  let node = this.head
  while (!!node) {
    if (node.value === value) {
      found = node
      node = null
    } else {
      node = node.next
    }
  }

  return found;
}

Stack implementation

It's easier to implement a stack with native array functions that will adhere to the time and space complexity defined earlier.

function Stack() {
  this.items = [];
};
Stack.prototype.push = function(item) {
  this.items.push(item);
}
Stack.prototype.pop = function(item) {
  this.items.pop(item)
}
Stack.prototype.size = function(item) {
  return this.items.length;
}
Stack.prototype.search = function(item) {
  return this.items.find(item);
}
Stack.prototype.isEmpty = function(item) {
  return this.items.length == 0;
}

And why not add an implementation using linked list 🙂:

function Node(value, next = null) {
  this.value = value
  this.next = next
}

function Stack() {
  this.head = null
  this.size = 0
}

Stack.prototype.isEmpty = function() {
  return this.size === 0
}

// insert the value at the beginning of the list
Stack.prototype.push = function(value) {
  const node = new Node(value)
  node.next = this.head
  this.head = node
  this.size++
}

// remove and return the first element in the list
Stack.prototype.pop = function() {
  if (!this.head) {
    return;
  }
  
  const removed = this.head
  this.head = this.head.next;
  this.size--
  return removed.value;
}

Now, you should have a good understanding of these data structures and their complexities.