A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element inserted into the stack is the first one to be removed. It can be visualized as a stack of plates, where the last plate placed on top is the first one to be taken out.
Example: Imagine a stack of books. If we want to take a book, we can only remove the topmost book first before accessing the ones below it.
Types of Stacks
There are two primary types of stacks:
- Static Stack: This type of stack has a fixed size. Once the size is set, it cannot be changed.
- Dynamic Stack: This stack can grow and shrink in size based on the number of elements it holds, usually implemented using linked lists.
Declaration & Initialization
In Java, a stack can be declared and initialized using the Stack class from the java.util package. Here’s how to declare and initialize a stack:
|
1 2 3 |
import java.util.Stack; Stack<Integer> stack = new Stack<>(); |
Basic Operations
Here are the basic operations that can be performed on a stack:
- Push: Add an element to the top of the stack.
- Pop: Remove and return the top element from the stack.
- Peek (Top): View the top element without removing it.
- isEmpty: Check if the stack is empty.
- isFull: Check if the stack is full (applicable in fixed-size stacks).
Stack Implementation using Array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Stack { private int arr[]; private int top; private int capacity; // Constructor to initialize stack Stack(int size) { arr = new int[size]; capacity = size; top = -1; // Stack is empty } // Push operation public void push(int data) { if (top == capacity - 1) { System.out.println("Stack Overflow! Cannot push " + data); return; } arr[++top] = data; } // Pop operation public int pop() { if (top == -1) { System.out.println("Stack Underflow! No elements to pop."); return -1; } return arr[top--]; } // Peek operation public int peek() { if (top == -1) { System.out.println("Stack is empty."); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } } // Usage Example public class StackExample { public static void main(String[] args) { Stack stack = new Stack(5); stack.push(10); stack.push(20); stack.push(30); System.out.println("Top element: " + stack.peek()); System.out.println("Popped element: " + stack.pop()); System.out.println("Is stack empty? " + stack.isEmpty()); } } |
Stack Implementation Using Java’s Built-in Stack Class
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import java.util.Stack; public class StackExample { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // Push elements stack.push(10); stack.push(20); stack.push(30); // Peek top element System.out.println("Top element: " + stack.peek()); // Pop element System.out.println("Popped element: " + stack.pop()); // Check if empty System.out.println("Is stack empty? " + stack.isEmpty()); } } |
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| Simple to implement and use. | Limited in size (for static stacks). |
| Helps in undo functionality in applications. | Can result in stack overflow if memory is exhausted. |
| Efficient for recursive function calls. | Only the top element can be accessed directly. |
| Useful in parsing expressions (e.g., parentheses). | Not suitable for random access to elements. |
Real-world Examples
- Undo/Redo Functionality: In applications like text editors, a stack is used to store the actions and their reversals, allowing the user to undo or redo actions.
- Expression Evaluation: Stacks are commonly used in parsing and evaluating mathematical expressions, such as converting infix to postfix or evaluating postfix expressions.
- Browser History: Stacks are used to store the pages visited in a web browser. When we press the “Back” button, the most recent page is popped from the stack.
