Stacks: Array Representation &
Linked List Implementation
Includes Java Code Examples
Introduction to Stacks
• A stack is a linear data structure following the
LIFO (Last In, First Out) principle.
• Elements are added (PUSH) and removed
(POP) from the top of the stack.
• Applications: Function calls, Expression
evaluation, Undo operations.
Array Representation of Stack
• Stack can be implemented using an array.
• Requires predefined size.
• Operations: Push, Pop, Peek.
Java Code: Stack using Array
// Stack Implementation using Array in Java } OUTPUT:
public class Main {
Pushed: 1
private int arr[]; // Array to store stack elements // Method to pop an element from the stack
private int top; // Top of the stack public int pop() { Pushed: 2
private int capacity; // Maximum capacity of the stack if (top == -1) { // Check for stack underflow Popped: 2
System.out.println("Stack Underflow");
// Constructor to initialize the stack return -1;
public Main(int size) { }
arr = new int[size]; // Create an array of given size System.out.println("Popped: " + arr[top]);
capacity = size; // Set stack capacity return arr[top--]; // Return top element and decrement
top = -1; // Initialize top to -1 (stack is empty) top
} }
// Method to push an element onto the stack // Main method to test stack operations
public void push(int x) { public static void main(String[] args) {
if (top == capacity - 1) { // Check for stack overflow Main stack = new Main(5); // Create a stack of size 5
System.out.println("Stack Overflow");
return; stack.push(1); // Push 1 onto the stack
} stack.push(2); // Push 2 onto the stack
arr[++top] = x; // Increment top and insert element stack.pop(); // Pop the top element (should remove 2)
System.out.println("Pushed: " + x); }
}
Stack Implementation Using Linked List
• Stack can also be implemented using a linked
list.
• Dynamic size, no need for a predefined
capacity.
• Operations: Push, Pop, Peek (peek means
retrieving the top element without removing it).
Java Code: Stack using Linked List
// Stack Implementation using Linked List in Java // Method to pop an element from the stack
public int pop() {
// Class representing a node in the linked list if (top == null) { // Check for stack underflow
class Node { System.out.println("Stack Underflow");
int data; // Data stored in the node return -1;
Node next; // Pointer to the next node }
int data = top.data; // Get the top element
// Constructor to initialize node top = top.next; // Move top pointer to next node
Node(int data) { OUTPUT: System.out.println("Popped: " + data);
this.data = data;
Pushed: 10 return data;
this.next = null; }
} Pushed: 20
} Popped: 20 // Main method to test stack operations
public static void main(String[] args) {
// Class representing a stack using a linked list Main stack = new Main(); // Create stack instance
public class Main {
private Node top; // Pointer to the top of the stack stack.push(10); // Push 10 onto the stack
stack.push(20); // Push 20 onto the stack
// Method to push an element onto the stack
public void push(int x) { stack.pop(); // Pop the top element (should remove 20)
Node newNode = new Node(x); // Create a new node }
newNode.next = top; // Link new node to the top }
top = newNode; // Update top to the new node
System.out.println("Pushed: " + x);
}
Java Code: Stack using Linked List
with import java.util.*
import java.util.LinkedList; // Method to pop an element from the stack
public int pop() {
// Class representing a stack using Java's built-in LinkedList if (stack.isEmpty()) { // Check for stack underflow
public class Main { System.out.println("Stack Underflow");
private LinkedList<Integer> stack; // Using LinkedList as a return -1;
stack }
int data = stack.removeFirst(); // Remove element from
// Constructor to initialize the stack OUTPUT: the front
public Main() { Pushed: 10 System.out.println("Popped: " + data);
stack = new LinkedList<>(); Pushed: 20 return data;
} Popped: 20 }
// Main method to test stack operations
// Method to push an element onto the stack public static void main(String[] args) {
public void push(int x) { Main stack = new Main(); // Create stack instance
stack.addFirst(x); // Add element at the front (top of stack.push(10); // Push 10 onto the stack
the stack) stack.push(20); // Push 20 onto the stack
System.out.println("Pushed: " + x); stack.pop(); // Pop the top element (should remove
} 20)
}
}
Java Code: Stack using Linked List
using peek
// Stack Implementation with Peek Operation int data = top.data;
class Node { top = top.next;
int data; System.out.println("Popped: " + data);
Node next; OUTPUT: return data;
Pushed: 10 }
Node(int data) {
this.data = data; Pushed: 20 // Peek operation - returns the top element without removing it
this.next = null; Pushed: 30 public int peek() {
} if (top == null) {
} Peek: 30 System.out.println("Stack is empty");
Popped: 30 return -1;
public class Main { }
private Node top; Peek after pop: 20 return top.data;
}
// Push operation
public void push(int x) { public static void main(String[] args) {
Node newNode = new Node(x); Main stack = new Main();
newNode.next = top;
top = newNode; stack.push(10);
System.out.println("Pushed: " + x); stack.push(20);
} stack.push(30);
// Pop operation System.out.println("Peek: " + stack.peek()); // Should return 30
public int pop() {
if (top == null) { stack.pop();
System.out.println("Stack Underflow"); System.out.println("Peek after pop: " + stack.peek()); // Should return 20
return -1; }
} }
Advantages & Disadvantages
• **Array-based Stack**: Fast access but fixed
size.
• **Linked List Stack**: Dynamic size but extra
memory for pointers.
• Stack is simple to implement but prone to
overflow (array) or extra memory usage (linked
list).
Conclusion
• Stacks follow LIFO principle.
• Can be implemented using arrays or linked
lists.
• Choice depends on memory constraints and
usage requirements.
