STACK
1. Stack Implementation CODE
Steps: class Stack {
public:
Stack Implementaion:-
*create Stack int *arr; =>dynamic array kai liyai pointer use kisya hai
*push()
*pop() int size;
*isEmpty() int top;
*getTop()
*getSize() Stack(int size) =>for stack create
arr = new int[size];
this->size = size;
this->top = -1;
void push(int data) =>for insert data
if (top == size - 1)
cout << "Stack overflow" << endl;
else
top++;
arr[top] = data;
void pop()
if (top == -1)
cout << "Stack underflow" << endl;
else
top--;
bool isEmpty()
if (top == -1) return true;
else return false;
int getTop()
if (top == -1)
cout << "Stack is empty" << endl;
else
return arr[top];
int getSize()
return top + 1;
};
Int main()
Stack st(8); =>creation(static way of creation)
[Link](10);
[Link](20);
2. Reverse String By Stack ↗ CODE
Remember Points: string str = "hellojee";
stack<char> st;
for(int i = 0; i<[Link](); i++) =>push char in stack
[Link](str[i]);
while( ![Link]() ) =>pop & print char from stack
cout<<[Link]();
[Link]();
3. Find Middle Element of Stack CODE
Remember Points: →void solve(stack<int> &st, int& pos, int &ans)
=>Base Case if(pos == 1) {
ans = [Link]();
[Link]();
return;
=>1 case hum solve krna hai pos--;
int temp = [Link]();
[Link]();
=>recursion solve(st,pos,ans);
=>backtrack [Link](temp);
→int getMiddleElement(stack<int> &st)
int size = [Link]();
if([Link]())
cout << "Stack is empty, no middle";
return -1;
else { =>stack is not empty
int pos = 0;
if(size & 1) pos = size/2 + 1; =>odd
else pos = size/2; =>even
int ans = -1;
solve(st,pos,ans);
return ans;
4. Insert At Bottom of Stack CODE
Remember Points: →void insertAtBottom(stack<int> &st, int &element
=>base case if ([Link]()) {
[Link](element);
return;
=>1 case hum solve krna hai int temp = [Link]();
[Link]();
=>baaaki recursion insertAtBottom(st, element);
=>backtrack [Link](temp);
5. Reverse a Stack(reverse elemnt with the pattern recursion) CODE
Remember Points: →void reverseStack(stack<int> &st) {
=>base case if ([Link]()) return;
=>1 case hum solve krna hai int temp = [Link]();
[Link]();
=>recursion reverseStack(st);
=>backtrack insertAtBottom(st, temp);
6. Insert in a Sorted Stack CODE
Remember Points: →void insertSorted(stack<int> &st, int element)
=>base case if([Link]() || element > [Link]())
[Link](element);
return;
=>1 case hum solve krna hai int temp = [Link]();
[Link]();
=>recursion sambhalega insertSorted(st,element);
=>backtrack [Link](temp);
7. Sort a Stack CODE
Remember Points: →void sortStack(stack<int> &st)
=>base case if([Link]()) return;
=>1 case hum solve krna hai int temp = [Link]();
[Link]();
=>baaaki recursion sortStack(st);
=>backtrack insertSorted(st, temp);
8. Implemented 2 Stack in an Array CODE
First Approach: Divide Array in 2 Equal Parts
NOTE: If stack is full & stack 2 is empty. And I want insert data then I don’t insert data even stack2 is empty. Memory wastage
Second Approach: Efficient Space Utilization
class Stack {
public:
int *arr;
int size;
int top1;
int top2;
Stack(int size)
arr = new int[size];
this->size = size;
top1 = -1;
top2 = size;
void push1(int data)
if(top2-top1 == 1) no space available
cout<<"OVERFLOW"<<endl;
else
top1++;
arr[top1] = data;
void push2(int data) {
if(top2-top1 == 1)
cout<<"OVERFLOW"<<endl;
else
top2--;
arr[top2] = data;
void pop1()
if(top1 == -1) stack1 is empty
cout<<"UNDERFLOW";
else
arr[top1] = 0;
top1--;
void pop2() {
if(top1 == size)
cout<<"UNDERFLOW";
else
arr[top2] = 0;
top2++;
};
9. Leetcode 20 Valid Parentheses ↗ CODE
Input: s = "(]" Output: false Input: s = "([])" Output: true
Remember Points: stack<char> st;
for(int i = 0; i<[Link](); i++)
char ch = s[i];
Step1: If an opening bracket ('(', '{', '['), push into the stack if(ch == '(' || ch == '{' || ch == '[')
[Link](ch);
Step2: If a closing bracket (')', '}', ']'), check else{
Step2.1: If the stack is empty → Return false (invalid case). if(![Link]())
Step2.2 check if the top of the stack matches the correct opening bracket. if(ch == ')' && [Link]() == '(')
If not, return [Link] it matches, pop the stack [Link]();
else if(ch == '}' && [Link]() == '{')
[Link]();
else if(ch == ']' && [Link]() == '[')
[Link]();
else
return false; =>no match
else
return false;
Step3:At the end if stack is empty the string is valid return ([Link]()) ? true : false;
10. Remove Redundant Brackets(Present Redundant or not) CODE
Input: s = (a+(b)) Output: true Input: s = (a+(b*c)) Output: false
Remember Points: for (int i = 0; i < [Link](); i++)
Step1: Push operator & opening brackets if (ch == '(' || ch == '+' || ch == '-' || ch == '*' || ch == '/' )
[Link](ch);
Step2: If closing bracket found then, count operator else if(ch == ')')
and pop until ( found and last check int operatorCount = 0;
operatorCount == 0 return true while ([Link]() != 0 && [Link]() != '(') {
char temp = [Link]();
if (temp == '+' || temp == '-' || temp == '*' || temp == '/')
operatorCount++;
[Link]();
[Link]();
if (operatorCount == 0) return true;
return false
11. Leetcode 155. Min Stack ↗ CODE
Remember Points: vector<pair<int,int> >st;
MinStack() { }
void push(int val)
=>i am inserting first element if([Link]())
pair<int, int> p;
[Link] = val;
[Link] = val;
st.push_back(p);
else
pair<int, int> p;
[Link] = val;
int puranaMin = [Link]().second;
[Link] = min(puranaMin, val);
st.push_back(p);
void pop()
st.pop_back();
int top()
pair<int, int> rightmostPair = [Link]();
return [Link];
int getMin()
pair<int, int> rightmostPair = [Link]();
return [Link];
12 Next Smaller Element CODE
Input: [8, 4, 6, 2, 3] Output: [4, 2, 2, -1, -1]
Steps: vector<int> nextSmallerElement(int arr[], int size, vector<int> &ans) {
stack<int> st;
[Link](-1);
for(int i = size-1; i >= 0; i--) {
int curr = arr[i];
while([Link]() >= curr)
[Link]();
ans[i] = [Link]();
[Link](curr);
}
return ans;
}
13 Previous Smaller Element
Input: [8, 4, 6, 2, 3] Output: [-1, -1, 4, -1, 2]
Steps: vector<int> prevSmallerElement(int arr[], int size, vector<int> &ans){
stack<int> st;
[Link](-1);
for(int i = 0; i<size; i++){
int curr = arr[i];
while([Link]() >= curr)
[Link]();
ans[i] = [Link]();
[Link](curr);
}
return ans;
}
14. Leetcode 84 Largest Rectangle in Histogram ↗
15. Leetcode 496. Next Greater Element I ↗
Problem: find the next greater element for each element in nums1 based on its position in nums2. If no greater element exists,
the result should be -1.
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1]
Steps: vector<int> ans([Link]());
unordered_map<int, int> mp;
stack<int> st;
[Link](-1);
for(int i = [Link]()-1; i >= 0; i--){ Step 1: Process nums2 from right to left to build the map
while([Link]() != -1 && [Link]() <= nums2[i])
[Link]();
mp[nums2[i]] = [Link]();
[Link](nums2[i]);
}
for(int i = 0; i < [Link](); i++) Step 2: Build the answer for nums1 using the map
ans[i] = mp[nums1[i]];
return ans;
16. GFG Count the Reversals ↗
Problem: find out the minimum number of reversals required to convert the string into a balanced expression. A reversal means
changing '{' to '}' or vice-versa.
Input: s = "}{{}}{{{" Output: 3
Steps: if([Link]() & 1) return -1;
stack<char> st;
int ans = 0;
for(int i = 0; i < [Link](); i++){
if(s[i] == '{')
[Link](s[i]);
else{
if(![Link]() && [Link]() == '{')
[Link]();
else
[Link](s[i]);
}
}
while(![Link]()){
char a = [Link](); [Link]();
char b = [Link](); [Link]();
if(a == b) ans += 1;
else ans += 2;
}
return ans;
17. The Celebrity Problem ↗
18. Leetcode 1019. Next Greater Node In Linked List ↗
Steps: vector<int> values; Step 1: Convert Linked List to Array
ListNode* current = head;
while (current) {
values.push_back(current->val);
current = current->next;
}
vector<int> answer([Link]()); Step 2: Traverse from Right to Left
stack<int> st; // stores node values
[Link](0);
for (int i = [Link]() - 1; i >= 0; --i) {
while ([Link]() != 0 && [Link]() <= values[i]) {
[Link]();
}
answer[i] = [Link]();
[Link](values[i]);
}
return answer;
19. N Stacks in Array
20. Leetcode 901. Online Stock Span ↗
Problem: you’re given stock prices one by one. For each new price, you must return how many consecutive days (including
today) the price was less than or equal to today’s price.
Input ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"] [[], [100], [80], [60], [70], [60], [75], [85]]
Output [null, 1, 1, 1, 2, 1, 4, 6]
Steps: stack <pair<int, int>> st; {price, span}
StockSpanner() {}
int next(int price) {
int span = 1;
while(![Link]() && [Link]().first <= price){
span = span + [Link]().second;
[Link]();
}
[Link]({price, span});
return span;
}
21. Leetcode 1003. Check If Word Is Valid After Substitutions ↗
Input: s = "aabcbc" Output: true
Explanation: "" -> "abc" -> "aabcbc" Thus, "aabcbc" is valid.
Steps: stack<char> st;
for (char ch : s) {
[Link](ch);
if ([Link]() >= 3) { Check if the top 3 characters are 'a', 'b', 'c'
char c = [Link](); [Link]();
char b = [Link](); [Link]();
char a = [Link](); [Link]();
if (a == 'a' && b == 'b' && c == 'c') Valid triplet 'abc', do nothing (they're removed)
else { Push them back if not 'abc'
[Link](a);
[Link](b);
[Link](c);
}
}
}
return [Link](); If stack is empty, it's valid
22. Leetcode 739. Daily Temperatures ↗
Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]
Steps: vector<int> ans([Link](), 0);
stack<int> st;
for(int i = [Link]()-1; i >= 0; i--){
while(![Link]() && temperatures[i] >= temperatures[[Link]()]){
[Link]();
}
if(![Link]()) ans[i] = [Link]() - i;
[Link](i);
}
return ans;
23. Leetcode 71. Simplify Path ↗
Rules to follow:
• '.' ➔ means current directory → so ignore it.
• '..' ➔ means go to parent directory → remove the last valid folder.
• Multiple slashes '//' ➔ treat as a single slash.
Input: path = "/home/user/Documents/../Pictures" Output: "/home/user/Pictures"
Steps: stringstream ss(path);
string token;
stack<string> st;
while(getline(ss, token, '/')){
if(token == "" || token == ".") continue;
if(token != "..") [Link](token);
else if(![Link]()) [Link]();
}
if([Link]()) return "/";
string ans;
while(![Link]()){
ans = '/' + [Link]() + ans;
[Link]();
}
return ans;
24. Leetcode 402. Remove K Digits
25. Leetcode 921. Minimum Add to Make Parentheses Valid
1. whenever we axis [Link]() then make sure [Link]() or not, eg. if([Link]() || element > [Link]())