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
queue [2015/02/02 08:28]
127.0.0.1 external edit
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.1422894502.txt.gz · Last modified: 2016/04/02 16:41 (external edit)