A stack is a LIFO (Last In First Out) or equivalently a FILO (First In Last Out) data structure. It finds use in a number of situations including the Depth-First Search in graph theory and the actual system stack on processors where it is useful because the last function to be called should be the first one to finish (and thus it's local variables should be removed first).

A stack's mechanism is best understood as a stack of dinner plates (perhaps this is where the name came from). When you put a new plate onto the stack it is somewhat of an ordeal to remove plates in the middle of the stack. The natural method of course is to take things in order back off the top. It should be noted that if you push values onto a stack and then pop them off it reverses their order.

As the main operations of a stack are push and pop the most common implementation is a dynamic array. This causes the following complexities:

Operation | Complexity | Description |
---|---|---|

push | $O(1)$ | adds an element to top of stack |

pop | $O(1)$ | removes an element from top of stack |

Stacks are built-in in java in java.util.Stack.

public static void main(String[] args) throws IOException { Stack s = new java.util.Stack(); // Let's add some items to the stack s.push("a"); s.push("b"); s.push("c"); s.push("d"); // Let's pop them off s.pop(); // d s.pop(); // c // Checking whether or not it's empty if(!s.empty()) { s.pop(); // b } // Its size (inherited from Vector) s.size(); // 1 }