🟨 JavaScript Q106 / 121

How do you implement a data structure like a stack or queue in JavaScript?

AI-Powered Answer ✓ Answered

Stacks and queues are fundamental linear data structures that store data sequentially. A stack operates on a Last-In, First-Out (LIFO) principle, while a queue operates on a First-In, First-Out (FIFO) principle. JavaScript's built-in `Array` object can be effectively used to implement both, providing convenient methods like `push()`, `pop()`, and `shift()`.

Implementing a Stack (LIFO)

A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. This means the last element added to the stack is the first one to be removed. Think of a stack of plates: you add new plates to the top, and you remove plates from the top.

javascript

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

  // Add an element to the top of the stack
  push(element) {
    this.items.push(element);
  }

  // Remove and return the top element from the stack
  pop() {
    if (this.isEmpty()) {
      return "Underflow"; // Or throw an error
    }
    return this.items.pop();
  }

  // Return the top element of the stack without removing it
  peek() {
    if (this.isEmpty()) {
      return null; // Or undefined
    }
    return this.items[this.items.length - 1];
  }

  // Check if the stack is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Return the number of elements in the stack
  size() {
    return this.items.length;
  }

  // Clear the stack
  clear() {
    this.items = [];
  }

  // Print the stack elements
  printStack() {
    return this.items.toString();
  }
}

In this implementation, push() adds an element to the end of the array (conceptually the top of the stack), and pop() removes an element from the end. peek() allows inspecting the top element without removal. isEmpty() and size() provide utility for checking the stack's state.

javascript

const myStack = new Stack();
console.log(myStack.isEmpty()); // true

myStack.push(10);
myStack.push(20);
myStack.push(30);

console.log(myStack.printStack()); // 10,20,30
console.log(myStack.peek());       // 30
console.log(myStack.size());       // 3

console.log(myStack.pop());        // 30
console.log(myStack.printStack()); // 10,20
console.log(myStack.isEmpty());    // false

Implementing a Queue (FIFO)

A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. This means the first element added to the queue is the first one to be removed. Think of a line at a supermarket: the first person in line is the first person to be served.

javascript

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

  // Add an element to the end of the queue
  enqueue(element) {
    this.items.push(element);
  }

  // Remove and return the front element from the queue
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow"; // Or throw an error
    }
    return this.items.shift(); // shift() removes from the beginning
  }

  // Return the front element of the queue without removing it
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[0];
  }

  // Check if the queue is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Return the number of elements in the queue
  size() {
    return this.items.length;
  }

  // Clear the queue
  clear() {
    this.items = [];
  }

  // Print the queue elements
  printQueue() {
    return this.items.toString();
  }
}

For a queue, enqueue() adds an element to the end of the array. The crucial part is dequeue(), which uses shift() to remove the element from the beginning of the array, ensuring the FIFO order. peek() returns the element at the front of the queue without removing it.

javascript

const myQueue = new Queue();
console.log(myQueue.isEmpty()); // true

myQueue.enqueue('Alice');
myQueue.enqueue('Bob');
myQueue.enqueue('Charlie');

console.log(myQueue.printQueue()); // Alice,Bob,Charlie
console.log(myQueue.peek());       // Alice
console.log(myQueue.size());       // 3

console.log(myQueue.dequeue());    // Alice
console.log(myQueue.printQueue()); // Bob,Charlie
console.log(myQueue.isEmpty());    // false

Performance Considerations and Alternatives

While JavaScript arrays are convenient for implementing both stacks and queues, it's worth noting that Array.prototype.shift() has a time complexity of O(n) because it re-indexes all subsequent elements after removing the first. For high-performance queue operations with a very large number of elements, a linked list-based implementation or a ring buffer might be more efficient, offering O(1) for both enqueue and dequeue. However, for most typical applications, the Array-based approach is simple, easy to understand, and performs well enough.

← All JavaScript questions