{"action":"created","issue":{"url":"https://api.github.com/repos/facebook/immutable-js/issues/470","labels_url":"https://api.github.com/repos/facebook/immutable-js/issues/470/labels{/name}","comments_url":"https://api.github.com/repos/facebook/immutable-js/issues/470/comments","events_url":"https://api.github.com/repos/facebook/immutable-js/issues/470/events","html_url":"https://github.com/facebook/immutable-js/issues/470","id":74442292,"number":470,"title":"Create a First in First out datastrcutre","user":{"login":"ericwooley","id":1930227,"avatar_url":"https://avatars.githubusercontent.com/u/1930227?v=3","gravatar_id":"","url":"https://api.github.com/users/ericwooley","html_url":"https://github.com/ericwooley","followers_url":"https://api.github.com/users/ericwooley/followers","following_url":"https://api.github.com/users/ericwooley/following{/other_user}","gists_url":"https://api.github.com/users/ericwooley/gists{/gist_id}","starred_url":"https://api.github.com/users/ericwooley/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ericwooley/subscriptions","organizations_url":"https://api.github.com/users/ericwooley/orgs","repos_url":"https://api.github.com/users/ericwooley/repos","events_url":"https://api.github.com/users/ericwooley/events{/privacy}","received_events_url":"https://api.github.com/users/ericwooley/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-05-08T17:49:20Z","updated_at":"2015-05-08T19:11:51Z","closed_at":null,"body":"It would be nice to have a queue, or similar data structure the same functionality can be achieved with a list, but it would be nicer and probably more performant to have a true queue implementation."},"comment":{"url":"https://api.github.com/repos/facebook/immutable-js/issues/comments/100330989","html_url":"https://github.com/facebook/immutable-js/issues/470#issuecomment-100330989","issue_url":"https://api.github.com/repos/facebook/immutable-js/issues/470","id":100330989,"user":{"login":"leebyron","id":50130,"avatar_url":"https://avatars.githubusercontent.com/u/50130?v=3","gravatar_id":"","url":"https://api.github.com/users/leebyron","html_url":"https://github.com/leebyron","followers_url":"https://api.github.com/users/leebyron/followers","following_url":"https://api.github.com/users/leebyron/following{/other_user}","gists_url":"https://api.github.com/users/leebyron/gists{/gist_id}","starred_url":"https://api.github.com/users/leebyron/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/leebyron/subscriptions","organizations_url":"https://api.github.com/users/leebyron/orgs","repos_url":"https://api.github.com/users/leebyron/repos","events_url":"https://api.github.com/users/leebyron/events{/privacy}","received_events_url":"https://api.github.com/users/leebyron/received_events","type":"User","site_admin":false},"created_at":"2015-05-08T19:11:51Z","updated_at":"2015-05-08T19:11:51Z","body":"Yeah that seems fine. I usually encourage people to just use List directly and use the `shift` and `pop` methods as `enqueue` and `dequeue`.\r\n\r\nThe issue with a double-linked-list is that such a structure can't be make immutable. Imagine what \"enqueue\" would need to do - after creating the new node and pointing to the previous tail, the previous tail would need to be mutated to point to the new tail. Since the nodes are immutable, we would need to clone that node with the edit pointing to the new tail. Then the next node which was pointing to it also needs to be edited and you end up cloning the entire list on every operation, making `enqueue` and `dequeue` both O(N), a sad result.\r\n\r\nWhat that MSDN article describes is called a \"finger tree\" - which is very similar in structure to the \"bitmap vector trie\" that is used to implement List, but ensures access to the beginning and end is only one link away while access to the middle is log N links away - making `enqueue` and `dequeue` amortize to O(1) - pretty awesome. In practice, if your queues are smaller than say... 1000 items, a \"finger tree\" and a \"bitmap vector trie\" are going to have identical performance. But if your queues are in the 10000+ category and are highly volatile, then using such a structure could squeeze even more performance. That's why adding such a new structure isn't going to be high priority, but still very interesting."}}