User Tools

Site Tools


Differences

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

Link to this comparison view

Next revision
Previous revision
queue [2014/07/12 22:31]
will created
queue [2016/04/03 00:20] (current)
will
Line 1: Line 1:
-====== Queue ======+====== Queue (abstract data type) ======
  
-A queue is a collection data type where the primary operations are ''​enqueue''​ which adds an element and ''​dequeue''​ which removes. It is a First-In-First-Out (FIFO) data structure, the first element pushed must be the first one removed.+A queue is a abstract ​collection data type where the primary operations are ''​enqueue''​ which adds an element and ''​dequeue''​ which removes. It is a First-In-First-Out (FIFO) data structure, the first element pushed must be the first one removed.
  
-===== Properties ​=====+===== Linked List Based ===== 
 +The [[Linked List]] based implementation works by keeping a pointer to the start and end of the list. Dequeueing removes the first element of the list, much like the linked list [[stack]], enqueueing utilises the pointer to the end of the list to add an item at the end of the list in constant time. 
 + 
 +==== Properties ​====
   * $O(1)$ enqueue   * $O(1)$ enqueue
   * $O(1)$ dequeue   * $O(1)$ dequeue
   * $O(n)$ space   * $O(n)$ space
- 
-===== Linked List Based ===== 
-The [[Linked List]] based implementation works by keeping a pointer to the start and end of the list. Dequeueing removes the first element of the list, much like the linked list [[stack]], enqueueing utilises the pointer to the end of the list to add an item at the end of the list in constant time. 
  
 [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.1405229467.txt.gz · Last modified: 2015/02/02 08:24 (external edit)