Stack
Lecture 1 code//////
Code1
#include<iostream>
#include<stack>
using namespace std;
class Stack {
//properties
public:
int *arr;
int top;
int size;
// behaviour
Stack(int size) {
this -> size = size;
arr = new int[size];
top = -1;
}
void push( int element) {
if(size - top > 1) {
top++;
arr[top] = element;
}
else{
cout << "Stack OverFlow" << endl;
}
}
void pop() {
if(top >=0 ) {
top--;
}
else{
cout << "Stack UnderFlow" << endl;
}
}
int peek() {
if(top >=0 )
return arr[top];
else
{
cout << "Stack is Empty" << endl;
return -1;
}
}
bool isEmpty() {
if( top == -1) {
return true;
}
else{
return false;
}
}
};
int main() {
Stack st(5);
[Link](22);
[Link](43);
[Link](44);
[Link](22);
[Link](43);
[Link](44);
cout << [Link]() << endl;
[Link]();
cout << [Link]() << endl;
[Link]();
cout << [Link]() << endl;
[Link]();
cout << [Link]() << endl;
if([Link]()) {
cout << "Stack is Empty mere dost " << endl;
}
else{
cout << "Stack is not Empty mere dost " << endl;
}
/*
//creation of stack
stack<int> s;
//push operation
[Link](2);
[Link](3);
//pop
[Link]();
cout << "Printing top element " << [Link]() << endl;
if([Link]()){
cout << "Stack is empty " << endl;
}
else{
cout << "stack is not empty " << endl;
}
cout << "size of stack is " << [Link]() << endl;
*/
return 0;
}
Code 2
class TwoStack {
int *arr;
int top1;
int top2;
int size;
public:
// Initialize TwoStack.
TwoStack(int s) {
this -> size = s;
top1 = -1;
top2 = s;
arr = new int[s];
}
// Push in stack 1.
void push1(int num) {
//atleast a empty space present
if(top2 - top1 > 1 ) {
top1++;
arr[top1] = num;
}
// Push in stack 2.
void push2(int num) {
if(top2 - top1 > 1 ) {
top2--;
arr[top2] = num;
}
// Pop from stack 1 and return popped element.
int pop1() {
if( top1 >= 0) {
int ans = arr[top1];
top1--;
return ans;
}
else
{
return -1;
}
}
// Pop from stack 2 and return popped element.
int pop2() {
if( top2 < size) {
int ans = arr[top2];
top2++;
return ans;
}
else
{
return -1;
}
}
};
Lecture 2
Code 1
#include<stack>
int findMinimumCost(string str) {
//odd condition
if([Link]()%2 == 1) {
return -1;
}
stack<char> s;
for(int i=0; i<[Link](); i++) {
char ch = str[i];
if(ch == '{')
[Link](ch);
else
{
//ch is closed brace
if(![Link]() && [Link]() == '{') {
[Link]();
}
else
{
[Link](ch);
}
}
}
//stack contains invalid expression
int a = 0, b = 0;
while(![Link]()) {
if([Link]() == '{') {
b++;
}
else
{
a++;
}
[Link]();
}
int ans = (a+1)/2 + (b+1)/2;
return ans;
Code 2
void solve(stack<int>&inputStack, int count, int size) {
//base case
if(count == size/2) {
[Link]();
return ;
}
int num = [Link]();
[Link]();
//RECURSIVE CALL
solve(inputStack, count+1, size);
[Link](num);
void deleteMiddle(stack<int>&inputStack, int N){
int count = 0;
solve(inputStack, count, N);
Code 3
void solve(stack<int>& s, int x) {
//base case
if([Link]()) {
[Link](x);
return ;
}
int num = [Link]();
[Link]();
//recursive call
solve(s, x);
[Link](num);
}
stack<int> pushAtBottom(stack<int>& myStack, int x)
{
solve(myStack, x);
return myStack;
}
Code 4
#include<stack>
bool findRedundantBrackets(string &s)
{
stack<char> st;
for(int i=0; i<[Link](); i++) {
char ch =s[i];
if(ch == '(' || ch == '+' ||ch == '-' || ch == '*' || ch == '/')
{
[Link](ch);
}
else
{
//ch ya toh ')' hai or lowercase letter
if(ch == ')') {
bool isRedundant = true;
while([Link]() != '(') {
char top = [Link]();
if(top == '+' ||top == '-' || top == '*' || top ==
'/') {
isRedundant = false;
}
[Link]();
}
if(isRedundant == true)
return true;
[Link]();
}
}
}
return false;
}
Code 5
void insertAtBottom(stack<int> &s, int element) {
//basecase
if([Link]()) {
[Link](element);
return ;
}
int num = [Link]();
[Link]();
//recursive call
insertAtBottom(s, element);
[Link](num);
}
void reverseStack(stack<int> &stack) {
//base case
if([Link]()) {
return ;
}
int num = [Link]();
[Link]();
//recursive call
reverseStack(stack);
insertAtBottom(stack,num);
}
Code 6
#include<iostream>
#include<stack>
using namespace std;
int main () {
string str = "babbar";
stack<char> s;
for (int i = 0; i<[Link](); i++) {
char ch = str[i];
[Link](ch);
}
string ans = "";
while(![Link]()) {
char ch = [Link]();
ans.push_back(ch);
[Link]();
}
cout << "answer is: "<< ans << endl;
return 0;
}
Code 7
void sortedInsert(stack<int> &stack, int num) {
//base case
if([Link]() || (![Link]() && [Link]() < num) ) {
[Link](num);
return;
}
int n = [Link]();
[Link]();
//recusrive call
sortedInsert(stack, num);
[Link](n);
}
void sortStack(stack<int> &stack)
{
//base case
if([Link]()) {
return ;
}
int num = [Link]();
[Link]();
//recursive call
sortStack(stack);
sortedInsert(stack, num);
}
Code 8
bool isValidParenthesis(string expression)
{
stack<char> s;
for(int i=0; i<[Link](); i++) {
char ch = expression[i];
//if opening bracket, stack push
//if close bracket, stacktop check and pop
if(ch == '(' || ch == '{' || ch == '['){
[Link](ch);
}
else
{
//for closing bracket
if(![Link]()) {
char top = [Link]();
if( (ch == ')' && top == '(') ||
( ch == '}' && top == '{') ||
(ch == ']' && top == '[') ) {
[Link]();
}
else
{
return false;
}
}
else
{
return false;
}
}
}
if([Link]())
return true;
else
return false;
}
Lecture 3
Code 1(Area Histogram)
class Solution {
private:
vector<int> nextSmallerElement(vector<int> arr, int n) {
stack<int> s;
[Link](-1);
vector<int> ans(n);
for(int i=n-1; i>=0 ; i--) {
int curr = arr[i];
while([Link]() != -1 && arr[[Link]()] >= curr)
{
[Link]();
}
//ans is stack ka top
ans[i] = [Link]();
[Link](i);
}
return ans;
}
vector<int> prevSmallerElement(vector<int> arr, int n) {
stack<int> s;
[Link](-1);
vector<int> ans(n);
for(int i=0; i<n; i++) {
int curr = arr[i];
while([Link]() != -1 && arr[[Link]()] >= curr)
{
[Link]();
}
//ans is stack ka top
ans[i] = [Link]();
[Link](i);
}
return ans;
}
public:
int largestRectangleArea(vector<int>& heights) {
int n= [Link]();
vector<int> next(n);
next = nextSmallerElement(heights, n);
vector<int> prev(n);
prev = prevSmallerElement(heights, n);
int area = INT_MIN;
for(int i=0; i<n; i++) {
int l = heights[i];
if(next[i] == -1) {
next[i] = n;
}
int b = next[i] - prev[i] - 1;
int newArea = l*b;
area = max(area, newArea);
}
return area;
}
};
Code 2(Next smaller)
#include<stack>
vector<int> nextSmallerElement(vector<int> &arr, int n)
{
stack<int> s;
[Link](-1);
vector<int> ans(n);
for(int i=n-1; i>=0 ; i--) {
int curr = arr[i];
while([Link]() >= curr)
{
[Link]();
}
//ans is stack ka top
ans[i] = [Link]();
[Link](curr);
}
return ans;
}
Lecture 3
Code 1(Celebrity)
//Initial template for C++
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution
{
private:
bool knows(vector<vector<int> >& M, int a, int b, int n) {
if(M[a][b] == 1)
return true;
else
return false;
}
public:
//Function to find if there is a celebrity in the party or not.
int celebrity(vector<vector<int> >& M, int n)
{
stack<int> s;
//step1: push all element in stack
for(int i=0; i<n; i++) {
[Link](i);
}
//step2: get 2 elements and copare them
while([Link]() > 1) {
int a = [Link]();
[Link]();
int b = [Link]();
[Link]();
if(knows(M,a,b,n)){
[Link](b);
}
else
{
[Link](a);
}
}
int ans = [Link]();
//step3: single element in stack is potential celeb
//so verify it
int zeroCount = 0;
for(int i=0; i<n; i++) {
if(M[ans][i] == 0)
zeroCount++;
}
//all zeroes
if(zeroCount != n)
return -1;
//column check
int oneCount = 0;
for(int i=0; i<n; i++) {
if(M[i][ans] == 1)
oneCount++;
}
if(oneCount != n-1)
return -1;
return ans;
}
};
// { Driver Code Starts.
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<vector<int> > M( n , vector<int> (n, 0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>M[i][j];
}
}
Solution ob;
cout<<[Link](M,n)<<endl;
}
}
// } Driver Code Ends
Code 2(Max Rectangle)
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// } Driver Code Ends
/*You are required to complete this method*/
class Solution{
private:
vector<int> nextSmallerElement(int *arr, int n) {
stack<int> s;
[Link](-1);
vector<int> ans(n);
for(int i=n-1; i>=0 ; i--) {
int curr = arr[i];
while([Link]() != -1 && arr[[Link]()] >= curr)
{
[Link]();
}
//ans is stack ka top
ans[i] = [Link]();
[Link](i);
}
return ans;
}
vector<int> prevSmallerElement(int* arr, int n) {
stack<int> s;
[Link](-1);
vector<int> ans(n);
for(int i=0; i<n; i++) {
int curr = arr[i];
while([Link]() != -1 && arr[[Link]()] >= curr)
{
[Link]();
}
//ans is stack ka top
ans[i] = [Link]();
[Link](i);
}
return ans;
}
int largestRectangleArea(int* heights, int n) {
//int n= [Link]();
vector<int> next(n);
next = nextSmallerElement(heights, n);
vector<int> prev(n);
prev = prevSmallerElement(heights, n);
int area = INT_MIN;
for(int i=0; i<n; i++) {
int l = heights[i];
if(next[i] == -1) {
next[i] = n;
}
int b = next[i] - prev[i] - 1;
int newArea = l*b;
area = max(area, newArea);
}
return area;
}
public:
int maxArea(int M[MAX][MAX], int n, int m) {
//compute area for first row
int area = largestRectangleArea(M[0], m);
for(int i = 1; i<n; i++) {
for(int j = 0; j<m; j++) {
//row udpate: by adding previous row's value
if(M[i][j] != 0)
M[i][j] = M[i][j] + M[i-1][j];
else
M[i][j] = 0;
}
//entire row is updated now
area = max(area, largestRectangleArea(M[i],m));
}
return area;
}
};
// { Driver Code Starts.
int main() {
int T;
cin >> T;
int M[MAX][MAX];
while (T--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> M[i][j];
}
}
Solution obj;
cout << [Link](M, n, m) << endl;
}
}
// } Driver Code Ends
Lecture 4
Code 1(Nstack)
class NStack
{
int *arr;
int *top;
int *next;
int n, s;
int freespot;
public:
// Initialize your data structure.
NStack(int N, int S)
{
n = N;
s = S;
arr = new int[s];
top = new int[n];
next = new int[s];
//top initialise
for(int i=0; i<n; i++) {
top[i] = -1;
}
//next initialise
for(int i=0; i<s; i++) {
next[i] = i+1;
}
//update last index value to -1
next[s-1] = -1;
//initialise freespot
freespot = 0;
// Pushes 'X' into the Mth stack. Returns true if it gets pushed into
the stack, and false otherwise.
bool push(int x, int m)
{
//check for overflow
if(freespot == -1) {
return false;
}
//find index
int index = freespot;
//insert element into array
arr[index] = x;
//update freespot
freespot = next[index];
//update next;
next[index] = top[m-1];
//update top
top[m-1] = index;
return true;
}
// Pops top element from Mth Stack. Returns -1 if the stack is empty,
otherwise returns the popped element.
int pop(int m)
{
//check underflow condition
if(top[m-1] == -1) {
return -1;
}
int index= top[m-1];
top[m-1] = next[index];
next[index] = freespot;
freespot = index;
return arr[index];
}
};
Lecture 5
Code 1(Special stack)
#include<stack>
#include<limits.h>
class SpecialStack {
// Define the data members.
stack<int> s;
int mini = INT_MAX;
/*----------------- Public Functions of SpecialStack
-----------------*/
public:
void push(int data) {
//for first element
if([Link]()) {
[Link](data);
mini = data;
}
else
{
if(data < mini) {
[Link](2*data - mini);
mini = data;
}
else
{
[Link](data);
}
}
}
int pop() {
if([Link]()){
return -1;
}
int curr = [Link]();
[Link]();
if(curr > mini) {
return curr;
}
else
{
int prevMin = mini;
int val = 2*mini - curr;
mini = val;
return prevMin;
}
}
int top() {
if([Link]())
return -1;
int curr = [Link]();
if(curr < mini) {
return mini;
}
else
{
return curr;
}
}
bool isEmpty() {
return [Link]();
}
int getMin() {
if([Link]())
return -1;
return mini;
}
};