package DataStructures.Stacks;

import java.util.NoSuchElementException;

/** @author Varun Upadhyay (https://github.com/varunu28) */

// An implementation of a Stack using a Linked List

class StackOfLinkedList {

 public static void main(String[] args) {

 LinkedListStack stack = new LinkedListStack();
 stack.push(1);
 stack.push(2);
 stack.push(3);
 stack.push(4);
 stack.push(5);

 System.out.println(stack);

 System.out.println("Size of stack currently is: " + stack.getSize());

 assert stack.pop() == 5;
 assert stack.pop() == 4;

 System.out.println("Top element of stack currently is: " + stack.peek());
 }
}

// A node class

class Node {
 public int data;
 public Node next;

 public Node(int data) {
 this.data = data;
 this.next = null;
 }
}

/**
 * A class which implements a stack using a linked list
 *
 * <p>Contains all the stack methods : push, pop, printStack, isEmpty
 */
class LinkedListStack {

 /** Top of stack */
 Node head;

 /** Size of stack */
 private int size;

 /** Init properties */
 public LinkedListStack() {
 head = null;
 size = 0;
 }

 /**
 * Add element at top
 *
 * @param x to be added
 * @return <tt>true</tt> if add successfully
 */
 public boolean push(int x) {
 Node newNode = new Node(x);
 newNode.next = head;
 head = newNode;
 size++;
 return true;
 }

 /**
 * Pop element at top of stack
 *
 * @return element at top of stack
 * @throws NoSuchElementException if stack is empty
 */
 public int pop() {
 if (size == 0) {
 throw new NoSuchElementException("Empty stack. Nothing to pop");
 }
 Node destroy = head;
 head = head.next;
 int retValue = destroy.data;
 destroy = null; // clear to let GC do it's work
 size--;
 return retValue;
 }

 /**
 * Peek element at top of stack
 *
 * @return element at top of stack
 * @throws NoSuchElementException if stack is empty
 */
 public int peek() {
 if (size == 0) {
 throw new NoSuchElementException("Empty stack. Nothing to pop");
 }
 return head.data;
 }

 @Override
 public String toString() {
 Node cur = head;
 StringBuilder builder = new StringBuilder();
 while (cur != null) {
 builder.append(cur.data).append("->");
 cur = cur.next;
 }
 return builder.replace(builder.length() - 2, builder.length(), "").toString();
 }

 /**
 * Check if stack is empty
 *
 * @return <tt>true</tt> if stack is empty, otherwise <tt>false</tt>
 */
 public boolean isEmpty() {
 return size == 0;
 }

 /**
 * Return size of stack
 *
 * @return size of stack
 */
 public int getSize() {
 return size;
 }
}