Data Structures: Queues

This flashcard set covers the Queue Abstract Data Type (ADT), its operations, Python implementation details using circular arrays, and time complexity.

Queue ADT

A data structure that stores arbitrary objects where insertions and deletions follow the first-in first-out (FIFO) scheme.

FIFO

Acronym for first-in first-out, meaning insertions are performed at the rear and removals are performed at the front.

enqueue(object)

A main queue operation that inserts an element at the end of the queue.

dequeue()

A main queue operation that removes and returns the element at the front of the queue.

first()

An auxiliary operation that returns the element at the front of the queue without removing it.

len()

An auxiliary operation that returns the integer number of elements stored in the queue.

is_empty()

A boolean auxiliary operation that indicates whether no elements are stored.

EmptyQueueException

The exception thrown when attempting the execution of dequeue or front on an empty queue.

Circular fashion

The use of an array of fixed size $N$ to store queue elements to avoid shifting elements up when an element is removed from position 0.

f

A variable tracking the index of the front element in an array-based queue implementation.

size

A variable tracking the current number of elements in the queue.

r

In diagram representations, this variable represents the index of the first element after the end of the queue, calculated using $(f + ext{size}) ext{ mod len}(Q)$, where the queue may be in normal or wrapped-around configuration.

Wrapped-around configuration

A state in circular array implementations where the rear index precedes the front index because the queue has wrapped around the end of the array.

resize(n)

An algorithm that occurs when the number of elements equals the capacity of the list ($ext{size} = ext{len}(Q)$), involving copying elements to a new list of capacity $n$, typically using $2 imes ext{len}(Q)$.

_data

A reference to a Python list instance with a fixed capacity used as the underlying storage structure for the queue.

_size

An integer instance variable representing the current number of elements stored in the queue as opposed to the length of the data list.

_front

An integer representing the index within data of the first element of the queue.

DEFAULT_CAPACITY

A constant set to $10$ providing a moderate capacity for all new ArrayQueue instances.

O(1)

The time complexity for all standard queue operations including enqueue(e), dequeue(), first(), is_empty(), and len(Q).

Dequeue (as an ADT)

An abstract data type that allows elements to be added and deleted from both the front and back of the queue.