LIFO or FIFO? Guide to Stacks/Queues

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Today, we're going to explore two essential data structures: stacks and queues. We'll dive into their concepts, use cases, and implement them in JavaScript using both classical and prototype-based approaches.

Stacks: Last In, First Out (LIFO)

Imagine a stack of pancakes – the last one you put on top is the first one you'll eat. That's exactly how a stack data structure works. It follows the Last In, First Out (LIFO) principle.

Key Operations

push(item): Add an item to the top of the stack
pop(): Remove the top item from the stack
peek(): Return the top item without removing it
isEmpty(): Check if the stack is empty

Use Cases

Stacks are particularly useful in scenarios involving:

Recursive algorithms
Undo mechanisms in text editors

JavaScript Implementation

Classical OOP

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

Prototype-Based

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};

Stack.prototype.size = function() {
  return this.items.length;
};

Stack.prototype.clear = function() {
  this.items = [];
};

Queues: First In, First Out (FIFO)

Now, let's shift our focus to queues. Unlike stacks, queues follow the First In, First Out (FIFO) principle. Think of a line at a concert venue – the first person to arrive is the first one to enter.

Key Operations

enqueue(item): Add an item to the end of the queue
dequeue(): Remove the first item from the queue
peek(): Return the first item without removing it
isEmpty(): Check if the queue is empty

Use Cases

Queues are commonly used in:

Breadth-first search algorithms
Task scheduling

JavaScript Implementation

Classical OOP

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

Prototype-Based

function Node(data) {
  this.data = data;
  this.next = null;
}

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

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

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

Performance Analysis

Both stacks and queues offer $O(1)$ time complexity for their core operations (push/pop for stacks, enqueue/dequeue for queues) when implemented efficiently. This makes them highly performant for their specific use cases.

They both provide elegant solutions to many common programming problems and form the basis for more complex data structures and algorithms. By understanding and implementing these structures in JavaScript, you're well-equipped to tackle a wide range of Leetcode/Algorithm problems 😎.

Blog

LIFO or FIFO? Guide to Stacks/Queues

Terrence Jung

Stacks: Last In, First Out (LIFO)

Key Operations

Use Cases

JavaScript Implementation

Classical OOP

Prototype-Based

Queues: First In, First Out (FIFO)

Key Operations

Use Cases

JavaScript Implementation

Classical OOP

Prototype-Based

Performance Analysis

Join Our Newsletter. No Spam, Only the good stuff.

Related