DSA Sheet - Day 13 Stacks and Queues

🚀 DSA Sheet – Day 13: Stacks & Queues (Part 1)

Stacks and Queues are fundamental data structures used in many advanced problems. This set introduces monotonic stack, simulation techniques, and classic patterns.

📊 Progress Tracker

Progress: 0 / 6 Completed

Done	Problem	Practice	Level	Companies
	Implement Stack using Queue	Solve	Easy	Amazon, Oracle
	Next Greater Element I	Solve	Easy	Meta, Apple
	Implement Queue using Stack	Solve	Easy	Microsoft, Uber
	Valid Parentheses	Solve	Easy	Google, JP Morgan
	First Non-Repeating Character in Stream	Solve	Easy	Meta, Adobe
	Reverse First K Elements of Queue	Solve	Easy	TCS

🧠 Key Approaches

• Stack using Queue: Either make push costly or pop costly
• Next Greater Element: Use Monotonic Stack
• Queue using Stack: Use two stacks (input/output)
• Valid Parentheses: Stack matching
• First Non-Repeating: Queue + frequency map
• Reverse K Elements: Stack + queue rotation

⚡ Quick Cheatsheet

Next Greater Element

stack st;

for(int i = n - 1; i >= 0; i--){
  while(!st.empty() && st.top() <= arr[i]) 
    st.pop();

  ans[i] = st.empty() ? -1 : st.top();

  st.push(arr[i]);
}
    

Valid Parentheses

stack st;

for(char c : s){
  if(c == '(' || c == '{' || c == '[') 
    st.push(c);
  else {
    if(st.empty()) return false;

    st.pop();
  }
}
    

Queue using Stacks

stack s1, s2;

// push in s1
// for pop:
// if s2 empty → transfer all from s1 to s2
// then pop from s2
    

🔥 Pro Tip

Stack & Queue problems revolve around patterns:

• Monotonic Stack (Next Greater/Smaller)
• Simulation using two data structures
• Order preservation (FIFO vs LIFO)

Once you recognize the pattern, most problems become straightforward.

🏠 All Days ⬅ Previous Next ➡