1. Introduction
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first element to be removed. Stacks are commonly used in algorithms, data processing, and for many system functionalities like call stack management.
2. Implementation Steps
1. Define a Stack class.
2. Within the class:
- Declare an array of a fixed size or use an ArrayList to store the stack elements.
- Declare a variable top to keep track of the topmost element in the stack.
- Provide methods like push(), pop(), peek(), and isEmpty().
3. Create an instance of the stack class and perform operations to demonstrate its functionality.
3. Implementation in Java
public class Stack<T> {
private int top; // To keep track of the topmost element
private final int capacity = 100; // Maximum size of the stack
private Object[] stack;
// Constructor
public Stack() {
top = -1;
stack = new Object[capacity];
}
// Check if the stack is empty
public boolean isEmpty() {
return top == -1;
}
// Add element to the stack
public void push(T data) {
if (top == capacity - 1) {
System.out.println("Stack is full. Can't push the data.");
return;
}
stack[++top] = data;
}
// Remove and return top element from the stack
public T pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Can't pop.");
return null;
}
return (T) stack[top--];
}
// View top element without removing it
public T peek() {
if (isEmpty()) {
System.out.println("Stack is empty. Nothing to peek.");
return null;
}
return (T) stack[top];
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Top element: " + stack.peek()); // Outputs 30
System.out.println("Popped element: " + stack.pop()); // Outputs 30
System.out.println("Top element after pop: " + stack.peek()); // Outputs 20
}
}
Output:
Top element: 30 Popped element: 30 Top element after pop: 20
Explanation:
1. A generic Stack class is defined. This allows us to use the stack with any data type.
2. An array stack of Objects and a top variable are declared to store stack elements and track the topmost element respectively.
3. The isEmpty() method checks whether the stack is empty by comparing the top variable with -1.
4. The push() method adds an element to the stack. It checks for overflow (when the stack is full) by comparing the top with capacity - 1.
5. The pop() method removes and returns the topmost element from the stack. It checks for underflow (when the stack is empty) using the isEmpty() method.
6. The peek() method returns the topmost element without removing it.
7. In the main() method, we create a Stack of Integers, push three elements onto it, and perform some operations to demonstrate its functionality.