Friday, February 15, 2019

Stack Implementation in Java Using Linked List

In this post we’ll see an implementation of Stack in Java using Linked list. Stack can also be implemented using array but that has one drawback that the stack size is fixed in that case.

Stack data structure

A stack is a Last In First Out (LIFO) data structure. In a stack items are both inserted and removed from the top and you have access to a single data item; that is the last item inserted. Once that is retrieved then only you can access the next item.

Following image shows the items in a Stack.

Java program for stack

Operations in a Stack

Mainly following three operations are implemented for a Stack-

  1. push- To insert an item on the stack.
  2. pop- To remove an item from the top of the stack.
  3. peek- Read value from the top of the stack without removing it.

Java program for Stack using Linked list

For representing nodes of the linked list a separate class (private class Node in the program) is used which apart from the data also holds a reference to itself.

There is also one reference top which always points to the first node of the Linked list (top of the stack).

For push operation new nodes are inserted in the beginning of the Linked list and the top references the new node.

For pop operation first node in the Linked list is removed and the top starts referencing to the next node.

public class LinkedListStack {
    //Reference for the top of the stack
    Node top;
    public LinkedListStack(){
        top = null;
    }
    //Class representing each node
    private class Node{
        //data
        int i;
        //ref to next node
        Node next;
        Node(int i){
            this.i = i;
        }
        public void displayData(){
            System.out.println("i= " + i);
        }
    }
    
    public void insertNode(int i){
        //Create a new node
        Node newNode = new Node(i);
        // current top is pushed down
        newNode.next = top;
        // newly inserted node is referenced by top
        top = newNode;
    }
    
    public int removeNode(){        
        Node temp = top;
        // Next item in the stack is referenced by top
        top = top.next;
        return temp.i;
    }
    
    public int nodeData(){
        return top.i;
    }
    
    public boolean isEmpty(){
        return top == null;
    }
    
    public void push(int item){
        insertNode(item);
    }
    public int pop(){
        // If no item is inserted
        if(isEmpty()){
            throw new RuntimeException("Stack is Empty");
        }
        return removeNode();
    }
    
    public int peek(){
        // If no item is inserted
        if(isEmpty()){
            throw new RuntimeException("Stack is Empty");
        }
        return nodeData();
    }
    
    public void displayStack(){
        // start from the top
        Node current = top;
        // traverse the list
        while(current != null){
            current.displayData();
            current = current.next;
        }
    }
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        System.out.println("Item peeked- " + stack.peek());
        System.out.println("Items in stack--");
        stack.displayStack();
        System.out.println("Item popped- " + stack.pop());
        System.out.println("Item popped- " + stack.pop());
        System.out.println("Item peeked- " + stack.peek());
        System.out.println("Items in stack--");
        stack.displayStack();
    }
}

Output

Item peeked- 40
Items in stack--
i= 40
i= 30
i= 20
i= 10
Item popped- 40
Item popped- 30
Item peeked- 20
Items in stack--
i= 20
i= 10

That's all for this topic Stack Implementation in Java Using Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Counting Sort Program in Java
  2. Java Program to Delete a Node From Binary Search Tree (BST)
  3. How to Create Your Own BlockingQueue - Java Program
  4. How to Find Common Elements Between Two Arrays - Java Program
  5. Find Duplicate Characters in a String With Repetition Count - Java Program

You may also like-

  1. Invoking Getters And Setters Using Reflection - Java Program
  2. Converting double to int in Java
  3. How to Create PDF From XML Using Apache FOP
  4. Creating Tar File And GZipping Multiple Files - Java Program
  5. Varargs in Java
  6. Bounded Type Parameter in Java Generics
  7. finally Block in Java Exception Handling
  8. Introduction to Hadoop Framework