Stack
Stack

Stack is one of the most simple data structure. It's based on a LIFOlast 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 FIFOfirst 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;
        }
    }
}








       
 

Place for your banner

Here is the position ready for our customer's banners.