//stacks and queues
take two queues q1,q2 i.e queue<int> q1,q2
push(x)
{
//push the element into q2
//if q1 is not empty then push the elements of q1 into q2 until q1 becomes empty
//swap(q1,q2)
}
pop()
{
//check whether stack is empty or not
// take one var ans
// ans=q1.front where it returns top of the stack
// pop it
}
//leetcode solution
class MyStack {
public:
queue<int> q1,q2;
MyStack() {
void push(int x) {
q2.push(x);
while(!q1.empty())
{
q2.push(q1.front());
q1.pop();
}
swap(q1,q2);
int pop() {
int ans;
if(empty())
return -1;
ans=q1.front();
q1.pop();
return ans;
}
int top() {
if(!empty())
{
return q1.front();
}
return -1;
bool empty() {
//if(q1.front()==-1) return true;
if(q1.empty()) return true;
else
return false;
}
};
//implementing queues using stack
class MyQueue {
public:
stack<int>s1,s2;
MyQueue() {
void push(int x) {
s1.push(x);
}
int pop() {
while(s1.empty()==false)
{
s2.push(s1.top());
s1.pop();
}
int ans=s2.top();
s2.pop();
while(s2.empty()==false)
{
s1.push(s2.top());
s2.pop();
}
return ans;
int peek() {
while(s1.empty()==false)
{
s2.push(s1.top());
s1.pop();
}
int ans=s2.top();
while(s2.empty()==false)
{
s1.push(s2.top());
s2.pop();
}
return ans;
bool empty() {
if(s1.empty()) return true;
else return false;
}
};
/**
push(x)
{
push the data into input stack
}
pop()
{
while s1 is not empty
{
push top of s1 into s2 until all the elements in s1 becomes empty
}
then ans=s2.top
then pop s2
while s2 is not empty
{
push top of s2 into s1 until all the elements in s2 becomes empty
}
return ans
//same logic for peek() except pop s2
*/balanced parenthensis
class Solution {
public:
stack<int>st;
bool isValid(string s) {
for(int i=0;i<s.size();i++)
{
if(s[i]=='[' |s[i]=='{' | s[i]=='(')
{
st.push(s[i]);
}
else
{
if(st.empty()||
s[i]==']' && st.top()!='[' ||
s[i]=='}' && st.top()!='{'||
s[i]==')' && st.top()!='(')
{
return false;
}
st.pop();
}
}
if(st.empty()) return true;
return false;
}
};
//next greater element
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int ans=-1;
unordered_map<int,int>mp;
for(int i=nums2.size()-1;i>=0;i--)
{
for(int j=i+1;j<nums2.size();j++)
{
if(nums2[j]>nums2[i])
{
ans=nums2[j];
break;
}
}
mp[nums2[i]]=ans;
ans=-1;
}
vector<int>v;
for(auto value:nums1)
{
if(mp.find(value)!=mp.end())
{
auto it=mp.find(value);
v.push_back(it->second);
}
else
{
v.push_back(-1);
}
}
return v;
}
};
//sort a stack
#include <bits/stdc++.h>
void sortStack(stack<int> &stack)
{
if(stack.empty()) return;
int x=stack.top();
stack.pop();
sortStack(stack);
// we have to pop the all the elements presents inside the stack
std::stack<int>temp;
while(!stack.empty()&&stack.top()>x)
{
temp.push(stack.top());
stack.pop();
}
stack.push(x);
while(!temp.empty())
{
stack.push(temp.top());
temp.pop();
}
// Write your code here
}
//sliding window maximum
#include<bits/stdc++.h>
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int>dq;
for(int i=0;i<nums.size();i++)
{
//check the subarray with size k only other than that we ahve to pop
out
if(!dq.empty()&&dq.front()==i-k)
{
dq.pop_front();
}
while(!dq.empty()&&nums[dq.back()]<nums[i])
{
dq.pop_back();
}
dq.push_back(i);
if(i>=k-1)
{
ans.push_back(nums[dq.front()]);
}
}
return ans;
}
};
deque is used here because it has two pointers back and front
//largest rectangle in a histogram
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
int left[n];
int right[n];
stack<int> st;
for(int i=0;i<n;i++)
{
while(!st.empty()&&heights[st.top()]>=heights[i])
{
st.pop();
}
if(st.empty())
{
left[i]=0;
}
else
{
left[i]=st.top()+1;
}
st.push(i);
}
while(!st.empty())
{
st.pop();
}
for(int i=n-1;i>=0;i--)
{
while(!st.empty()&&heights[st.top()]>=heights[i])
{
st.pop();
}
if(st.empty())
{
right[i]=n-1;
}
else
{
right[i]=st.top()-1;
}
st.push(i);
}
int maxa=0;
for(int i=0;i<n;i++)
{
maxa=max(maxa,(heights[i]*(right[i]-left[i]+1)));
}
return maxa;
}
};
//the stack span problem
span=current index-top
stop if current index price is less than top
pop if current index price is greater than top
class StockSpanner {
public:
vector<int>list;
StockSpanner() {
int next(int price) {
list.push_back(price);
int count=0;
for(int i=list.size()-1;i>=0;i--)
{
if(list[i]>price)
break;
count++;
}
return count;
}
vector<int>calculate(vector<int>&prices)
{
vector<int>spans(prices.size(),0);
spans[0]=1;
stack<int>s;
s.push(0);
for(int i=1;i<prices.size();i++)
{
while(!s.empty()&&prices[s.top()]<prices[i])
{
s.pop();
}
if(s.empty())
spans[i]=i+1;
else
spans[i]=i-s.top();
}
return spans;
}
};
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner* obj = new StockSpanner();
* int param_1 = obj->next(price);
*/
