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).
- view top of the stack:
- remove top of the stack:
- this may or may not return the top item
- add to the top of the stack:
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.
- Keep track of the head, or top of the stack
A list can sometimes be used to mimic a stack:
- for a Python list:
list[-1]to access top
array[array.length - 1]to access top
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:
- iterate through a string pushing each letter onto stack
- pop off all elements into a new 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.
Compilers & Interpreters:
- space for parameters, local variables, and return address of each function call (stack frame)
- compiler's syntax check for matching braces
Virtual (stack) machines:
- JVM (Java, Clojure, Scala, Groovy)
- CLR & Mono (C#)
- CPython (Python)
- Ruby MRI (>=1.9)
Class Stack<E>. Java Collections stack.
stack<T, Sequence>. C++ STL stack.
Using Lists as Stacks. Data Structures. Python.