Linked List: Program to implement a stack using linked list


Write a program to implement a stack like data structure using linked list

Stack is a data structure that follows LIFO (last in first out) rule
For implementing the stack using a linked list we will perform all operations of the stack

 
  • push(): it pushes the given element into the stack
  • peek(): this operation returns the element which is at the top(an element that enters last)
  • pop(): this operation deletes the top element of the stack
  • display(): this operation simply displays all elements of the stack
 
  • We implement the above operations on a LinkedList such that we derive the LIFO property of the stack
  • push(): add elements to the head of LinkedList
  • pop(): remove elements from the head of LinkedList
  • peek(): show a head element of LinkedList
  • display(): iterate LinkedList from head and print elements
 
Approach
  1. push()
    • Create new node current and current.data = given element
    • If the current is NULL then the stack is full/overflow so, cannot push
    • Else make current.next = top
    • And set-top on current
  2. peek()
    • If top is NULL then the print stack is empty and simply returns
    • Else return top.data
  3. pop()
    • If top is NULL then the print stack is empty and simply returns
    • Else set top = top.next
  4. display()
    • If top is NULL then simply return
    • Create a pointer say current and point on top
    • Print all elements of stack till current is not NULL
 
Complexity

Time Complexity : O(1)
Space Complexity : O(n) , where n is the size of linked list

 
Java Code
class LinkedListAsStack{
	
        class Node {
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
                this.next = null;
            }
        }
    
        Node top;
     
        public void push(int element) {
            Node current = new Node(element);
            current.next = top;
            top = current;
        }
     
        public int peek() {
            if (top == null) {
                System.out.println("Stack is Empty");
                return -1;
            } else {
                return top.data;
            }
        }
     
        public void pop() {
            if (top == null) {
                System.out.println("Stack is Empty");
                return;
            } else {
                top = top.next;
            }
        }
     
        public void display() {
            if (top == null) {
                System.out.println("Stack is Empty");
                return;
            }
            Node current = top;
            while (current != null) {
                System.out.print(current.data + "\n");
                current = current.next;
            }
        }
     
        public static void main(String[] args) {
            LinkedListAsStack ss = new LinkedListAsStack();
            ss.push(10);
            ss.push(20);
            ss.push(30);
            ss.push(40);
            ss.push(50);
            ss.push(60);
            System.out.println("Element at peek in the stack is " + ss.peek());
            System.out.println("Original Stack");
            ss.display();
            System.out.println("Stack after pop operation");
            ss.pop();
            ss.display();
        }
    
 }
Output

Element at peek in the stack is 60
Original Stack
60
50
40
30
20
10
Stack after pop operation
50
40
30
20
10



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list