Data Structures & Algorithms·Reason about cost and structure

Stacks and queues

Restricting where insertion and removal happen makes some problems simple.

Intermediate 13 min read Lesson 8 of 300 Challenge included

What you will be able to do

A stack can validate balanced brackets in one pass.
A queue explores level by level in BFS.
Choose the data structure before the loop.

In plain English

A stack is last-in, first-out; a queue is first-in, first-out. Use a stack for undo, parsing and depth-first traversal. Use a queue for scheduling and breadth-first traversal. In JavaScript, shift on a large array is O(n), so use a deque or index for queues.

brackets.jsJavaScript

function balanced(text) {
  const pairs = { ')': '(', ']': '[', '}': '{' }
  const stack = []

  for (const char of text) {
    if ('([{'.includes(char)) stack.push(char)
    else if (char in pairs) {
      if (stack.pop() !== pairs[char]) return false
    }
  }
  return stack.length === 0
}

Your turn

Validate brackets

Medium

Use a stack to return false for the string "([)]" and true for "([])".

JS · starter

function balanced(text) {}

Check your understanding before moving on.

Knowledge checkQuestion 1

Which order does a queue process items?

Select an answer to continue

Study tools

Make it yours.

Keep a private note for this lesson, then turn the key ideas into flashcards you can revisit.

Sign in to save notes and flashcards.Both are private to your account and stay with your progress.

Finished reading?

Lock in what you just learned.

Mark this lesson complete to save your place and move one step closer to the certificate.

Next: Hash maps and frequency counting

Lesson 8 of 300 · 0% of course