Last Updated on March 21, 2022 by Ria Pathak
Concepts Used
Basic operations of stack.
Difficulty Level:
Hard.
Problem Statement :
Nikhil now got a job.
His task is to evaluate files. His boss comes and puts a file on top of his existing file stack and he after completing a task removes the file from the top of the stack and evaluates it.
Now the boss asks his time to complete a file evaluation, So to get a promotion Nikhil always tells him the minimum time required.
So for every file, you are given the time to evaluate.the operations are:
- "1 x" add a file with time x to top of the stack.
- "2" removes the file from top of the stack and print the time to evaluate the file removed.
- "3" print the time to evaluate the top file.4. "4" print the minimum time of the present stack.
You are given Q queries, evaluate them. if there is an empty stack and top is asked, print −1.if there is an empty stack and element is tried to pop, print −1.if there is an empty stack and minimum element is asked, print −1.
See original problem statement here
Test Case:
Input:
1
7
1 1
1 3
1 4
1 9
2
3
4
Output:
9
4
1
Explanation:
Top of the stack is 9, and we remove it
Top of the stack now 4.
The minimum element in the stack is 1.Solving Approach:
- This problem involves basic stack operations of push and pop.
- To get the minimum element from stack we design another stack(say stackmin) whick stores the minimum element.
- If the top of the original stack is less than the top of stackmin,we push the element to stackmin.
- Also, while popping elements from original stack,if the popped element is equal to the top of stackmin,the top of stackmin is also popped.
Solutions:
#include <stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int q;
scanf("%d",&q);
int stack[q],stackmin[q];
int top=-1,topmin=-1;
while(q--)
{
int x;scanf("%d",&x);
if(x==1)
{
int y;scanf("%d",&y);
stack[++top]=y;
if(topmin==-1)
stackmin[++topmin]=y;
else if(y<=stackmin[topmin])
stackmin[++topmin]=y;
}
else if(x==2)
{
if(top==-1)
printf("-1\n");
else
{
if(stack[top]==stackmin[topmin])
topmin--;
printf("%d\n",stack[top]);
top--;}
}
else if(x==3)
{
if(top==-1)
printf("-1\n");
else
printf("%d\n",stack[top]);}
else
{
if(top==-1)
printf("-1\n");
else
printf("%d\n",stackmin[topmin]);}
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
class DS
{
public:
stack<int> s;
stack<int> m;
int min1;
DS()
{
while(s.size()>0)
s.pop();
while(m.size()>0)
m.pop();
m.push(-1);
min1=-1;
}
void push(int x) {
if(min1==-1)
min1=x;
else if(min1>x)
min1=x;
s.push(x);
m.push(min1);
fflush(stdout);
}
void pop() {
if(s.size()==0||m.size()==0)
return;
m.pop();
s.pop();
min1=m.top();
}
int top() {
if(s.size()==0)return -1;
return s.top();
}
int getMin() {
return min1;
}
};
int main()
{
int t;
cin>>t;
while(t--)
{
DS *d=new DS();
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
if(x==1){
int y;
cin>>y;
d->push(y);
}else if(x==2)
{
cout<<d->top()<<"\n";
d->pop();
}else if(x==3)
{
cout<<d->top()<<"\n";
}else if(x==4)
{
cout<<d->getMin()<<"\n";
}
}
}
return 0;
}
import java.util.*;
public class Solution{
public static class DS
{
Scanner sc=new Scanner(System.in);
int min1;
Stack<Integer> s=new Stack<Integer>();
Stack<Integer> m=new Stack<Integer>();
public void DS(){
while(s.size()>0)
s.pop();
while(m.size()>0)
m.pop();
m.push(-1);
min1=-1;
}
public void push(int x) {
if(min1==-1)
min1=x;
else if(min1>x)
min1=x;
s.push(x);
m.push(min1);
sc.next();
System.out.println();
}
public void pop() {
if(s.size()==0||m.size()==0)
return;
m.pop();
s.pop();
min1=m.peek();
}
public int top() {
if(s.size()==0)
return -1;
return s.peek();
}
public int getMin() {
return min1;
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
DS ob=new DS();
int n=sc.nextInt();
while(n-->0)
{
int x=sc.nextInt();
if(x==1){
int y=sc.nextInt();
ob.push(y);
}
else if(x==2)
{
System.out.println(ob.top());
ob.pop();
}else if(x==3)
{
System.out.println(ob.top());
}
else if(x==4)
{
System.out.println(ob.getMin());
}
}
}
}
}
[forminator_quiz id="1936"]
So, in this blog, we have tried to explain basic operations of stack. If you want to solve more questions on stack data structure, which are curated by our expert mentors at PrepBytes, you can follow this link Stack.