Name some Queue implementations and compare them by efficiency of operations

Technology CommunityCategory: QueuesName some Queue implementations and compare them by efficiency of operations
VietMX Staff asked 3 years ago

An inefficient queue implementation would be a naively-manipulated array, wherein all elements are shifted to accommodate an operation at one end of the array. This would be O(n) for one of the operations (enqueue/dequeue). This is because adding to or removing from the first location (that is, index position 0) is very slow O(n).

To achieve efficient O(1) performance, you can implement a queue as either:

  • a doubly-linked list, which naturally allows you to manipulate each end as a single operation.
  • a “circular dynamic array”, where you keep track of pointers that tells you where the front and back of the queue reside. The “front” and “back” can float around the array arbitrarily. Note there is one subtle complexity. The block of values stored in the collection can wrap around from the end back to the beginning.

The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us to enqueue or dequeue items in O(logn).