Cracking LeetCode Stacks and Queues Issues: A Step-by-Step Guide to Solving LeetCode Challenges

Learning to handle 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 discuss some LeetCode problems using stacks and queues and solve them using JavaScript 💻.

Welcome back to this new article in the DSA series 📚! If you have been following my articles until the last article, you will notice that I have discussed the basic concepts of stacks and queues, how they work and the terminologies used when I talk about them 🧠.

Table of contents

1. Introduction
2. Issue 1: Deploying Stack using Queues
3. Problem 2: Implementing queue using stacks
4. Problem 3: Valid parentheses
5. Problem 4: Decoding string
6. Conclusion

Introduction

In the last two articles we discussed 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 solve some issues on LeetCode related to the use of stacks and queues using our implementations. Get ready to put your knowledge to the test and take your coding skills to the next level! 🚀

Before we start solving some problems, let’s quickly remind ourselves of the basics of queuing and stacking.

Pile: Think of a stack as a stack of books. You can only add or remove books from the top. Last in, first out (LIFO).

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

Queue: Imagine a line at a ticket counter. The first person in line is served first. First in, first out (FIFO).

For more information about the queue, check out my previous article.

Now that we’ve refreshed our memories, let’s discuss some of the issues. Shall we?

Issue 1: Deploy Stack using queues

Problem Link: LeetCode – Implement Stack using queues

Explanation:

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

Approximation:

We use two queues. When we push an element, we add it to the first queue and then move all the 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: Implementing queue using stacks

Problem Link: LeetCode – Implement queue using stacks

Explanation:

We need to implement a queue with only stack operations. The challenge is to convert LIFO behavior (stacking behavior) into FIFO behavior (queuing behavior).

Approximation:

We use two stacks. One for queuing and another for dequeuing.

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, which means that each opening parenthesis must have a corresponding closing parenthesis in the correct order.

Approximation:

We use a stack to keep track of the opening parentheses and check whether they match the closing parentheses.

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: Decoding string

Problem Link: LeetCode – Decode string

Explanation:

We need to decode a string containing repeated substrings enclosed in square brackets, preceded by a number indicating the number of repetitions.

Approximation:

We use two stacks: one for numbers and one for characters. We will 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 explored the fundamental concepts of queues and stacks and solved several LeetCode problems showing their implementation and use cases. By solving these problems, you have gained valuable insight into how these data structures can be applied to solve complex coding challenges.

Stay informed and connected

To ensure you don’t miss any part of this series and to contact me for more in-depth discussions on software development (web, server, mobile or scraping/automation), data structures and algorithms and other exciting technical topics, follow I on:

Stay tuned and happy coding 👨‍💻🚀