Algorithms + Data Structures: Stacks and Queues

🎨 Front End

Apr 25, 2023

3 min read

Stacks and Queues are similar but data retrieval is different. Here I discuss how they are different and how to approach questions are round these two topics.

Stacks

Think of a stack of cubes. Each cube is put on top of another. To retrieve a cube you must first remove the cube on the top. This is known as last in first out (LIFO).

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

  push(val) {
    return this.stack.push(item);
  }

  pop() {
    return this.stack.pop();
  }

  // return/peek at last item in stack
  peek() {
    return this.stack[this.length - 1];
  }

  getLen() {
    return this.stack.length;
  }

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

Queues

Like lining up in an orderly manner, a queue is no different. It uses the first in first out (FIFO) principle.

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

  enqueue(item) {
    return this.queue.unshift(item);
  }

  dequeue() {
    return this.queue.pop();
  }

  peek() {
    return thi.queue[this.length - 1];
  }

  getLen() {
    return this.queue.length;
  }

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

Problem Sets

Medium

Balanced Brackets

Write a function that takes in a string made up of brackets (, [, {, ), ], } and other optional characters. A string is said to be balanced if it has as many opening brackets of a certain type as it has closing brackets of that type and if no bracket is unmatched.

Sample Input

string = "([])(){}(())()()"

Sample Output

true

Code Given

function balancedBrackets(string) {
  // Write your code here.
}

Answer

function balancedBrackets(string) {
  const openingBrackets = "([{";
  const closingBrackets = ")]}";
  const matchingBrackets = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const char of string) {
    if (openingBrackets.includes(char)) {
      stack.push(char);
    } else if (closingBrackets.includes(char)) {
      if (stack.length == 0) {
        return false;
      }
      if (stack[stack.length - 1] === matchingBrackets[char]) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  return stack.length === 0;
}

Hard

Shortest Path

Write a function that takes in a non-empty string representing a valid unix-shell path and returns a shortened version of that path. A path is a notation that represents the location of a file or directory in a file system. A path can be an absolute path, meaning that it starts at the root directory in a file system, or a relative path, meaning that it starts at the current directory in a file system.

Sample Input

path = "/foo/../test/../test/../foo//bar./test"

Sample Output

"/foo/bar/test"

Code Given

function shortenPath(path) {
  // Write your code here.
}

Answer

function shortenPath(path) {
  const startsWithSlash = path[0] === "/";
  const tokens = path.split("/").filter(isImportantToken);
  const stack = [];
  if (startsWithSlash) stack.push(" ");
  for (const token of tokens) {
    if (token === "..") {
      if (stack.length === 0 || stack[stack.length - 1] === "..") {
        stack.push(token);
      } else if (stack[stack.length - 1] !== "") {
        stack.pop();
      } else {
        stack.push(token);
      }
    }
  }
  if (stack.length === 1 && stack[0] === "") return "/";
  return stack.join("/");
}

function isImportantToken(token) {
  return token.length > 0 && token !== ".";
}