WINSEM2024-25_STS4022_SS_VL2024250500364_2024-12-21_Reference-Material-I.pptx

Adhuuu idhaba

1. Minimum Stack

2. Minimum Stack Problem: Design and implement a stack that supports push(),pop(), top() and retrieving the minimum element in constant time. Implement a Stack class, which supports the following methods in O(1) time complexity. void push() : Insert element onto the stack. void pop() : Remove the top element from the stack. int top() : Retrieve the top element in the stack. int getmin() : Retrieve the minimum element in the stack.

3. Example Current Minimum Push 4 Push 3 Push 6 Push 2 Push 1 Pop 6 Pop 2 4 4 4 4 3 3 3 3 6 4 3 6 2 4 3 6 2 3 3 1 4 4 3 3 1

4. import java.util.*; class Mystack { Stack<Integer> s; Stack<Integer> a; Mystack() { s = new Stack<Integer>(); a = new Stack<Integer>(); } void getMin() { if(a.isEmpty()) System.out.println(“Stack is Empty”); else System.out.println(“Minimum element : “ + a.peek()); } void peek(){ if(s.isEmpty()) { System.out.println(“Stack is Empty”); return ; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

5. integer t=s.peek(); System.out.print(“Top most element:” + t); } void pop() { int t = s.pop(); if(s.isEmpty()) { System.out.println(“Stack is Empty”); return ; } else System.out.println(“Removed element : “ + t); if(t == a.peek()) a.pop(); } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

6. void push(int x) { if ( s.isEmpty()) { s.push(x); a.push(x); System.out.println(“ Number Inserted: “+ x); return ; } else { s.push(x); System.out.prinln( “ Number Inserted: “ +x);} if ( x<= a.peek() ) a.push(x); } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

7. public class Main { public static void main(String args[]) { Mystack s=new Mystack(); Scanner sc = new Scanner(System.in); int n=sc.nextInt(); for( int i=0;i<n;i++) { int m=sc.nextInt(); s.push(m); } s.getMin(); s.pop(); s.getMin(); s.pop(); s.peek(); } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

8. THANK YOU