#SideNotes — Queue — Abstract Data Type and Data Structure

I’m just a regular person who believes life is simple, and I like a simple life.

In this #sidenotes we will talk about the Queue as an Abstract Data Type and as a Data Structure.

Abstract data types, commonly abbreviated ADTs, are a way of classifying data structures based on how they are used and the behaviors they provide. They do not specify how the data structure must be implemented but simply provide a minimal expected interface and set of behaviors.

Data Structure is a concrete implementation of a data type. It’s possible to analyze the time and memory complexity of a Data Structure but not from a data type. The Data Structure can be implemented in several ways and its implementation may vary from language to language.

Queue — Abstract Data Type

This abstract data type holds a collection of elements where they are added to the back of the queue and removed from the front of the queue. The principle by which a queue is ordered is called FIFO (first-in first-out).

Queue representation. https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

The first element inserted in the queue would be the first element removed from the queue.

The Queue and Stack are similar but they follow different principles when comes to the how the inserts and removes are manipulated.

The Queue is a known principle in our daily lives when we go shopping we need to be in a queue to the cashier. The first in the queue is the first to leave, the last in the queue is the last to leave.

ADT — Interface

The Queue interface can be implemented in different ways, is important to have operations to queue a new element and to dequeue an element:

# Main operations
enqueue(element)         -> Add an element to the queue
dequeue()                -> Remove the element from the queue
isEmpty()                -> Check if the queue is empty

Since abstract data types don’t specify an implementation, this means it’s also incorrect to talk about the time complexity of a given abstract data type.

ADT — Operations

Traversal : You must be thinking, “how could I print all the elements of a Queue?”
A Queue can be traversed , is possible to navigate in the queue using the dequeue the element to remove from the top until the queue is empty.

queue = Queue()
queue.enqueue(1)  # 1 is added to the back queue
queue.enqueue(2)  # 2 is added to the back queue
queue.enqueue(3)  # 3 is added to the back queue
# Queue looks like = Queue(1, 2, 3)
while the is not queue.isEmpty()
    print queue.dequeue()
# The elements will be printed in this order: 1-> 2 -> 3

This is an abstract operation and the implementation will define how you interact with the Stack.

Double-Ended Queues & Priority Queues

Double-ended queues, called deques for short, are a generalized form of the queue. It is exactly like a queue except that elements can be added to or removed from the back or front.

Priority queues are a kind of abstract data type that generalizes the queue. Their principles are exactly the same except that they also include a priority for every value in the queue. When a value is inserted, a priority is assigned to it. The value with the highest priority is always removed first.

Queue — Data Structure

Implementation

A queue can be implemented using data structures like arrays (circular queue), dynamic arrays, singly linked list, or doubly linked list. It all depends on the performance needed in the queue and enqueue .

To have in mind: the Double-ended queues are usually implemented with Doubly linked list to have O(1) in the enqueue and dequeue. They can also be implemented using a dynamic array with a performance change in the dequeue to O(n). The Priority queues are implemented using a heap structure, we will not talk much here about this because we will see it in the further side notes.

C — Implementation using a LinkedList

In this implementation, we are using the data structure LinkedList to achieve the desired behavior.

The enqueue process is appending to the end of the Queue and the dequeue is removing the first item in the Queue.

Complexity

O(1) -> enqueue, dequeue, isEmpty

The complexity is O(1) for enqueue, dequeue and isEmpty this is achieved because we use a LinkedList and the push and pop of a LinkedList is also O(1). An implementation using an Array with append and pop would not result in the same performance. We could use an array to implement a Circular Queue but we would have a limitation on the size of the queue.

Useful links

Queue (abstract data type) - Wikipedia

https://en.wikipedia.org/wiki/Double-ended_queue

Priority queue - Wikipedia

https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/