In this week's post I'll be going over queues. Similar to stacks, which we discussed last week, queues are a linear data structure, meaning the data elements are arranged sequentially. However, queues operate on the first in first out principle, or FIFO.
The term queue originates from the British term for a waiting line. Queues require two main methods, enqueue and dequeue. Enqueue adds an element to the end of the queue. And dequeue removes and element from from the beginning of the queue. In Javascript this can easily be done by representing the queue as an array. We can then use the push method to add the the end of the queue, and shift to remove from the beginning of the queue.
Next, I'd like to do a little callback to my post on linked lists and look at how we can implement a queue using a linked list.
Instead of having basic elements like our first example this queue will have nodes. These nodes will contain the data we want, as well as a pointer to the next node in the queue.
To implement the queue would first need some constructors. One for our nodes and another for our queue.
Next, we will need to implement our enqueue function. The concept is still the same, but we need to tweak it to conform to the linked list structure. We'll begin by creating a node using the data we need. Then we make our node the head if there is no current head, otherwise we'll add a pointer to the node at the end of our queue, then add our new node to the end of the queue.
For our dequeue method, we save the data we want from the first node in our queue, our head, then we replace that head with the next node in the queue.
As always you can check out the code from this post at my Github.
Top comments (0)