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.
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.
The array based implementation works by keeping a two arrays
right. Dequeue is even though it includes a
reverse operation. This is because the reverse happens at a frequency.
- Amortized dequeue