Skip to content

README.md

Latest commit

 

History

History
122 lines (98 loc) · 9.72 KB

README.md

File metadata and controls

122 lines (98 loc) · 9.72 KB

05 - Stack + Queue

PHASE 5 — STACK + QUEUE (221–270)

Topics Covered

  • Stack and Queue Fundamentals
  • Monotonic Stack and Monotonic Queue
  • Deque-based Window Problems
  • Expression Parsing and Evaluation
  • Parentheses Matching
  • Design Problems with Queues and Stacks
  • Simulation Problems
  • Greedy Stack Processing

Problems List

No. Problem Difficulty Topics Link
1 Valid Parentheses Easy Stack, String Open
2 Min Stack Easy Stack, Design Open
3 Evaluate Reverse Polish Notation Easy Stack, Array Open
4 Generate Parentheses Easy Backtracking, Stack Open
5 Implement Queue using Stacks Easy Stack, Queue, Design Open
6 Implement Stack using Queues Easy Stack, Queue, Design Open
7 Next Greater Element I Easy Stack, Monotonic Stack Open
8 Online Stock Span Easy Stack, Monotonic Stack Open
9 Baseball Game Easy Stack, Array Open
10 Backspace String Compare Easy Stack, String Open
11 Queue using Array Easy Queue, Array Open
12 Stack using Array Easy Stack, Array Open
13 Balanced Brackets Easy Stack, String Open
14 Remove All Adjacent Duplicates Easy Stack, String Open
15 Min Add to Make Parentheses Valid Easy Stack, String Open
16 Reverse First K Elements of Queue Easy Queue, Recursion Open
17 Daily Temperatures Medium Stack, Monotonic Stack Open
18 Car Fleet Medium Stack, Sorting Open
19 Basic Calculator II Medium Stack, String Open
20 Next Greater Element II Medium Stack, Monotonic Stack Open
21 Asteroid Collision Medium Stack, Simulation Open
22 Decode String Medium Stack, String Open
23 Simplify Path Medium Stack, String Open
24 Remove K Digits Medium Stack, Greedy Open
25 Sum of Subarray Minimums Medium Stack, Monotonic Stack Open
26 Trapping Rain Water Medium Stack, Two Pointer Open
27 Design Circular Queue Medium Queue, Design Open
28 Design Circular Deque Medium Queue, Deque, Design Open
29 Final Prices With Discount Medium Stack, Monotonic Stack Open
30 Queue Reconstruction by Height Medium Queue, Greedy Open
31 Rotten Oranges Medium Queue, BFS Open
32 Maximum Nesting Depth Medium Stack, String Open
33 Remove Outermost Parentheses Medium Stack, String Open
34 Make The String Great Medium Stack, String Open
35 First Non-Repeating Character in Stream Medium Queue, Hash Table Open
36 Sliding Window Maximum Medium Deque, Sliding Window Open
37 Monotonic Stack Medium Stack, Monotonic Stack Open
38 Circular Tour Medium Queue, Greedy Open
39 Celebrity Problem Hard Stack, Two Pointer Open
40 Infix to Postfix Hard Stack, Expression Conversion Open
41 Postfix Evaluation Hard Stack, Expression Evaluation Open
42 Prefix Evaluation Hard Stack, Expression Evaluation Open
43 Sort Stack Recursively Hard Stack, Recursion Open
44 Recursive Queue Reversal Hard Queue, Recursion Open
45 Nearest Smaller Element Hard Stack, Monotonic Stack Open
46 Maximal Rectangle Hard Stack, Monotonic Stack, Matrix Open
47 Expression Evaluation Hard Stack, Parsing Open
48 Implement Deque Hard Queue, Deque, Design Open
49 Frequency Stack Hard Stack, Hash Table, Design Open

Important Patterns

Stack Fundamentals

  • LIFO structure for nested processing
  • Use for expression parsing, reversal, and backtracking support
  • Common operations: push, pop, peek

Queue Fundamentals

  • FIFO structure for ordered processing
  • Use for BFS, streaming, and scheduling problems
  • Support with arrays, linked lists, or circular buffers

Monotonic Stack

  • Maintain increasing or decreasing order
  • Great for next greater/smaller and histogram-style problems
  • Reduces many O(n^2) solutions to O(n)

Monotonic Queue / Deque

  • Maintain sliding-window min/max efficiently
  • Useful for window maximum and queue-based optimization
  • Supports both ends in O(1)

Expression Evaluation

  • Convert or evaluate infix, postfix, and prefix forms
  • Track operators, precedence, and operands carefully
  • Use stack recursion or parsing state

Parentheses Handling

  • Validate balanced brackets with stack or counters
  • Remove or transform invalid parentheses using greedy or BFS
  • Useful for nested structure parsing

Design with Stacks and Queues

  • Implement queue using stacks and stack using queues
  • Circular queue and deque require wrap-around logic
  • Frequency stack combines stack ordering with frequency counts

Simulation and Greedy Processing

  • Asteroid collision and car fleet use stack-based simulation
  • Remove K digits and adjacent duplicates use greedy stack pruning
  • Queue reconstruction often relies on sorting plus insertion order