Stack
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;
}
}
}