User Tools

Site Tools

This is an old revision of the document!


A stack is a collection data type where the primary operations are push which adds an element and pop which removes. It is a Last-In-First-Out (LIFO) data structure, the last element pushed must be the first one popped.


  • $O(1)$ push
  • $O(1)$ pop
  • $O(n)$ space

Array Based

An array implementation uses an simple array and items are added and removed from the end of the array. In a language without dynamic arrays, the stack would keep track of the number of items and the available space, when the stack runs out of space the array would be reallocated to provide more space. In Javascript the array data structure is dynamically resized and the stack implementation is very simple. Arrays in Javascript provide native push and pop functions, for this visualisation these are reimplemented.

Both this visualisation and the list based visualisation start with a stack that has had “A”, “B”, “C” pushed onto it in order.

λ Stack_array-based

Linked List Based

The Linked List based implementation is also simple. A push adds a new node onto the front of a list, and pop removes the front of the list.

λ Stack_List-based

stack.1422894502.txt.gz · Last modified: 2016/04/02 23:23 (external edit)