Jaconir

Stacks & Queues: Orderly Data

Learn about two fundamental data structures that manage collections of items in a specific order.

What Is a Stack? (LIFO)

A stack is a "Last-In, First-Out" (LIFO) data structure. Imagine a stack of plates: the last plate you put on top is the first one you take off. Stacks have two primary operations:

  • Push: Adds an item to the top of the stack.
  • Pop: Removes the item from the top of the stack.

This structure is incredibly useful for tasks like managing function calls (the call stack) in programming, implementing the "undo" functionality in an editor, or handling a browser's back-button navigation history.

What Is a Queue? (FIFO)

A queue is a "First-In, First-Out" (FIFO) data structure. Think of a line at a grocery store: the first person to get in line is the first person to be served. Queues have two main operations:

  • Enqueue: Adds an item to the back of the queue.
  • Dequeue: Removes the item from the front of the queue.

In frontend development, this concept is similar to the browser's event loop, which processes user interactions (like clicks) and rendering updates in the order they are received. It's also used for breadth-first search in graph algorithms.

Interactive Stack (LIFO)
Last-In, First-Out. Think of a stack of plates.
C
B
A
Interactive Queue (FIFO)
First-In, First-Out. Think of a checkout line.
FRONT
A
B
C
BACK
Problem: Valid Parentheses
Use a stack to determine if a string of parentheses is valid (e.g., \`()\`, \`[]\`, \`()\`).
{[()]}
Start with an empty stack.
function isValid(s) {
  const stack = [];
  const map = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (map[char]) {
      stack.push(char);
    } else {
      if (stack.length === 0) {
        return false;
      }
      const lastOpen = stack.pop();
      if (map[lastOpen] !== char) {
        return false;
      }
    }
  }

  return stack.length === 0;
}
Coding Challenge
Given a string `s` containing just the characters `(`, `)`, `{`, `}`, `[` and `]`, determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and open brackets must be closed in the correct order.
Quick Quiz: Test Your Knowledge

A web browser's "Back" button functionality is best implemented using a:

A print queue that prints jobs in the order they were submitted is an example of a:

A function call stack in a programming language follows which principle?

Go Deeper with "Cracking the Coding Interview"

For a comprehensive guide to data structures like stacks and queues and the interview problems associated with them, "Cracking the Coding Interview" by Gayle Laakmann McDowell is an essential resource.

View on Amazon

Previous

Linked Lists

Next

Hash Tables