Stack is one of the most simple data structure. It's based on a LIFO – last in, first out – principle, which means, that the elemen inserted (push) into the structure as the last one, will be removed (pop) as the first one.

Opposite approach called FIFO – first in, first out – is used in the queue data structure.

## Abstract data type stack

The stack abstract data type specifies these operations:

- push – Insert the element at the top of the stack.
- pop – Remove the elements, which is at the top of the stack.
- top – Return the element at the top of the stack.
- isEmpty – Query whether the stack does not contain any element.

## Usage

Stack is usually used for storing state in programs and algorithms. It is used in the Tarjan's algorithm, depth-first search or implicitly in all recursive algorithms. Stack-based architecture is also used in virtual machines of several programming languages – for example Java and Lisp.

## Code

/** * Stack * Implemented as a linked list */ public class Stack { private Node first; private int size; public Stack() { this.size = 0; } /** * Inserts the element at the top of the stack * Complexity - O(1) * @param i element to be stored */ public void push(int i) { Node n = new Node(i); Node currFirst = first; first = n; n.next = currFirst; size++; } /** * Removes the element, which is at the top of the stack * Complexity - O(1) * @return value of the element */ public int pop() { if (size == 0) { throw new IllegalStateException("Stack is empty"); } int value = first.value; first = first.next; size--; return value; } /** * Return the value of the element at the top of the stack * Complexity - O(1) * @return value of the element at the top of the stack */ public int top() { if (size == 0) { throw new IllegalStateException("Stack is empty"); } return first.value; } /** * Returns the size of the stack * @return size of the stack */ public int getSize() { return this.size; } @Override public String toString() { StringBuilder builder = new StringBuilder(); Node curr = first; for (int i = 0; i < this.size; i++) { builder.append(curr.value).append(" "); curr = curr.next; } return builder.toString(); } /** * Inner represantation of the element (node of the linked list) */ private class Node { private int value; private Node next; private Node(int value) { this.value = value; } } }