Tagged
• Data Structure
• Stack
•

# Introduction

Stack is a linear data structure to store and manipulate data which follows LIFO (Last In First Out) order during adding and removing elements in it. There are two basic ways to implement stack data structure :

In this post we are going to discuss about linked list based implementation of stack data structure. Before proceeding with this post, it is highly recommended to understand what is linked list and how stack operations are performed.

# Prerequisite

In a linked list, whenever we want to add/delete an element we either add/delete at the beginning or at random position or at the end of the linked list. Whereas in case of stack we do restrict add/delete at only one endpoint which is at the end as it follows Last In First Out ordering. So the last node is always the key element for stack operations.

# Algorithm

Stack algorithm is defined in terms of adding an element which is called Push and deleting an element from the stack which is called Pop.

Initialization : Add variable last which points to the last node of the linked list. If there are no elements in the stack, it points to null.

## Push Operation

1. Create a new node for the data given. Let us assume newly created node as newNode
2. If stack is empty (no elements left in the stack)
• initialize last to newNode
3. Else
• in this case newNode will be the last element and the current last element will be the oldLast element.
• update newNode as the last element.
• the last element next points to the oldLast element.
```1void push(int data) : 2      Node newNode = new Node(data)  3
4      if(last == null) : 5        last = newNode   6
7      else : 8        // store oldLast pointer 9        Node oldLast = last 10
11         // update newNode as the last element12        last = newNode 13
14        // add connection to oldLast element 15        last.next = oldLast ```

## Pop Operation

1. If stack is empty (last == null)
• throw exception
2. Else
• remove the last element
• It means second last element will be the last element which is last.next
```1int pop() : 2    if(last == null) :   3      throw exception 4
5    else :   6      Node top = last 7
8      // remove last element by updating last to next element  9      last = last.next 10    11    return top.data  ```

# Dry Run

To understand push and pop operations clearly, let us perform below operations. Let us consider we have few balls and we want to place them or delete them on request basis in a container (stack)

# Java Implementation

```1public class StackUsingLinkedList {2  private Node last ;3
4  public void push(int data){5    // create new node for the given data6    Node newNode = new Node(data);7
8    //check stack is empty or not9    if(isEmpty()){10      // initialize last to newly created node11      last = newNode;12    }13    // if stack is not empty14    else {15      Node oldLast = last;16
17      // newNode will be always on top18      // and is obviously last element19      last = newNode;20
21      // add link to oldLast element22      // as last node next element23      last.next = oldLast;24    }25  }26
27  public int pop(){28    // if stack is empty throw exception29    if(isEmpty()){30      throw new RuntimeException("Stack is Empty");31    }32    // take data of the last element33    int data = last.data;34
35    // remove last element by36    // updating last to it's next element37    last = last.next;38
39    //return data40    return data;41  }42
43  // to check which element is on top44  public int peek(){45    if(isEmpty()){46      throw new RuntimeException("Stack is Empty");47    }48    // as stack is not empty49    // last element is always on top of stack50    return last.data;51  }52
53  // code to check the stack is empty or not54  public boolean isEmpty(){55    return last == null;56  }57
58  // node class59  private static class Node{60    Node next;61    int data;62
63    Node(int data){64      this.data = data;65    }66  }67
68  public static void main(String[] args) {69    StackUsingLinkedList obj = new StackUsingLinkedList();70
71    int data = 20;72    obj.push(data);73    System.out.println("Top Element After pushing "+data+" >>>>  "+obj.peek());74
75    data = 30;76    obj.push(data);77    System.out.println("Top Element After pushing "+data+" >>>>  "+obj.peek());78
79    data = 45;80    obj.push(data);81    System.out.println("Top Element After pushing "+data+" >>>>  "+obj.peek());82
83    // As last element is 45, obj.pop should remove 4584    // and top element should be at 3085    System.out.println("POP >> "+obj.pop());86    System.out.println("Top Element After pop is "+obj.peek());87  }88}```

• Data Structure
• Stack