Queue implementation using TypeScript
A queue is an abstract data type that serves as a collection of elements, with two principal operations: enqueue, which adds an element to the collection, and dequeue, which removes the earliest added element. The order in which elements are dequeued is First In First Out aka. FIFO. The term queue takes it name from the real world queues e.g. "a queue at the ticket counter".
A good target is to implement these operations with a time complexity of O(1). In this lesson we discuss how to implement it using JavaScript / TypeScript.
[00:00] A queue is a first-in/first-out collection data structure with a time complexity of O(1) for key operations. We can easily model this in TypeScript using a generic class for items of type T.
[00:21] A queue has two key operations -- enqueue, which adds an item to the queue in a time complexity of O(1), and then there is the dequeue operation, which removes the first item that was added to the queue, again in a time complexity of O(1).
[00:39] If there are no more items in the queue, then it can return something that is out of bound, for example, undefined. Of course, this information can be encoded as a return value for the dequeue method of the queue class.
[00:53] We can naively try and implement this data structure using the JavaScript array. For example, we go ahead and store the items internally as an array of type T, in a member called Tara. Whenever the enqueue operation is called, we simply push the item into this array. Whenever we have to dequeue, we shift out the first item from the array.
[01:24] However, this implementation is incorrect because in JavaScript arrays implementations, shift requires changing the index of any remaining elements in the array. Therefore, this implementation has an average runtime of O(n) and thus does not meet our O(1) operation cost requirement.
[01:44] Not all is lost, though, because we can implement a queue by internally using a map. Here, we simply use a null prototype object as a map. With this map, we will need to track the valid range of indexes in the form of the last dequeued index, as well as the next enqueue index. Both of these, we initialize to zero.
[02:09] Whenever we need to enqueue a new item, we will store the item at the current next enqueue index within the internal data map, followed by incrementing the next enqueue index for any future calls to enqueue.
[02:26] Whenever there is a call to dequeue, we simply check if the last dequeued index hasn't caught up to the next enqueue index. If it has, then we let the default return of undefined handle that scenario.
[02:41] Otherwise, we load the item that we plan to dequeue from the internal data map. We then delete it from the internal map to conserve space. Next, we increment our last dequeued index for any future calls to dequeue and finally return this dequeued item.
[03:06] In short, the implementation is simply maintaining a map and tracking our queue and dequeue indexes within the enqueue and dequeue methods.
[03:16] The common additional requirement of adding a size function, which returns a number of elements in the queue, can easily be met by diff-ing the next enqueue index with the last dequeued index.