# Differences

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

 queue [2014/07/12 22:31]will created queue [2016/04/03 00:20] (current)will 2016/04/03 00:20 will 2016/04/02 16:41 will 2015/02/02 08:28 external edit2014/07/12 22:31 will created Next revision Previous revision 2016/04/03 00:20 will 2016/04/02 16:41 will 2015/02/02 08:28 external edit2014/07/12 22:31 will created 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)