Java Program to Implement a Stack Using Linked List

Introduction

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Unlike arrays, which have a fixed size, a linked list-based stack dynamically grows and shrinks as elements are added or removed. This guide will walk you through writing a Java program that implements a stack using a singly linked list. The stack operations include push, pop, peek, and checking if the stack is empty.

Problem Statement

Create a Java program that:

• Implements a stack using a linked list.
• Provides methods to perform standard stack operations: push, pop, peek, and isEmpty.
• Displays the stack contents after various operations.

Example:

• Input: Push elements: 10, 20, 30
• Operations: push(40), pop(), peek()
• Output:
  • After pushing 40: 40 -> 30 -> 20 -> 10 -> null
  • After popping: 30 -> 20 -> 10 -> null
  • Peeked element: 30

Solution Steps

1. Create the Node Structure: Define a Node class to represent each element in the stack.
2. Create the Stack Structure: Define a Stack class to represent the stack using a linked list, including methods for standard stack operations.
3. Implement Stack Operations: Implement methods to push elements onto the stack, pop elements from the stack, peek at the top element, and check if the stack is empty.
4. Display the Stack: Output the stack’s contents after performing various operations.

Java Program

// Java Program to Implement a Stack Using Linked List // Author: https://www.rameshfadatare.com/ // Step 1: Define the Node class to represent each element in the stack class Node { int data; Node next; // Constructor to initialize the node public Node(int data) { this.data = data; this.next = null; } } // Step 2: Define the Stack class to manage the stack operations using a linked list class Stack { private Node top; // Constructor to initialize the stack (initially empty) public Stack() { this.top = null; } // Step 3: Method to push an element onto the stack public void push(int value) { // Create a new node with the given value Node newNode = new Node(value); // Point the new node's next to the current top newNode.next = top; // Update the top to point to the new node top = newNode; System.out.println("Pushed " + value + " onto the stack."); } // Step 4: Method to pop an element from the stack public int pop() { if (isEmpty()) { System.out.println("Stack is empty. Unable to pop."); return -1; // Return a sentinel value indicating the stack is empty } else { // Retrieve the top element's data int poppedValue = top.data; // Update the top to point to the next node top = top.next; System.out.println("Popped " + poppedValue + " from the stack."); return poppedValue; } } // Step 5: Method to peek at the top element of the stack public int peek() { if (isEmpty()) { System.out.println("Stack is empty. Nothing to peek."); return -1; // Return a sentinel value indicating the stack is empty } else { System.out.println("Peeked at the top element: " + top.data); return top.data; } } // Step 6: Method to check if the stack is empty public boolean isEmpty() { return (top == null); } // Step 7: Method to display the contents of the stack public void display() { if (isEmpty()) { System.out.println("Stack is empty."); } else { System.out.print("Stack contents: "); Node current = top; while (current != null) { System.out.print(current.data + " -> "); current = current.next; } System.out.println("null"); } } } public class StackDemo { public static void main(String[] args) { Stack stack = new Stack(); // Create a stack // Push elements onto the stack stack.push(10); stack.push(20); stack.push(30); stack.display(); // Push another element stack.push(40); stack.display(); // Pop an element from the stack stack.pop(); stack.display(); // Peek at the top element stack.peek(); stack.display(); // Pop all elements to test underflow stack.pop(); stack.pop(); stack.pop(); stack.pop(); // This pop should trigger an underflow condition stack.display(); } } 

Explanation

Step 1: Define the Node Class

• The Node class represents a single element in the stack. Each node contains data and a reference to the next node (next).
• The constructor initializes the node with data and sets the next pointer to null.

Step 2: Define the Stack Class

• The Stack class manages the stack operations using a linked list. The class contains a top node that points to the top of the stack.
• The stack is initialized as empty, with top set to null.

Step 3: Push an Element onto the Stack

• The push() method adds a new node to the top of the stack:
  • A new node is created with the given value.
  • The new node’s next pointer is set to the current top.
  • The top is updated to point to the new node.

Step 4: Pop an Element from the Stack

• The pop() method removes and returns the top element of the stack:
  • If the stack is empty, an underflow message is displayed.
  • Otherwise, the top element’s data is returned, and top is updated to point to the next node.

Step 5: Peek at the Top Element of the Stack

• The peek() method returns the top element without removing it:
  • If the stack is empty, an appropriate message is displayed.
  • Otherwise, the top element’s data is returned.

Step 6: Check if the Stack is Empty

• The isEmpty() method checks if the stack is empty by verifying if top is null.

Step 7: Display the Stack Contents

• The display() method prints all elements currently in the stack:
  • The stack is traversed from the top to the bottom, printing each element’s data.

Output Example

Pushed 10 onto the stack. Pushed 20 onto the stack. Pushed 30 onto the stack. Stack contents: 30 -> 20 -> 10 -> null Pushed 40 onto the stack. Stack contents: 40 -> 30 -> 20 -> 10 -> null Popped 40 from the stack. Stack contents: 30 -> 20 -> 10 -> null Peeked at the top element: 30 Stack contents: 30 -> 20 -> 10 -> null Popped 30 from the stack. Popped 20 from the stack. Popped 10 from the stack. Stack is empty. Unable to pop. Stack is empty. 

Conclusion

This Java program demonstrates how to implement a stack using a linked list, including handling underflow conditions when attempting to pop from an empty stack. The program efficiently manages stack operations, providing dynamic growth and shrinkage, unlike array-based stacks. This exercise is valuable for understanding how to implement and manipulate stacks using linked lists in Java programming.