Stack in Java

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle, meaning
the last element added to the stack is the first one to be removed.

Characteristics of a Stack
1. Operations:

o Push: Add an element to the top of the stack.

o Pop: Remove the top element from the stack.

o Peek/Top: View the top element without removing it.

o isEmpty: Check if the stack is empty.

2. Real-World Examples:

o Plates stacked in a cafeteria (you remove the top plate first).

o Undo/Redo functionality in text editors.

3. Applications:
o Expression evaluation (infix, postfix, prefix).

o Function call management (recursion).

o Depth-first search in graph traversal.

Example: Stack Using Java's Built-in Class

The java.util.Stack class is a part of Java's Collection Framework.

import java.util.Stack;

public class StackExample {

public static void main(String[] args) {

Stack<Integer> stack = new Stack<>();

// Push elements onto the stack

 stack.push(10);

stack.push(20);

stack.push(30);

System.out.println("Stack after pushes: " + stack);

// Peek the top element

System.out.println("Top element: " + stack.peek());

// Pop elements from the stack

System.out.println("Popped: " + stack.pop());

System.out.println("Stack after pop: " + stack);

// Check if stack is empty

System.out.println("Is stack empty? " + stack.isEmpty());

// Search for an element (1-based index)

System.out.println("Position of 10 in stack: " + stack.search(10));

Sample Output
Stack after pushes: [10, 20, 30]

Top element: 30

Popped: 30

Stack after pop: [10, 20]

Is stack empty? false

Position of 10 in stack: 2
Custom Stack Implementation
If you want to implement your own stack, you can use an array or linked list.

Using Array
class Stack {
private int[] arr;

private int top;

private int capacity;

// Constructor
public Stack(int size) {

arr = new int[size];

capacity = size;
top = -1;

// Push an element

public void push(int value) {

if (isFull()) {

System.out.println("Stack Overflow!");
return;

arr[++top] = value;

System.out.println(value + " pushed onto stack.");

// Pop an element
public int pop() {
 if (isEmpty()) {

System.out.println("Stack Underflow!");

return -1;

}
return arr[top--];

// Peek the top element

public int peek() {

if (!isEmpty()) {

return arr[top];

}
return -1;

// Check if the stack is empty

public boolean isEmpty() {

return top == -1;

// Check if the stack is full

public boolean isFull() {

return top == capacity - 1;

public class CustomStackDemo {

 public static void main(String[] args) {

Stack stack = new Stack(3);

stack.push(10);
stack.push(20);

stack.push(30);

stack.push(40); // This will cause overflow

System.out.println("Top element: " + stack.peek());

System.out.println("Popped: " + stack.pop());

System.out.println("Popped: " + stack.pop());

System.out.println("Popped: " + stack.pop());

System.out.println("Popped: " + stack.pop()); // This will cause underflow

Sample Output
10 pushed onto stack.

20 pushed onto stack.

30 pushed onto stack.

Stack Overflow!

Top element: 30

Popped: 30

Popped: 20

Popped: 10

Stack Underflow!

Assignments
 1. Reverse a String Using a Stack:

o Implement a program to reverse a string using a stack.

2. Balanced Parentheses:

o Write a program to check if an expression has balanced parentheses using a stack.

o Example: {[()()]} is balanced, while {[(])} is not.

3. Stack-Based Expression Evaluation:

o Evaluate a postfix expression using a stack.

o Example: Input: 23*54*+, Output: 29.

4. Design a Stack with Minimum Functionality:

o Implement a stack that supports retrieving the minimum element in O(1)O(1)
time.

5. Implement Two Stacks in One Array:

o Implement two stacks using a single array.

Code: Stack Implementation Using Arrays

// Stack class using an array

class Stack {

private int[] stackArray; // Array to store stack elements

private int top; // Index of the top element

private int capacity; // Maximum capacity of the stack

// Constructor to initialize the stack

public Stack(int size) {

stackArray = new int[size];

capacity = size;
top = -1; // Stack is initially empty
}

// Push operation: Adds an element to the top of the stack

public void push(int value) {

if (isFull()) {

System.out.println("Stack Overflow! Unable to push " + value);

return;

stackArray[++top] = value; // Increment top and add the value

System.out.println(value + " pushed to the stack.");

// Pop operation: Removes and returns the top element of the stack

public int pop() {

if (isEmpty()) {

System.out.println("Stack Underflow! Stack is empty.");

return -1;

System.out.println(stackArray[top] + " popped from the stack.");

return stackArray[top--]; // Return the top element and decrement top

// Peek operation: Returns the top element without removing it

public int peek() {

if (isEmpty()) {

System.out.println("Stack is empty. No element to peek.");

return -1;
 }

return stackArray[top];

// isEmpty operation: Checks if the stack is empty

public boolean isEmpty() {

return top == -1;

// isFull operation: Checks if the stack is full

public boolean isFull() {

return top == capacity - 1;

}

// Display operation: Prints the stack elements

public void display() {

if (isEmpty()) {

System.out.println("Stack is empty!");

return;
}

System.out.print("Stack elements: ");

for (int i = 0; i <= top; i++) {

System.out.print(stackArray[i] + " ");

System.out.println();

}
}
// Main class to test the Stack implementation

public class ArrayStackDemo {

public static void main(String[] args) {

Stack stack = new Stack(5); // Stack with a capacity of 5

stack.push(10); // Push elements to the stack

stack.push(20);

stack.push(30);

stack.display(); // Display the stack elements

System.out.println("Top element is: " + stack.peek()); // Peek the top element

stack.pop(); // Pop elements from the stack

stack.display();

stack.pop();

stack.pop();
stack.pop(); // Attempt to pop from an empty stack

stack.push(40);

stack.push(50);

stack.push(60);

stack.push(70);

stack.push(80);
stack.push(90); // Attempt to push into a full stack
 }

Explanation of the Code

1. Push Operation:

o Adds an element to the stack.

o Checks if the stack is full (isFull method).

o If not full, increments the top and inserts the element.

2. Pop Operation:
o Removes and returns the top element of the stack.

o Checks if the stack is empty (isEmpty method).

o If not empty, retrieves the top element and decrements top.

3. Peek Operation:

o Returns the top element without modifying the stack.

o Checks if the stack is empty before accessing the element.

4. Helper Methods:

o isEmpty: Returns true if the top index is -1.

o isFull: Returns true if the top index is equal to capacity - 1.

5. Display Method:
o Iterates through the array from index 0 to top to print the stack elements.

Sample Output
10 pushed to the stack.

20 pushed to the stack.

30 pushed to the stack.

Stack elements: 10 20 30
Top element is: 30
30 popped from the stack.

Stack elements: 10 20

20 popped from the stack.

10 popped from the stack.

Stack Underflow! Stack is empty.

40 pushed to the stack.

50 pushed to the stack.

60 pushed to the stack.

70 pushed to the stack.

80 pushed to the stack.

Stack Overflow! Unable to push 90

Key Points
 The capacity of the stack is fixed in this implementation.

 If you need a dynamic stack (resizable), consider using ArrayList or LinkedList.

Practice Assignments
1. Dynamic Stack Implementation:

o Modify the above code to resize the stack array when it gets full.
2. Reverse a String:

o Use this stack implementation to reverse a string.

3. Palindrome Check:

o Use a stack to check if a given string is a palindrome.

4. Postfix Expression Evaluation:

o Write a program to evaluate a postfix expression using the stack.

5. Minimum Element in a Stack:

 o Extend the stack to support a getMin() operation that returns the minimum
element in O(1)O(1) time.

Balanced Parentheses Using Stack in Java

A string with parentheses is considered balanced if:

1. Every opening parenthesis ((, {, [) has a corresponding closing parenthesis (), }, ]).

2. The parentheses are properly nested.

Algorithm
1. Traverse the string character by character.

2. Push every opening parenthesis ((, {, [) onto the stack.

3. For every closing parenthesis:

o Check if the stack is empty (if yes, it's unbalanced).

o Pop the top of the stack and ensure it matches the current closing parenthesis.
4. After traversing the string, check if the stack is empty. If not, it's unbalanced.

Code Implementation
import java.util.Stack;

public class BalancedParentheses {

// Method to check if parentheses are balanced

public static boolean isBalanced(String expression) {

Stack<Character> stack = new Stack<>(); // Stack to hold opening brackets

for (int i = 0; i < expression.length(); i++) {

char current = expression.charAt(i);

 // Push opening brackets onto the stack

if (current == '(' || current == '{' || current == '[') {

stack.push(current);

}
// Check for closing brackets

else if (current == ')' || current == '}' || current == ']') {

// If stack is empty, it's unbalanced

if (stack.isEmpty()) {

return false;
}

// Pop the top element and check if it matches the current closing bracket
char top = stack.pop();

if (!isMatchingPair(top, current)) {

return false;

// If stack is empty, it's balanced; otherwise, it's not

return stack.isEmpty();

// Helper method to check if two brackets are matching pairs

private static boolean isMatchingPair(char open, char close) {

return (open == '(' && close == ')') ||

(open == '{' && close == '}') ||
 (open == '[' && close == ']');

// Main method for testing

public static void main(String[] args) {

String expression1 = "{[()]}";

String expression2 = "{[(])}";

String expression3 = "{[(";

System.out.println(expression1 + " -> " + (isBalanced(expression1) ? "Balanced" : "Not

Balanced"));

System.out.println(expression2 + " -> " + (isBalanced(expression2) ? "Balanced" : "Not

Balanced"));

System.out.println(expression3 + " -> " + (isBalanced(expression3) ? "Balanced" : "Not

Balanced"));

Explanation of the Code

1. Stack Usage:

o A stack is used to store opening brackets ((, {, [) as they appear in the string.

o When a closing bracket is encountered (), }, ]), the top of the stack is checked and
popped if it matches.

2. isMatchingPair Method:

o Ensures that the popped opening bracket corresponds to the current closing
bracket.

3. Edge Cases:

o If the string starts with a closing bracket, the stack will be empty, and the method
will return false.
 o If the stack is not empty after processing the string, it indicates unmatched
opening brackets.

Sample Input/Output

Input:
{[()]} -> Balanced

{[(])} -> Not Balanced

{[( -> Not Balanced

Output:
{[()]} -> Balanced

{[(])} -> Not Balanced

{[( -> Not Balanced

Practice Assignments
1. Extend the Program:

o Modify the program to handle additional characters in the string (e.g., a + b * (c -

d)).

2. Parentheses Count:

o Write a program to count the number of opening and closing parentheses in a

string and verify if they're equal.

3. Fix Unbalanced Parentheses:

o Create a program that can suggest corrections for an unbalanced string (e.g., ({[}
→ ({[]})).

Evaluate Postfix Expressions Using Stack in Java

A postfix expression (also known as Reverse Polish Notation) is a mathematical expression
where the operators follow their operands. For example:

 Infix: (3 + 4) * 5

 Postfix: 3 4 + 5 *
To evaluate a postfix expression:
 1. Traverse the expression from left to right.

2. Push operands onto the stack.

3. When an operator is encountered:

o Pop the required number of operands from the stack.

o Perform the operation.

o Push the result back onto the stack.

4. At the end, the stack contains the result.

Code Implementation
import java.util.Stack;

public class PostfixEvaluation {

// Method to evaluate a postfix expression

public static int evaluatePostfix(String expression) {

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < expression.length(); i++) {

char current = expression.charAt(i);

// If the current character is a space, skip it

if (current == ' ') {

continue;

// If the current character is a digit, push it onto the stack

if (Character.isDigit(current)) {
// Convert character to integer and push
 stack.push(current - '0');

// If the current character is an operator, perform the operation

else {
int operand2 = stack.pop(); // Second operand

int operand1 = stack.pop(); // First operand

switch (current) {

case '+':
stack.push(operand1 + operand2);

break;

case '-':
stack.push(operand1 - operand2);

break;

case '*':

stack.push(operand1 * operand2);

break;

case '/':

stack.push(operand1 / operand2);
break;

default:

throw new IllegalArgumentException("Invalid operator: " + current);

// The final result will be the only element left in the stack
 return stack.pop();

// Main method to test the evaluation

public static void main(String[] args) {

String expression1 = "3 4 + 5 *"; // Equivalent to (3 + 4) * 5 = 35

String expression2 = "6 3 / 2 * 1 +"; // Equivalent to ((6 / 3) * 2) + 1 = 5

String expression3 = "5 1 2 + 4 * + 3 -"; // Equivalent to 5 + ((1 + 2) * 4) - 3 = 14

System.out.println("Result of '" + expression1 + "' is: " + evaluatePostfix(expression1));

System.out.println("Result of '" + expression2 + "' is: " + evaluatePostfix(expression2));

System.out.println("Result of '" + expression3 + "' is: " + evaluatePostfix(expression3));

}

Explanation of the Code

1. Stack Usage:

o The stack is used to temporarily store operands. Operators act on these operands
to produce intermediate results, which are also stored on the stack.

2. Operands:

o When a digit is encountered, it is converted from a character to an integer and

pushed onto the stack.

3. Operators:

o When an operator is encountered, the top two elements of the stack are popped.
o The operation is performed, and the result is pushed back onto the stack.

4. Final Result:

o After processing the entire expression, the stack contains only one element, which
is the final result.
 5. Edge Cases:

o The expression must be valid. If the stack is empty or contains less than two
elements during an operator evaluation, an error will occur.

Sample Input/Output

Input:
Expression: "3 4 + 5 *"

Output:
Result of '3 4 + 5 *' is: 35

Input:
Expression: "6 3 / 2 * 1 +"

Output:
Result of '6 3 / 2 * 1 +' is: 5

Practice Assignments
1. Support Floating Point Numbers:

o Modify the program to handle floating-point numbers.

2. Infix to Postfix Conversion:

o Write a program to convert an infix expression (e.g., (3 + 4) * 5) to a postfix

expression.
3. Error Handling:

o Add error handling for cases like division by zero or invalid expressions.

4. Operator Precedence:

o Enhance the program to handle operator precedence during evaluation (though

this is typically done during infix to postfix conversion).

5. Evaluate Prefix Expression:

o Implement a similar program to evaluate prefix expressions.