A stack mimics a stack of paper. You add and remove things from the top. This is also known as “Last In, First Out” (LIFO).


Note that you shouldn’t need to (or be able to) iterate through a stack. Knowing the size of the stack may also be optional.



A list can sometimes be used to mimic a stack:

Other language libraries use another ADT to implement a stack:

Since lists can be used to implement a stack, it follows that they can also be implemented directly using list implementation techniques.


Reversing a string:

Stack machines, like an interpreter for Reverse Polish Notation.

The shunting-yard algorithm parses infix expression (1 + 2) to produce postfix ones (RPN) or an AST. Uses both stack and queue.

TODO: Backtracking

Compilers & Interpreters:

Virtual (stack) machines:


Class Stack<E>. Java Collections stack.

stack<T, Sequence>. C++ STL stack.

Using Lists as Stacks. Data Structures. Python.

Array. Javascript reference. MDN.