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
queue [2016/04/02 16:41]
will
queue [2016/04/03 00:20] (current)
will
Line 12: Line 12:
  
 [algorithm Queue List-based] [algorithm Queue List-based]
 +
 +===== Array Based =====
 +The array based implementation works by keeping a two arrays ''​left''​ and ''​right''​. Dequeue is $O(1)$ even though it includes a $O(n)$ ''​reverse''​ operation. This is because the reverse happens at a $1/n$ frequency.
 +
 +==== Properties ====
 +  * $O(1)$ enqueue
 +  * Amortized $O(1)$ dequeue
 +  * $O(n)$ space
 +
 +[algorithm Queue Array-based]
queue.txt ยท Last modified: 2016/04/03 00:20 by will