TIL - Today I Learned
Search…
Computer Science
Software Engineering
Personal Development
TIL - Today I Learned
Queue
A Queue is a linear data structure that keeps its elements in a queue. It uses FIFO (first-in-first-out) ordering in which elements are added to the "end" and are removed from the "front".
Description
A Queue is a linear data structure that keeps its elements in a queue. It means that one end of a queue is used to add data into it and another end is used to remove data from it.
We often use queues in our everyday life. For example, queue at the supermarket, queue at the airport, and so on...
This ordering mechanism is also called FIFO (first-in-first-out) in which the first added element is processed first and the newest added element is processed last.
A Queue is like an array but with a few restrictions:
- You can't randomly access an item by its index.
- You can only add data in one end and retrieve data from the other.
Base operations
Operation
Description
enqueue(item)add an item to the end of a queue
dequeue()remove the first item in a queue
peek()get an element that is in the front of a queue
When to use
It can be used for any task where the first data/job that arrives needs to be processed first (FIFO). For example, it's possible to use a queue to upload images one by one in the order they arrived.
Time Complexity
Operation
Complexity
Insertion
O(1)
Deletion
O(1)
*Access
O(n)
*To access some value you need to remove elements that are first in a queue.
Code
Queue.ts
1
import { LinkedList } from '../LinkedList/LinkedList';
2
3
export class Queue<T> {
4
private storage = new LinkedList<T>();
5
6
/**
7
* Add a new element to the end of the queue.
8
* This element will be processed after all elements that are already in the queue.
9
*/
10
public enqueue(value: T): void {
11
this.storage.append(value);
12
}
13
14
/** Remove the element that is at the front of queue. */
15
public dequeue(): T | null {
16
return this.storage.deleteHead()?.value || null;
17
}
18
19
/** Read the element at the front of the queue without removing it */
20
public peek(): T {
21
return this.storage.getFirst()?.value || null;
22
}
23
24
public isEmpty(): boolean {
25
return !this.storage.getFirst();
26
}
27
28
public size(): number {
29
return this.storage.toArray().length;
30
}
31
32
public toString(callback?: (val: T) => string): string {
33
return this.storage.toString(callback);
34
}
35
}
Copied!
Links:
Last modified 1yr ago
Copy link