Stack Using Linked List - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using linked list. Push and pop operations are done on the first element. This takes constant time for any operation and about ~36N Bytes for N stack items - 16B overhead + 8B inner Node class + 8B reference to Node object + 4B for integer values.

Following is the program:

	package stacks;
	public class StackLL {
	private Node first = null;
	static int size = 0;
	public class Node{
	int value;
	Node next;
	}
	public void push(int val) {//insert at the beginning of the LL
	Node n1 = new Node();
	n1.value = val;
	n1.next = first;
	first = n1;
	size++;
	}
	public int pop() {//pop the first ele - LIFO
	if(isEmpty()) {
	System.out.println("stack empty");
	return Integer.MIN_VALUE;
	}
	int val = first.value;
	first = first.next;
	size--;
	return val;
	}
	public int size() {
	return size;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public void print() {
	System.out.println("============================================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	StackLL stack = new StackLL();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	}
	}

view raw StackLL.java hosted with ❤ by GitHub