Reverse a string / queue using a stack; check balanced parentheses
Problem
Three warm-ups that show how a stack works: reverse a string with a stack; reverse a queue with a stack; check that a string of brackets is balanced.
Example 1
Input: reverse "stack" Output: "kcats"
Example 2
Input: balanced? "[()]{}"
Output: trueAlso asked as: Reverse a String using Stack · Reverse a Queue using recursion · Check the expression has valid or Balanced parenthesis or not
Test cases
Case 1
Input: "[()]{}"
Expected: trueCase 2
Input: "([)]" Expected: false
Case 3
Input: "(("
Expected: falseCase 4
Input: ")" Expected: false
Case 5
Input: "" Expected: true
View solutionHide solution1 approach
1. Stack fundamentals
Time O(n)Space O(n)
Push all characters/elements and pop them to reverse. For balanced parentheses, push openers and match each closer against the stack top. To reverse a queue recursively: dequeue the front, recurse, then enqueue the saved front at the back.
const reverseWithStack = (s) => { const st = [...s]; let r = ''; while (st.length) r += st.pop(); return r; };
function isBalanced(s) { const pair = { ')': '(', ']': '[', '}': '{' }, st = []; for (const c of s) { if ('([{'.includes(c)) st.push(c); else if (st.pop() !== pair[c]) return false; } return st.length === 0;}
function reverseQueue(q) { if (q.length === 0) return; const front = q.shift(); reverseQueue(q); q.push(front);}