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
Last revision Both sides next revision
stack [2015/02/02 08:28]
127.0.0.1 external edit
stack [2016/04/02 23:23]
will
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.
- +
-===== Properties ===== +
-  * $O(1)$ push +
-  * $O(1)$ pop +
-  * $O(n)$ space+
  
 ===== Array Based ===== ===== Array Based =====
Line 12: Line 7:
  
 Both this visualisation and the list based visualisation start with a stack that has had "​A",​ "​B",​ "​C"​ pushed onto it in  order. Both this visualisation and the list based visualisation start with a stack that has had "​A",​ "​B",​ "​C"​ pushed onto it in  order.
 +
 +==== Properties ====
 +  * $O(1)$ push
 +  * $O(1)$ pop
 +  * $O(n)$ space
  
 [algorithm Stack array-based] [algorithm Stack array-based]
Line 18: Line 18:
 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. 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.
  
-[algorithm Stack List-based]+==== Properties ==== 
 +  * $O(1)$ push 
 +  * $O(1)$ pop 
 +  * $O(n)$ space
  
 +[algorithm Stack List-based]
stack.txt · Last modified: 2016/04/03 00:08 by will