Code Destine

Problem Statement

Design a Stack (LIFO) data structure using Linked List. The Stack data structure will supports the following operations:

1. push(N) :- It insert element N onto the top of the stack.
2. pop() :- It removes and returns the element from the top of the stack.
3. peek() :- It returns (not remove) the element from the top of the stack.
4. isEmpty() :- It checks whether the stack is empty or not.
5. size() :- It return the total number of elements.
6. iterator() :- It returns the java iterator object for iterating through the elements of the stack.

Example 

Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.peek(); -- value: 30
stack.pop();  -- value: 30
stack.isEmpty(); -- value: false
stack.size(); -- value: 2

Solution

Each node of linked list will contain two parts :

1. Data Part:- It contains the value to be pushed into the stack.
2. Next Part:- It contains pointer the next value in the stack.

Each operation of the stack will work in the following way:

1. push(N) :- It creates and inserts a new node to the head of the linked list. Node’s data part contains element N, next part contains the current head of the linked list.
2. pop() :- It removes and returns the head node and makes node next to the head node as a new head of the linked list.
3. peek() :- It returns data part of the head node.
4. isEmpty() :- If head of the linked list is null, then returns true otherwise returns false.
5. size() :- It traverses the linked list and count the total number of nodes and return the count.
6. iterator() :- It returns the object of StackIterator class.

Stack Interface

public interface Stack<T> extends Iterable<T> {

	public void push(T t);
	
	public T pop();
	
	public T peek();
	
	public boolean isEmpty();
	
	public int size();
	
}

Stack Implementation

import java.util.Iterator;

public class LinkedListStack<T> implements Stack<T> {

	private Node head;
	
	@Override
	public void push(T t) {
		Node node = head;
		head = new Node();
		head.element = t;
		head.next = node;
	}

	@Override
	public T pop() {
		T t = head.element;
		head = head.next;
		return t;
	}
	
	@Override
	public T peek() {
		if(head != null) {
			return head.element;
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		return head == null;
	}

	@Override
	public int size() {
		Node temp = head;
		int count = 0;
		while(temp != null){
			temp = temp.next; 
			count++;
		}
		return count;
	}
	
	private class Node{
		T element;
		Node next;
	}

	@Override
	public Iterator<T> iterator() {
		return new StackIterator<T>(head);
	}
	
	private class StackIterator<T> implements Iterator<T>{

		private LinkedListStack<T>.Node head;
		
		public StackIterator(LinkedListStack<T>.Node head) {
			super();
			this.head = head;
		}

		@Override
		public boolean hasNext() {
			return head !=null;
		}

		@Override
		public T next() {
			if(head != null){
				T t = head.element;
				head = head.next;
				return t;
			}else {
				throw new RuntimeException("Iterator Exhuested Exception");
			}
		}		
	}
}

Similar Post

1. Design Queue using Linked List
2. Design Stack using Dynamic Array
3. Design Queue using Dynamic Array

That’s all for Design Stack using Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.