User Tools

Site Tools


This is an old revision of the document!


Queue (abstract data type)

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.

Properties

  • $O(1)$ enqueue
  • $O(1)$ dequeue
  • $O(n)$ space

λ Queue_List-based

queue.1459640483.txt.gz · Last modified: 2016/04/02 16:41 by will