Queues & Priority Queues – Beau teaches JavaScript



Queues are a first-in first-out data structure. Also learn about priority queues.

🔗 Code: http://codepen.io/beaucarnes/pen/QpaQRG?editors=0012
🔗 More info: https://www.safaribooksonline.com/library/view/learning-javascript-data/9781783554874/ch04.html

Beau Carnes on Twitter: https://twitter.com/carnesbeau

⭐JavaScript Playlists⭐
▶Data Structures and Algorithms: https://www.youtube.com/playlist?list=PLWKjhJtqVAbkso-IbgiiP48n-O-JQA9PJ
▶JavaScript Basics: https://www.youtube.com/playlist?list=PLWKjhJtqVAbk2qRZtWSzCIN38JC_NdhW5
▶Design Patterns: https://www.youtube.com/playlist?list=PLWKjhJtqVAbnZtkAI3BqcYxKnfWn_C704
▶ES6: https://www.youtube.com/playlist?list=PLWKjhJtqVAbljtmmeS0c-CEl2LdE-eR_F
▶Clean Code: https://www.youtube.com/playlist?list=PLWKjhJtqVAbkK24EaPurzMq0-kw5U9pJh


We’re busy people who learn to code, then practice by building projects for nonprofits. Learn Full-stack JavaScript, build a portfolio, and get great references with our open source community.

Join our community at https://freecodecamp.com
Read great tech articles at https://medium.freecodecamp.com

source

This Post Has 17 Comments

  1. DuoDecillion

    Isn't the splice inside the for loop of the enqueue function to make it O(n^2)?. And I think you could make the dequeue function O(1), if you use pop() instead of shift which is O(n), just changing the condition on the enqueue function to be element[1] > collection[i][1] etc.

  2. Oplaflafla

    thx, very useful to know how to implement priority queues in js

  3. Always remember to repent of your sins (sin is transgression of YAHUAH The Father In Heaven’s LAW: Genesis, Exodus, Leviticus, Numbers, & Deuteronomy) And Have Belief On Yahusha The Messiah. HE Died and Rose three days later so that you can be forgiven of your sins!

    HE Loves you! Come to HIM🙂🙂🙂🙂🙂🙂

  4. Mohaiminul Hasan

    Thanks. This helped me with my pathfinding visualizer. But during enqueue I compared current priority > iterated priority. I guess it has something to do with min-heap / max-heap. Once I made that change pathfinding was faster than DFS in my grid.

  5. Naman Gupta

    Shift method works like a charm for removing first element from the array.

  6. Fadi

    For the enqueue method, instead of using a for loop and writing all that code, you can push the element into the collection array and then sort it in ascending order:

    this.enqueue = function(element) {

    this.collection.push(element);

    this.collection.sort((a, b) => a[1] – b[1]);

    }

  7. Shayn Hacker

    How do I dynamically assign priority to data being sent into the array/collection array instead of it being hard-coded like how you have it in the video?

  8. israel meza

    if you remove form the beginning of an array the complexity is O(n) if you remove from a linked list it is O(1). Does this mean that for coding interviews I have to implement my own linked list queue?

  9. Charlie Kim

    for this.enqueue function isn't line 41: if(this.isEmpty()) a bit redundant since we would just be doing the same thing in line 52? If collection is empty, then var added will remain false since the If-statement in the for-loop would never evaluate to true and therefore the element would be pushed onto collections.

    Are we just checking for the empty array right away so in the case where the array is empty we could just stop the function early? Does this help performance or something?

  10. Tushar Chhibber

    Anyone please correct me if I am wrong, when we are running a loop to check for priorities… lets say this is the sample collections [ ['a', 4], ['b', 3], ['c', 2]] and I want to add ['d', 1]. If we run look from i = 0 to collection.length with if condition of element[1] < collection[i][1], we will end up with [ ['d', 1], ['a', 4], ['b', 3], ['c', 2]], but if we run with if condition of element[1] > collection[i][1], we will get [ ['a', 4], ['b', 3], ['c', 2], ['d', 1] ] ….

  11. Jason Jay Nulla

    In the priority queue, why not use index as the priority? Then each index has a collection and just check if it's empty or not instead of looping through all the elements?

  12. I didn't get collection.splice(i, 0, element) in PriorityQueue.enqueue('cedar', 2)
    Is not element[0] and not just element, because enqueue have 2 parameters in an array?
    EDIT: I got it, bc he's adding the priority too…
    Nice implementation

  13. Bijay Timilsina

    The simple code along with the soft voice makes it so easy and quick to understand these things. Just a tip: You can put the collection with array of items on a side window or as comments beside the line of code that you are currently explaining so it's easy to see the code along with collection ( eg. the part where you do colletion[ i ] [1]). Not a big thing, but human brain's algorithm is bit slow in searching memory queues (pun intended), especially for beginners. Thank you Beau, you are AWESOME and please keep sharing. Have a nice day 🙂

  14. Jay P

    The enqueue function here is linear. If you use a heap as the storage, you will have logarithmic enqueue/dequeue functions. Using a heap, you can still maintain FIFO within a given priority level by performing a secondary comparison to an "epoch" or "addedAt" parameter.

Leave a Reply