A queue uses FIFO (first-in-first-out) ordering, that is, items are removed from the queue in the same order that they are added, like a line. Queues can be used whenever is necessary to process things in that order (FIFO), like requests to a single shared resource, CPU scheduling, also helps in algorithms of other data structures, such as breadth-first search in graphs.
Representation
A queue can be implemented using an array or a linked list, can be either fixed or dynamic size.
Basic operations
- Add - Add an item to the end of the queue, also called enqueue.
- Remove - Remove the first item from the queue, also called dequeue.
- Peek - Return the top of the queue, without removing it.
- isEmpty - Return true if the queue is empty.
- isFull - Return true if the stack is full, used when the queue is fixed size.
Here's an implementation of a queue using an array, in TypeScript an array doesn't have a fixed length, so the operation isFull is not required, however, you can implement a queue with a fixed length and use that operation.
1class Queue<T> {
2 private array: T[] = [];
3
4 add(data: T): void {
5 this.array.push(data);
6 }
7
8 remove(): T | undefined {
9 if (this.isEmpty()) throw new EmptyQueueException();
10
11 return this.array.shift();
12 }
13
14 peek(): T {
15 if (this.isEmpty()) throw new EmptyQueueException();
16
17 return this.array[0];
18 }
19
20 isEmpty(): boolean {
21 return this.array.length === 0;
22 }
23}
