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)$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 ?.

The above is the detailed content of LIFO or FIFO? Guide to Stacks/Queues. For more information, please follow other related articles on the PHP Chinese website!