Abstract Data Type

Queue (FIFO)

In a queue, the element deleted is always the one that has been in the set for the longest time. The queue implements a first-in, first-out (FIFO) policy.

Basic Operations → each operation is $O(1)$ time using a Linked List

• enter - adds an element to the end of the queue
• leave - removes the element at the beginning of the queue:
• first - gets the first element
• isEmpty - checks if queue is empty

Implementation

Implement it using a Linked List, that points to both head and tail.

• Add new values to tail
• Remove values from head
• Get value from head

You can do it with a Dynamic Array, but it is not very efficient, since you need shift all the elements indices by 1 every time you call leave.

Both Python and C++ implement it using a Deque.

Language Specific

Python

from collections import deque
queue = deque()
 
# Adding elements
queue.append(23)
queue.append(3)
 
# Removing Elements
queue.popleft()
 
 
queue.empty() #Check if empty

C++ (uses a Deque)

queue<int> q;
q.push(3);
q.push(2);
q.push(5);
cout << q.front(); // 3
q.pop();
cout << q.front(); // 2

printing a queue

while (!q.empty()) {
	cout << q.front() << endl;
	q.pop();
}

Stack vs. Queue (memory trick)

https://www.youtube.com/watch?v=2wM6_PuBIxY&ab_channel=CS50 This video above helped me remember the difference between a stack and a queue.