User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
stack [2014/07/10 23:10]
will
stack [2016/04/03 00:08] (current)
will [Properties]
Line 1: Line 1:
-====== Stack ======+====== Stack (abstract data type) ======
  
-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.+A stack is a abstract ​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.
  
 ===== Array Based ===== ===== 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.+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.
  
 ==== Properties ==== ==== Properties ====
Line 10: Line 12:
   * $O(1)$ pop   * $O(1)$ pop
   * $O(n)$ space   * $O(n)$ space
 +
 +This is written out long-hand for demonstration,​ a pure Javascript array which has native ''​push''​ and ''​pop''​ is a better solution.
  
 [algorithm Stack array-based] [algorithm 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.
 +
 +==== Properties ====
 +  * $O(1)$ push
 +  * $O(1)$ pop
 +  * $O(n)$ space
 +
 +[algorithm Stack List-based]
stack.1405059027.txt.gz · Last modified: 2015/02/02 08:24 (external edit)