Implement Stack Using Singly Linked List

Source: https://algorithms.tutorialhorizon.com/implement-stack-using-linked-list/

Objective:

Write an algorithm to implement Stack using Linked List.

If you do not know about then for starters its abstract data type in which follows the principle of LIFO (Last-In-First-Out) which means the data goes in last comes out first to read about in detail please read this link Stack

Approach:

Solution is quite simple, Earlier we have seen an article “Linked List Implementation“, we need to make some changes to make it work as Stack.

Stack Operations:

push() :Insert the element into linked list at the beginning and increase the size of the list. O(1) operation.

pop() :Return the element first node from the linked list and move the head pointer to the second node. Decrease the size of the list. O(1) operation.

getSize(): Return the size of linked list.

displayStack(): Print the linked list.

Solution

Algorithms@tutorialhorizon

https://algorithms.tutorialhorizon.com/implement-stack-using-linked-list/

public class StackUsingLinkedList {
    Node head= null;
    int size =0;

    public void push(int data){
        Node x = new Node(data);
        if(getSize()==0){
            head = x;
        }else{
            //add the Node at the start of a Linked List
            Node temp = head;
            x.next = temp;
            head = x;
        }
        System.out.println("Element "+ data + " is pushed into Stack");
        size++;
    }

    public int pop(){
        if(getSize()==0){
            System.out.println("Stack is Empty");
            return -1;
        }else{
            Node temp = head;
            head = head.next;
            size--;
            return temp.data;
        }

    }

    public void printStack(){
        Node curr = head;
        while(curr!=null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }
    public int getSize(){
        return size;
    }

    public static void main(String[] args) {
        StackUsingLinkedList stck = new StackUsingLinkedList();
        stck.push(1);
        stck.push(2);
        stck.push(4);
        stck.printStack();
        System.out.println("Pop out element " + stck.pop());
        stck.printStack();
    }
}
class Node{
    int data;
    Node next;
    public Node(int data){
        this.data = data;
    }
}

GeeksforGeeks:

https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/

// Java program to Implement a stack 
// using singly linked list 
// import package 
import static java.lang.System.exit; 

// Create Stack Using Linked list 
class StackUsingLinkedlist { 

    // A linked list node 
    private class Node { 

        int data; // integer data 
        Node link; // reference variavle Node type 
    } 
    // create globle top reference variable 
    Node top; 
    // Constructor 
    StackUsingLinkedlist() 
    { 
        this.top = null; 
    } 

    // Utility function to add an element x in the stack 
    public void push(int x) // insert at the beginning 
    { 
        // create new node temp and allocate memory 
        Node temp = new Node(); 

        // check if stack (heap) is full. Then inserting an 
        // element would lead to stack overflow 
        if (temp == null) { 
            System.out.print("\nHeap Overflow"); 
            return; 
        } 

        // initialize data into temp data field 
        temp.data = x; 

        // put top reference into temp link 
        temp.link = top; 

        // update top reference 
        top = temp; 
    } 

    // Utility function to check if the stack is empty or not 
    public boolean isEmpty() 
    { 
        return top == null; 
    } 

    // Utility function to return top element in a stack 
    public int peek() 
    { 
        // check for empty stack 
        if (!isEmpty()) { 
            return top.data; 
        } 
        else { 
            System.out.println("Stack is empty"); 
            return -1; 
        } 
    } 

    // Utility function to pop top element from the stack 
    public void pop() // remove at the beginning 
    { 
        // check for stack underflow 
        if (top == null) { 
            System.out.print("\nStack Underflow"); 
            return; 
        } 

        // update the top pointer to point to the next node 
        top = (top).link; 
    } 

    public void display() 
    { 
        // check for stack underflow 
        if (top == null) { 
            System.out.printf("\nStack Underflow"); 
            exit(1); 
        } 
        else { 
            Node temp = top; 
            while (temp != null) { 

                // print node data 
                System.out.printf("%d->", temp.data); 

                // assign temp link to temp 
                temp = temp.link; 
            } 
        } 
    } 
} 
// main class 
public class GFG { 
    public static void main(String[] args) 
    { 
        // create Object of Implementing class 
        StackUsingLinkedlist obj = new StackUsingLinkedlist(); 
        // insert Stack value 
        obj.push(11); 
        obj.push(22); 
        obj.push(33); 
        obj.push(44); 

        // print Stack elements 
        obj.display(); 

        // pritn Top element of Stack 
        System.out.printf("\nTop element is %d\n", obj.peek()); 

        // Delete top element of Stack 
        obj.pop(); 
        obj.pop(); 

        // pritn Stack elements 
        obj.display(); 

        // print Top element of Stack 
        System.out.printf("\nTop element is %d\n", obj.peek()); 
    } 
}

Reference

https://algorithms.tutorialhorizon.com/implement-stack-using-linked-list/

https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/