Problems

654B

Stack.h

Open

Implement Stack using Queues

1. Step 1: Push the element into the Q2.

2. Step 2: Push the remaining elements of Q1 into Q2.

3. Step 3: Swap(Q1, Q2).

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

#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 using a Stack

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

Best Approach: Reverse a string using STL Build-in Function reverse()

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

#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

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

#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

using single stack only

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);
}

Function	Time Complexity	Space Complexity
insertatBottom()	O(n)	O(n)
reverseStack()	O(n)	O(n)

Q8: Reverse stack using extra stack

using double stack

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

Q8: Sort a Stack

#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

Note

• Time Complexity: O(n)

• Space Complexity: O(n) // because of stack

#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

#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

Dry Run

#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

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 --> pending

Q14: Next Smaller Element

#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)

Q15: Previous Smaller Element

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

#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.

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)

#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

#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
    
}