Cracking Stack and Queue LeetCode Problems: A Step-by-Step Guide to Solving LeetCode Challenges

Learning how to use stacks and queues effectively is an important skill for any developer, and it's a common topic in coding interviews 🎯. In this article, we'll go over some LeetCode problems that involve the use of stacks and queues, and we'll solve them using JavaScript 💻.

Welcome back to this new article in the DSA series 📚! If you've been following my articles up till last article, you'll notice that I've been going over the basic concepts of stacks and queues, how they work and the terminologies used when talking about them 🧠.

Table of Contents

1. Introduction
2. Problem 1: Implement Stack using Queues
3. Problem 2: Implement Queue using Stacks
4. Problem 3: Valid Parentheses
5. Problem 4: Decode String
6. Conclusion

Introduction

In the last two articles, we've gone over the basic concepts of stacks and queues 📚, how they work and the terminologies used when talking about them as well as their implementations in JavaScript. In this article, we'll be solving some problems on LeetCode that involves the use of stacks and queues using our implementations. Get ready to put your knowledge to the test and level up your coding skills! 🚀

Before we start cracking some problems, let's quickly remind ourselves the basic of queue and stack.

Stack: Think of a stack as a pile of books. You can only add or remove books from the top. Last In, First Out (LIFO).

For more information on stack, check out my previous article.

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

Emmanuel Ayinde ・ Oct 8

#beginners #javascript #dsa #datastructures

Queue: Imagine a line at a ticket counter. The first person in line is the first to be served. First In, First Out (FIFO).

For more information on queue, check out my previous article.

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

Emmanuel Ayinde ・ Oct 9

#beginners #javascript #dsa #programming

Now that we've refreshed our memories, let's go over some problems. Shall we?

Problem 1: Implement Stack using Queues

Problem Link: LeetCode - Implement Stack using Queues

Explanation:

We need to implement a stack using only queue operations. The main challenge is that queues follow FIFO, while stacks follow LIFO.

Approach:

We'll use two queues. When pushing an element, we'll add it to the first queue and then move all other elements behind it.

Solution:

class MyStack {
  constructor() {
    this.queue1 = [];
    this.queue2 = [];
  }

  push(x) {
    // Add the new element to queue2
    this.queue2.push(x);

    // Move all elements from queue1 to queue2
    while (this.queue1.length > 0) {
      this.queue2.push(this.queue1.shift());
    }

    // Swap queue1 and queue2
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
  }

  pop() {
    return this.queue1.shift();
  }

  top() {
    return this.queue1[0];
  }

  empty() {
    return this.queue1.length === 0;
  }
}

Problem 2: Implement Queue using Stacks

Problem Link: LeetCode - Implement Queue using Stacks

Explanation:

We need to implement a queue using only stack operations. The challenge is to convert LIFO (stack) behavior to FIFO (queue) behavior.

Approach:

We'll use two stacks. One for enqueue operations and another for dequeue operations.

Solution:

class MyQueue {
  constructor() {
    this.stack1 = []; // For enqueue
    this.stack2 = []; // For dequeue
  }

  push(x) {
    this.stack1.push(x);
  }

  pop() {
    if (this.stack2.length === 0) {
      this.transferStack1ToStack2();
    }
    return this.stack2.pop();
  }

  peek() {
    if (this.stack2.length === 0) {
      this.transferStack1ToStack2();
    }
    return this.stack2[this.stack2.length - 1];
  }

  empty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }

  transferStack1ToStack2() {
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
}

Problem 3: Valid Parentheses

Problem Link: LeetCode - Valid Parentheses

Explanation:

We need to determine if the input string has valid parentheses, meaning every opening bracket must have a corresponding closing bracket in the correct order.

Approach:

We'll use a stack to keep track of opening brackets and check if they match with closing brackets.

Solution:

const isValid = (s) => {
  const stack = [];
  const bracketPairs = {
    ")": "(",
    "}": "{",
    "]": "[",
  };

  for (let char of s) {
    if (!bracketPairs[char]) {
      // It's an opening bracket, push to stack
      stack.push(char);
    } else {
      // It's a closing bracket
      if (stack.pop() !== bracketPairs[char]) {
        return false;
      }
    }
  }

  // If stack is empty, all brackets were matched
  return stack.length === 0;
};

Problem 4: Decode String

Problem Link: LeetCode - Decode String

Explanation:

We need to decode a string that contains repeated substrings enclosed in square brackets, preceded by a number indicating the repetition count.

Approach:

We'll use two stacks: one for numbers and another for characters. We'll build the decoded string piece by piece.

Solution:

const decodeString = (s) => {
  const numStack = [];
  const strStack = [];
  let currentNum = 0;
  let currentStr = "";

  for (let char of s) {
    if (char >= "0" && char <= "9") {
      currentNum = currentNum * 10 + parseInt(char);
    } else if (char === "[") {
      numStack.push(currentNum);
      strStack.push(currentStr);
      currentNum = 0;
      currentStr = "";
    } else if (char === "]") {
      let repeatTimes = numStack.pop();
      let prevStr = strStack.pop();
      currentStr = prevStr + currentStr.repeat(repeatTimes);
    } else {
      currentStr += char;
    }
  }

  return currentStr;
};

Conclusion

In this blog post, we've explored the fundamental concepts of Queues and Stacks and solved several LeetCode problems that showcase their implementation and use cases. By working through these problems, you've gained valuable insight into how these data structures can be applied to solve complex coding challenges.

---

---

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding 👨‍💻🚀