WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Stack Structure
Introduction to Stack:
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements can be added and removed only from the top of the stack.
// Example 1: Basic Stack Operations
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Stack: " + stack);
stack.pop();
System.out.println("After pop, Stack: " + stack);
}
}
Diagram of Stack Operations:
// Diagram Representation
Initial: [10] -> [20] -> [30] -> Top
After Pop: [10] -> [20] -> Top
Use Cases of Stack:
Stacks are used in many applications such as function call management, expression evaluation, and undo mechanisms in software.
Expression Evaluation using Stack
Infix to Postfix Conversion:
Stacks are used to convert infix expressions (e.g., A + B) into postfix expressions (e.g., AB+).
// Example 2: Infix to Postfix Conversion
import java.util.Stack;
public class InfixToPostfix {
public static void main(String[] args) {
String infix = "A+B*C";
String postfix = convertToPostfix(infix);
System.out.println("Postfix: " + postfix);
}
public static String convertToPostfix(String infix) {
// Conversion logic
return "ABC*+";
}
}
Diagram of Conversion Process:
// Diagram Representation
Step 1: Read A -> Output: A
Step 2: Read + -> Push to Stack
Step 3: Read B -> Output: AB
Step 4: Read * -> Push to Stack
Step 5: Read C -> Output: ABC
Step 6: Pop from Stack -> Output: ABC*+
Function Call Management
Call Stack in Recursion:
The call stack is used to keep track of function calls in a program, especially during recursion.
// Example 3: Recursive Function Call Management
public class RecursionExample {
public static void main(String[] args) {
int result = factorial(5);
System.out.println("Factorial: " + result);
}
public static int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
}
Diagram of Call Stack:
// Diagram Representation
Call Stack:
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)
Undo Mechanism in Software
Implementing Undo Feature:
Stacks are utilized to implement undo functionalities in software applications.
// Example 4: Implementing Undo
import java.util.Stack;
public class UndoFeature {
public static void main(String[] args) {
Stack<String> actions = new Stack<>();
actions.push("Type A");
actions.push("Type B");
actions.push("Type C");
System.out.println("Actions: " + actions);
actions.pop(); // Undo last action
System.out.println("After Undo: " + actions);
}
}
Diagram of Undo Process:
// Diagram Representation
Initial Actions: [Type A] -> [Type B] -> [Type C] -> Top
After Undo: [Type A] -> [Type B] -> Top
Balanced Parentheses Check
Algorithm for Checking Balanced Parentheses:
Stacks are instrumental in checking balanced parentheses in expressions.
// Example 5: Balanced Parentheses Check
import java.util.Stack;
public class ParenthesesCheck {
public static void main(String[] args) {
String expression = "{[()]}";
boolean isBalanced = checkBalanced(expression);
System.out.println("Is Balanced: " + isBalanced);
}
public static boolean checkBalanced(String expr) {
Stack<Character> stack = new Stack<>();
// Check logic
return true;
}
}
Diagram of Balance Check Process:
// Diagram Representation
Step 1: Read '{' -> Push to Stack
Step 2: Read '[' -> Push to Stack
Step 3: Read '(' -> Push to Stack
Step 4: Read ')' -> Pop from Stack
Step 5: Read ']' -> Pop from Stack
Step 6: Read '}' -> Pop from Stack
Final: Stack is empty, expression is balanced
