Here are the key Stack Implementation(Array and Linked List):
There are two ways to implement a stack:
1.) Using Array:
In an array-based implementation, the push operation is implemented by incrementing the index of the top element and storing the new element at that index.
The pop operation is implemented by storing the element at the top, decrementing the index of the top element and returning the value stored.
Merits of Stack Implementation Using Arrays:
- It requires no extra memory to store the pointers in stack implementation using an array.
- More efficient in terms of time, compared to stack implementation using linked-list.
Demerits of Stack Implementation Using Arrays:
- The size of the stack is fixed, so it cannot increase and decrease stack implementation using an array.
- Insertion and deletion in an array are quite difficult as it stores the elements in consecutive memory locations.
Code for stack implementation using an Array in java:
public class ArrayStack {
private int[] array;
private int top; // Index of the top element in the stack
private int capacity; // Maximum capacity of the stack
// Constructor to initialize the stack with a given capacity
public ArrayStack(int capacity) {
this.capacity = capacity;
this.array = new int[capacity];
this.top = -1; // Initialize top to -1 to indicate an empty stack
}
// Method to push an element onto the stack
public void push(int element) {
if (isFull()) {
System.out.println("Stack overflow. Cannot push element " + element);
return;
}
array[++top] = element; // Increment top and insert the element into the array
}
// Method to pop the top element from the stack and return it
public int pop() {
if (isEmpty()) {
System.out.println("Stack underflow. Cannot pop element from an empty stack.");
return -1; // Return a default value indicating stack underflow
}
return array[top--]; // Decrement top and return the top element from the array
}
// Method to peek at the top element of the stack without removing it
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty. No element to peek.");
return -1; // Return a default value indicating an empty stack
}
return array[top]; // Return the top element from the array
}
// Method to check if the stack is empty
public boolean isEmpty() {
return top == -1;
}
// Method to check if the stack is full
public boolean isFull() {
return top == capacity - 1;
}
// Main method for testing the stack implementation
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5); // Create a stack with capacity 5
// Push elements onto the stack
stack.push(1);
stack.push(2);
stack.push(3);
// Print the stack
System.out.println("Stack: ");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
// Try popping from an empty stack
stack.pop();
}
}Using Linked list:
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
Merits of Stack Implementation Using Linked List
- The size of the stack can be increased or decreased dynamically by adding or removing nodes from the linked list, without the need to allocate a fixed amount of memory for the stack upfront.
- Since nodes in a Single linked list only have a next pointer and not a pre pointer, they use less memory than nodes in a doubly linked list.
- Linked lists can be used to implement a wide range of data structures, including stacks, queues, associative arrays, and graphs, as well as linked data structures such as trees and hash tables.
Demerits of Stack Implementation Using Linked List
- The memory used by Linked List is more because we also need to store the address of the next data.
- We can not access any element of the Linked List directly. We don’t have direct access to every element of Linked List.
- Linked lists can be more complex to implement than other data structures, such as arrays or stacks
Code for stack implementation using Linked List in java:
import java.util.LinkedList;
public class LinkedListStack<T> {
private LinkedList<T> stack;
public LinkedListStack() {
stack = new LinkedList<>();
}
// Push operation: Add an element to the top of the stack
public void push(T element) {
stack.addLast(element);
}
// Pop operation: Remove and return the top element from the stack
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack.removeLast();
}
// Peek operation: Return the top element of the stack without removing it
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack.getLast();
}
// Check if the stack is empty
public boolean isEmpty() {
return stack.isEmpty();
}
// Get the size of the stack
public int size() {
return stack.size();
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
// Push elements onto the stack
stack.push(1);
stack.push(2);
stack.push(3);
// Print the stack
System.out.println("Stack: ");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
// Try popping from an empty stack
// stack.pop(); // This would throw an exception since the stack is empty
}
}
