HGPA

stacks

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).

Requirements

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.

Conceptualization

Implementation

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.

Applications

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:

REFERENCES

Class Stack<E>. Java Collections stack.

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

Using Lists as Stacks. Data Structures. Python.

Array. Javascript reference. MDN.

Filename: stacks.md (Edit)
Modified: 2016-12-12 (8f86a817a2957fbe35ef496e67a7c1ae917d3095)
Created: 2016-12-12 (8f86a817a2957fbe35ef496e67a7c1ae917d3095)