The Great SoluTion 🚀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
- Introduction
- Problem 1: Implement Stack using Queues
- Problem 2: Implement Queue using Stacks
- Problem 3: Valid Parentheses
- Problem 4: Decode String
- 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.
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.
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:
Stay tuned and happy coding 👨💻🚀
