# Problems

##

{% file src="/files/gl3AwdbrgkSv8TyYBFE6" %}

## [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)

1. `Step 1:` Push the element into the <mark style="color:red;">Q2</mark>.
2. `Step 2:` Push the remaining elements of <mark style="color:red;">Q1</mark> into <mark style="color:red;">Q2</mark>.
3. `Step 3:` <mark style="color:red;">Swap(Q1, Q2)</mark>.

```cpp
class MyStack {
    queue<int> q1, q2;
public:
    
    void push(int x) {
        q2.push(x);

        while(!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        
        swap(q1, q2);
    }
    
    int pop() {
        if(q1.empty())return -1;

        int d = q1.front();
        q1.pop();
        return d;
    }
    
    int top() {
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
```

## `Q1:`   [Two Stacks](https://www.codingninjas.com/studio/problems/two-stacks_983634?leftPanelTab=0\&campaign=YouTube_CodestudioLovebabbar5thfeb\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=YouTube_CodestudioLovebabbar5thfeb)

```cpp
#include <bits/stdc++.h> 
class TwoStack {
    int *arr;
    int top1, top2;
    int size;
    int elements;
public:

    // Initialize TwoStack.
    TwoStack(int s) {
        size = s;
        arr = new int[size];
        top1 = -1;
        top2 = size;
        elements = 0;
    }
    
    bool full() {
        return elements == size;
    }
    
    bool empty() {
        return elements == 0;
    }
    
    // Push in stack 1.
    void push1(int num) {
        if(full()) return;

        arr[++top1] = num;
        elements++;
    }

    // Push in stack 2.
    void push2(int num) {
        if(full()) return;

        arr[--top2] = num;
        elements++;
    }

    // Pop from stack 1 and return popped element.
    int pop1() {
        if(top1 == -1) return -1;

        int d = arr[top1--];
        elements--;
        return d;
    }

    // Pop from stack 2 and return popped element.
    int pop2() {
        if(top2 == size) return -1;

        int d = arr[top2++];
        elements--;
        return d;
    }
};

```

## `Q2:`   [Reverse a string](https://leetcode.com/problems/reverse-string/solutions/) using a Stack

Not a Good approach because the time and space complexity of this program is O(n)

### Best Approach:  [Reverse a string](/nafees/string.md#q1-reverse-string) using STL Build-in Function reverse()

```cpp
void reverseString(vector<char>& str) {
    stack <char> s;
    for(int i = 0; i < str.size(); i++){
        s.push(str[i]);
    }
    int j = 0;
    while(!s.empty()){
        str[j++] = s.top();
        s.pop();
    }
}
```

## `Q3:`   [Delete Middle element from Stack](https://www.codingninjas.com/studio/problems/delete-middle-element-from-stack_985246?leftPanelTab=0%3Fsource%3Dyoutube\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

```cpp
#include <bits/stdc++.h> 
void sol(stack<int>&s, int count, int size) {
   // Base Case
   if(count == size/2){
      s.pop();
      return;
   }
   
   int topElement = s.top();
   s.pop();

   // recursive call
   sol(s, ++count, size);

   s.push(topElement);
}

void deleteMiddle(stack<int>&inputStack, int N){
   int count = 0;
   sol(inputStack, count, N);
}
```

## `Q4:`   [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

```cpp
class Solution {
public:
    bool isValid(string str) {
        stack<char> s;
        for(int i = 0; i < str.length(); i++) {

            char ch = str[i]; 

            // if opening bracket, stack push
            // if closing bracket, stack top check and pop
            
            if(ch == '(' || ch == '{' || ch == '[')
                s.push(ch);

            else{

                if(s.empty())
                    return false;
                
                // for closing parentheses
                else{
                    char top = s.top();

                    if( ( ch == ')' && top == '(' ) || ( ch == '}' && top == '{' ) || ( ch == ']' && top == '[' ) )
                        s.pop();

                    else
                        return false;
                }
            }
        }
        // 
        if(s.empty())
            return true;

        else
            return false;
    }
};

Time & space complexity of this program is O(N); // N is the size of the string str
```

## `Q5:`   [Insert An Element At Its Bottom In A Given Stack](https://www.codingninjas.com/studio/problems/insert-an-element-at-its-bottom-in-a-given-stack_1171166?topList=love-babbar-dsa-sheet-problems\&leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

```cpp
#include <bits/stdc++.h>

void Solution(stack<int>& myStack, int x) {
    // Base-Condition
    if(myStack.empty()){
        myStack.push(x);
        return;
    }

    int topElem = myStack.top();
    myStack.pop();
    
    // Recursive Call
    Solution(myStack, x);

    myStack.push(topElem);
} 

stack<int> pushAtBottom(stack<int>& myStack, int x) 
{
    Solution(myStack, x);
    return myStack;
}
```

## `Q6:`   [Reverse Stack Using Recursion](https://www.codingninjas.com/studio/problems/reverse-stack-using-recursion_631875?topList=love-babbar-dsa-sheet-problems\&leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

{% code title="using single stack only" %}

```cpp
void insertatBottom(stack<int> &stack, int element) {
    if(stack.empty()) {
        stack.push(element);
        return ;
    }
    
    int topElem = stack.top(); 
    stack.pop();
    insertatBottom(stack, element);
    
    stack.push(topElem);
}

void reverseStack(stack<int> &stack) {

    if(stack.empty()) 
        return;
    
    int topElem = stack.top();
    stack.pop();
    
    reverseStack(stack);

    insertatBottom(stack, topElem);
}
```

{% endcode %}

| Function           | Time Complexity | Space Complexity |
| ------------------ | --------------- | ---------------- |
| `insertatBottom()` | O(n)            | O(n)             |
| `reverseStack()`   | O(n)            | O(n)             |

## `Q8:`   [Reverse stack using extra stack](https://www.codingninjas.com/studio/problems/reverse-stack-using-recursion_631875?topList=love-babbar-dsa-sheet-problems\&leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

{% code title="using double stack" %}

```cpp
void reverseStack(stack<int> &s) {
    stack<int>s2;
    while(!s.empty()) {
        s2.push(s.top());
        s.pop();
    }
    s = s2;
}
```

{% endcode %}

## `Q8:`   [Sort a Stack](https://www.codingninjas.com/studio/problems/sort-a-stack_985275?topList=love-babbar-dsa-sheet-problems\&leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

```cpp
#include <bits/stdc++.h> 

void sortedInsert(stack<int> &s, int n) {
	if(s.empty() || s.top() < n) {
		s.push(n);
		return;
	}

	int topElem = s.top();
	s.pop();

	sortedInsert(s, n);

	s.push(topElem);
}

void sortStack(stack<int> &s){
	if(s.empty()) 
		return;
	
	int topElem = s.top();
	s.pop();

	sortStack(s);

	sortedInsert(s, topElem);
}
```

## Q9:   [Redundant Brackets](https://www.codingninjas.com/studio/problems/redundant-brackets_975473?leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

## [Note](https://drive.google.com/file/d/17u2Zaf3qol_k7o6cvyZIc8Qg0yR6XOec/view?usp=drive_link)

* Time Complexity: O(n)
* Space Complexity: O(n)      // because of stack

```cpp
#include <bits/stdc++.h> 

bool findRedundantBrackets(string &str){
    stack<char> s;

    for(int i = 0; i < str.size(); i++) {
        char ch = str[i];

        if( ch == '(' || ch == '+' || ch == '-' || ch == '*' || ch == '/') 
            s.push(ch);

        else {
            if( ch == ')' ) // ignoring all letters
            {
                bool isRedundant = true;

                while (s.top() != '(') { // loop terminated when stack top element == '('
                    char topElem = s.top(); // storing operators and comparing

                    if(topElem == '+' || topElem == '-' || topElem == '*' || topElem == '/') 
                        isRedundant = false; //not redundant brackects
        
                    s.pop(); // pop oprtators (+,-,*,/)
                }
                s.pop(); // pop the '('
                
                // if there's no operator left between '(' & ')'
                if(isRedundant == true) 
                    return true; // redundant brackets
            }
        }
    }
    return false;
}

```

## `Q10:`  Check palindrome

```cpp
#include <iostream>
#include <cstring>
#include "Stack.h"

bool checkPalindrome(Stack& s, int size) {
    Stack s2;
    
    for (int i = 0; i < size/2; i++)
    {
        s2.push(s.top());
        s.pop();
    }

    if(size & 1) // for odd elements
        s.pop();

    for (int i = 0; i < size/2; i++)
    {
        if(s.top() != s2.top()) return false;

        s.pop();
        s2.pop();
    }

    return true;
}

int main() {
    Stack s;
    int size = 0;
    char ch[Stack::SIZE];
    
    cin.getline(ch, Stack::SIZE);
    
    for (auto  c: ch)
    {
        if(c == '-' || s.isFull()) break;
     
        s.push(c);
        size++;
    }
    
    cout << boolalpha << checkPalindrome(s, size) << endl;
    
    if(s.isEmpty()) cout << "\nEmpty Stack!";

    while (!s.isEmpty())
    {
        cout << s.top() << " ";
        s.pop();
    }
}
```

## `Q11:`   [Minimum Cost To Make String Valid](https://www.codingninjas.com/studio/problems/minimum-cost-to-make-string-valid_1115770?leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

## [Dry Run](https://drive.google.com/file/d/1tgbr15Yc39r80HAh3GAvB4c57ru0wrtH/view?usp=drive_link)

```cpp
#include <bits/stdc++.h> 
int findMinimumCost(string str){
    if(str.size() & 1) return -1;

    stack<char> s;
    for (auto c : str) {

        //for open braces
        if(c == '{') {
            s.push(c);
        }
        
        else {
// if c == '}' & s.top() contain '{' then pop.
            if(!s.empty() && s.top() == '{')
                s.pop();
                
// if c == '}' & s.top() is empty & and not contain '{' then push c into the stack
            else
                s.push(c);
        }
    }

    // 'a' count open braces 
    // 'b' count closed braces

    int a, b;
    a = b = 0;

    while (!s.empty()) {
        if(s.top() == '{')
            a++;
        else
            b++;
        s.pop();
    }

    int ans = (a+1)/2 + (b+1)/2;
    return ans;
}
```

## `Q12:`   [Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)

```cpp
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        
        stack<char> s1, s2;
        for(auto ch: s) {

            if(!s1.empty() && ch == '#') 
                s1.pop();

            else if(ch != '#')
                s1.push(ch);

        }

        for(auto ch: t) {
            if(!s2.empty() && ch == '#') 
                s2.pop();
            
            else if(ch != '#')
                s2.push(ch);
            
        }
        return s1 == s2;
    }
}; 

// error if ignoring else if (ch != '#')
// s = "y#fo##f"
// t = "y#f#o##f"
```

## `Q13:`   [Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/)  --> pending

## `Q14:`   [Next Smaller Element](https://www.codingninjas.com/studio/problems/next-smaller-element_1112581?topList=love-babbar-dsa-sheet-problems\&leftPanelTab=0\&campaign=Lovebabbarcodestudio\&utm_source=youtube\&utm_medium=affiliate\&utm_campaign=Lovebabbarcodestudio)

```cpp
#include<stack>
vector<int> nextSmallerElement(vector<int> &arr, int n)
{
    stack<int> s;
    s.push(-1);
    vector<int> ans(n);
    int cur;
    
    for(int i = n-1; i >= 0; i--) {
        cur = arr[i];

        // pop until find the smallest element than cur 
        while(s.top() >= cur){
            s.pop();
        }
        
        // now s.top() contain the smallest element
        ans[i] = s.top();
        s.push(cur); // push cur element into the stack
    }
    return ans;
}

// T.C = O(N)
```

## &#x20;`Q15:`   Previous Smaller Element

```cpp
vector<int> previousSmallestElement(vector<int>& arr, int n){
    stack<int> s;
    s.push(-1);
    vector<int> ans(n);
    int cur;
    
    // change in 'for loop' of next smaller element code
    for (int i = 0; i < n; i++) {
        cur = arr[i];
        while(s.top() >= cur) {
            s.pop();
        }

        ans[i] = s.top();
        s.push(cur);
    }
    return ans;
}
```

## `Q16:`  Min Index

```cpp
#include<iostream>
#include<stack>
#include<climits>
using namespace std;

class MinStack {
    stack<int> s1, s2;
    int mini = INT_MAX;

public:
    
    void push(int val) {
        s1.push(val);
        mini = min(s1.top(), mini);
        s2.push(mini);
    }
    
    void pop() {
        if(empty()) return;

        s1.pop();
        s2.pop();
    }
    
    bool empty() {
        return s1.empty() || s2.empty();
    }

    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
};


int main() {
    MinStack s;
    s.push(100);
    s.push(531);
    s.push(233);
    s.push(2);
    s.push(4);

    while(!s.empty()) {
        // cout << s.top() << " ";
        cout << s.getMin() << " ";
        s.pop();
    } // 2 2 100 100 100 
}
```

## `Q17:`  Search in Stack and restore it in the same position.

```cpp
void insertInStack (Stack& s, Queue& q) {
    if(q.empty()) 
        return ;

    int temp = q.front();
    q.dequeue();

    insertInStack(s, q);

    s.push(temp);
}

bool findElement(Stack& s, const int x) {

    Queue q; // empty queue
    bool isPresent = false;

    while (!s.empty()) {
        if(s.top() == x) isPresent = true;

        q.enqueue(s.top());
        s.pop();
    }

    insertInStack(s, q);

    return isPresent;
    
}

```

## `Q18:`   2 Sorted Stack (min on top) inserted into 3rd Stack (min on top)

```cpp
#include <iostream>
using namespace std;

class Stack {
    int *arr;
    int elements;
    int s_top;
    int size;
public:
    
    Stack(int);

    int Size() {
        return size;
    }

    bool empty() const {
        return elements == 0;
    }
    
    bool full() const {
        return elements == size;
    }

    void push(const int x);
    void pop();

    int top() {
        return empty() ? -1: arr[s_top];
    }
};

Stack :: Stack(const int s) {
    size = s;
    arr = new int[size];
    elements = 0;
    s_top = -1;
} 

void Stack :: push(const int x) {
    if(full()) return ;

    arr[++s_top] = x;
    elements++;
}

void Stack :: pop() {
    if(empty()) return ;

    s_top--;
    elements--;
}

void insertAtBottom(Stack& s, const int x) {
    if(s.empty()) {
        s.push(x);
        return;
    }

    int temp = s.top();
    s.pop();

    insertAtBottom(s, x);

    s.push(temp);
}

void reverseStack(Stack& s) {
    if(s.empty()) return ;

    int temp = s.top();
    s.pop();

    reverseStack(s);
    
    insertAtBottom(s, temp);
}

void sortedInserted (Stack s1, Stack s2, Stack& s3) {
    while (!s1.empty() && !s2.empty()) {
        if(s1.top() <= s2.top()) {
            s3.push(s1.top());
            s1.pop();
        }
        else {
            s3.push(s2.top());
            s2.pop();
        }
    }

    while (!s1.empty()) {
        s3.push(s1.top());
        s1.pop();
    }

    while (!s2.empty()) {
        s3.push(s2.top());
        s2.pop();
    }
    
    reverseStack(s3);
}

int main() {
    Stack s1(4);
    s1.push(5);
    s1.push(3);
    s1.push(1);
    s1.push(0);

    Stack s2(3);
    s2.push(7);
    s2.push(6);
    s2.push(2);
    
    Stack s3(s1.Size() + s2.Size());

    sortedInserted(s1, s2, s3);

    while (!s3.empty()) {
        cout << s3.top() << " ";
        s3.pop();
    }
    
}
```

## `Q19:`  Remove All Duplicates

```cpp
#include <iostream>
#include <stack>
using namespace std;

void removerDuplicates(stack<int>& s) {
    if(s.empty()){
        return;
    }
    
    int temp = s.top();
    s.pop();
    
    agya wapis:
    if(!s.empty() && s.top() == temp) {
        s.pop();
        goto jump; // ja dubara check kr or h to bahir nikall
    }
    removerDuplicates(s);
    s.push(temp);
}

int main() {
    stack<int> s;
    s.push(0);
    s.push(0);
    s.push(0);
    s.push(1);
    s.push(4);
    s.push(4);
    s.push(4);
    s.push(4);
    
    removerDuplicates(s);
    
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }   // 0 1 4
    
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/stack/problems.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.