In this article I will first implement a queue in typescript and will display data saved in the queue using Angular. Later on I will talk about priority queues and implement it using a similar logic. The idea is to display another type of queue where the elements will have a priority which will determine who will be pulled first.
Queue is a FIFO (First In First Out) data structure. Let’s think of a group of customers in the shop waiting to buy coffee. The one who arrived first will be served first. All the customers arriving will be waiting at the end of the line until everyone who came before will be served.
Queue Terminology and Operations
- enqueue: Add a new element at the collection.
- dequeue: Remove and returns the least recently-added element.
- peek: Retrieve the least recently-added element without removing it.
- isEmpty: Checks if the collection has no elements.
When implementing a queue it is important that all the operations should be executed in constant time, O(1) complexity. With that being said, contrary to stack, we can not use arrays to implement a queue because either in enqueue or dequeue we will have to shift the elements so the complexity will be O(N).
For the above mentioned reasons I have implemented a generic Queue using Linked List. This is the node definition:
export class Node<T> {
value: T;
next: Node<T>;
}Each node has a value and a pointer to the next node. Here is the Queue implementation:
export class Queue<T> {
private head: Node<T>;
private tail: Node<T>;
public enqueue(value: T): Node<T> { }
public dequeue(): Node<T> { }
public peek(): T { }
public isEmpty(): boolean { }
public get data(): [] { }
}As we can see the queue includes all the operations such as enqueue, dequeue, peek and a check if the queue is empty. I have also added a method to get data so that I can display them in the application. Since adding and removing new elements of the queue needs to be done in constant time we need to keep track of the head and the tail of the linked list. When adding new elements the tail will be updated and when removing the head will be updated.
You can find the queue implementation in this Stack Blitz Link. I have also displayed the queue state after each operation as below. As you will see, by clicking the Enqueue button new elements will be added at the end of the queue and by clicking Dequeue the first added elements will be removed.
Priority Queue
The above explanation works where the client to be served is the next in line. Let’s suppose there is a rule that indicates the elder people have a higher priority to be served first. At this moment, regardless of the time they came, the oldest will be getting their coffee first. The above implementation can not be used for this case.
A priority queue is an abstract data type in which each element has additionally a priority associated with it. In a priority queue, an element with higher priority will be served before an element with lower priority.
If we consider the coffee example, the age will be the priority to determine who will get the coffee first. There are different kinds of implementations for the priority queue. First is using a sorted list, whenever a new element is added it will check the position to be inserted considering the priority. Secondly you can implement it using an unordered list, but when a dequeue happens it will check which element to remove by priority assigned. The third implementation is using a heap. I have chosen the first implementation. Each of them have different advantages in add and remove elements as below.
Let’s analyze the first implementation. When adding a new element in a sorted list we will need to iterate all the elements until we find it’s correct position. For this reason insertion takes linear time. While removing elements is constant because the element with the higher priority will be at the beginning of the list.
Priority Queue Implementation using Sorted Linked List
The difference between the priority queue and queue nodes, will be that the first will need to keep track of the priority value. So the node definition will be:
export class PriorityNode<T> {
value: T;
priority: number;
next: PriorityNode<T>;
}Again the priority queue will define all the operations like: enqueue, dequeue, peek, and is empty. The enqueue will now include managing the insertion at the right position. Here is the definition:
export class PriorityQueue<T> {
private head: PriorityNode<T>;
private tail: PriorityNode<T>; public enqueue(value: T, priority: number): PriorityNode<T> { }
public dequeue(): PriorityNode<T> {}
public peek(): T { }
public isEmpty(): boolean { }
public get data() { }
}
As you will see, by clicking the Enqueue button new elements will be added to the collection and by clicking Dequeue the one with the higher priority will be removed. As you can see even why a new customer with age 92 came last, he will be served first because age is the priority in this case.
In the Stack Blitz Link you can see the code and the behaviour of priority queue, otherwise if you want to access only the application where you could see the queue and priority queue behaviour you could go here: Stack Blitz App.
Conclusions
To sum up, we created a new queue using Typescript and then visualized the operations using Angular. After a detailed explanation we went over the priority queue and its implementation in Typescript using sorted list. Hope you found this article helpful and let me know your thoughts.
Originally published at http://agdev.tech on March 9, 2021.
