Stacks are a fundamental data structure based on the Last-In-First-Out (LIFO) principle, widely used in various algorithmic problems. On Day 8, I explored essential stack operations and solved problems that highlight their applications.
1. Implement a Stack Using Arrays
Create a stack data structure from scratch using arrays to support basic operations such as push, pop, and peek. This demonstrates the underlying mechanism of stacks.
import java.util.Scanner;
class Stack{
static int[] st = new int[50];
static int top = 0;
public static void Push(int num){
if(top == st.length-1)
System.out.println("Stack is already full");
else{
top++;
st[top] = num;
Top();
}
}
public static void Pop(){
if(top==0)
System.out.println("Stack is already empty!!");
else
top--;
}
public static void Top(){
if(top==0)
System.out.println("Stack is empty!!!");
else
System.out.println("Element at the top is: "+st[top]);
}
}
public class StackImplementation{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("What action do you want to perform:\n1. Push\n2. Pop\n3. Top");
int num = sc.nextInt();
switch(num){
case 1:
System.out.print("Enter the number you want to push: ");
Stack.Push(sc.nextInt());
break;
case 2:
Stack.Pop();
break;
case 3:
Stack.Top();
break;
default:
System.out.println("Invalid Input!!!!");
break;
}
}
}
}
2. Check for Balanced Parentheses Using a Stack
Use a stack to determine if a given string has balanced parentheses, including {}, [], and (). Push opening brackets onto the stack and check for matching closing brackets.
import java.util.Scanner;
import java.util.Stack;
public class BalancedParenthesis {
public static void main(String[] args) {
Stack<Character> st = new Stack<>();
Scanner sc = new Scanner(System.in);
System.out.println("Enter all Parenthesis: ");
String str = sc.nextLine();
for(char c : str.toCharArray()){
if(c=='}')
st.pop();
else
st.push('{');
}
if(st.isEmpty())
System.out.println("Parenthesis are balanced.");
else
System.out.println("Parenthesis are not balanced.");
}
}
3. Solve the "Next Greater Element" Problem Using a Stack
For each element in an array, find the next greater element to its right. The stack is used to efficiently traverse the array and store potential candidates.
import java.util.Scanner;
import java.util.Stack;
public class NextGreaterElement {
public static void main(String[] args) {
boolean bool = false;
Scanner sc = new Scanner(System.in);
Stack<Integer> st = new Stack<>();
System.out.print("Enter the number of elements in the array: ");
int[] arr = new int[sc.nextInt()];
System.out.println("Enter the elements of the array: ");
for(int i=0; i<arr.length; i++)
arr[i] = sc.nextInt();
System.out.print("Enter the index of the element whose next greatest element you want to find: ");
int index = sc.nextInt();
for(int i=arr.length-1; i>index; i--)
st.push(arr[i]);
while(!st.isEmpty()){
if(st.lastElement()>arr[index]){
System.out.print("Next Greatest Element after "+arr[index]+" is: "+st.lastElement());
bool = true;
st.clear();
}
}
if(!bool)
System.out.println("There exists no greater element after the given element.");
}
}
4. Reverse a String Using a Stack
Reverse the characters of a string by pushing them onto a stack and then popping them off, leveraging the LIFO property.
import java.util.Scanner;
import java.util.Stack;
public class ReverseString {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack<Character> st = new Stack<>();
System.out.print("Enter the string: ");
String str = sc.nextLine();
for(char c:str.toCharArray())
st.push(c);
str="";
while(!st.isEmpty()){
str = str.concat(st.lastElement().toString());
st.pop();
}
System.out.println("Reversed String is: ".concat(str));
}
}
5. Implement a Stack Supporting Push, Pop, and Minimum in O(1)
Design a stack that allows:
Push and pop operations.
Retrieval of the minimum element in O(1) time.
This can be achieved using an auxiliary stack or modifying the main stack's behavior.
import java.util.Scanner;
import java.util.Stack;
class MyStack{
static Stack stack = new Stack();
static Stack min = new Stack();
public static void Push(int num){
if(stack.isEmpty() || num<=Integer.parseInt(min.peek().toString()))
min.push(num);
stack.push(num);
}
public static void Pop(){
if(stack.isEmpty())
System.out.println("Stack is Empty");
else{
int num = Integer.parseInt(stack.peek().toString());
stack.pop();
if(num==Integer.parseInt(stack.peek().toString()));
min.pop();
}
}
public static void Top(){
System.out.println("Element at the top is: ".concat(stack.peek().toString()));
}
public static void Min(){
System.out.println("Smallest Number in the Stack is: ".concat(min.peek().toString()));
}
}
public class SmallestElement{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("What action do you want to perform:\n1. Push\n2. Pop\n3. Top\n4. Get Smallest Number");
int num = sc.nextInt();
switch(num){
case 1:
System.out.print("Enter the number you want to push: ");
MyStack.Push(sc.nextInt());
break;
case 2:
MyStack.Pop();
break;
case 3:
MyStack.Top();
break;
case 4:
MyStack.Min();
break;
default:
System.out.println("Invalid Input!!!!");
break;
}}
}
}
Reflection
Stacks are incredibly versatile and are often the key to solving problems related to parsing, reversing, or traversing. The "next greater element" problem stood out as a great example of optimizing brute force approaches with stacks.
Eager to dive into more data structure problems on Day 9! 🚀