Being an object-oriented language, data-structures aren't an uncommon occurrence in the world of Javascript. All data-structures have fun little quirks that differentiate them, and in queues, one of their quirks is their structure. This is often referred to as FIFO (First In, First Out). This simply means that objects removed from the queue, will be removed on a first-come, first-serve basis. Kind of like waiting at the DMV, or a drive-thru.
Functionality and Structure
So, how does this work? Easy. Think of an array, but this array only has two main methods:
- Enqueue
- Dequeue
We can compare Enqueue to the Array.push method, which adds an item to the end of an array.
We can compare Dequeue to the Array.shift method, which removes the first element of an array.
There's one more important feature that's also similar to the Array.length method. Queues will also have a size property, which just maintains how many elements are contained within it.
Implementation
As you can see, implementation of a Queue can be pretty easy by using an array, but a another way is using a Linked List. Linked Lists point to the next object in the list, which is really all you need. In the same manner, both Queues and Linked Lists will have a head and a tail.
Here is my most recent implementation:
In this code snippet, I created a a class called Queue. In the constructor function, the queue is given a size to keep track of how many items are being added, and the index is keeping track of the items place in the 'queue'. The queue in this implementation, is being stored in an object with key/value pairs. Here, we have count keeping track of the key that is to be dequeued next, so we are making sure that the first item in that object is the one to be removed. Size is also decremented to reflect an accurate amount of items within the queue.
In your first look over the code, the counter variable may be seemingly confusing. However, keep in mind that in this implementation, I am using an object, which I am then deleting properties from by using the delete keyword. After the deletion, I'm incrementing count to keep track of which item is essentially at the start of the Queue. In this example, I've kept the time complexity at a constant by only deleting a single item each time dequeue is called, and just keeping track of the items in queue with a counter instead of rearranging the entire object, which would then, at the minimum, make the time complexity of this implementation linear.
Something I haven't mentioned in this example is the "index" of the queue, which I am only incrementing when items are Enqueued. The reason why this is being incremented, is because of similar reasons before, to keep the time complexity constant. The index is giving each value their new key, which is their position in the queue. Without the index, the counter being incremented on the dequeue method wouldn't work properly, and vice versa.
Conclusion
All in all, Queues are a simple data structure. They are mostly used for things like some kind of help request ticket system, or even just waiting for food at any fast food chain. Things are added and removed from the queue of orders being placed often. So, the next time you're waiting in line for your french fries, hopefully this post comes to mind.
Top comments (0)