Last active
October 25, 2020 14:00
-
-
Save ivanzusko/aa3e78ed0bb2155d03eedf115311d19b to your computer and use it in GitHub Desktop.
Queue data structure
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* Queue */ | |
| /** | |
| * insertion - O(1) | |
| * removal - O(1) | |
| * searching - O(n) | |
| * access - O(n) | |
| */ | |
| function Queue() { | |
| let size = 0; | |
| let first = null; | |
| let last = null; | |
| const Node = function(element){ | |
| this.element = element; | |
| this.next = null; | |
| }; | |
| this.enqueue = function (element) { | |
| const node = new Node(element); | |
| if (first === null) { | |
| first = node; | |
| last = node; | |
| } else { | |
| last.next = node; | |
| last = node; | |
| } | |
| size++; | |
| return this; | |
| } | |
| this.dequeue = function () { | |
| if (first === null) { | |
| return undefined; | |
| } | |
| const currentNode = first; | |
| first = currentNode.next; | |
| size--; | |
| if (size === 0) { | |
| first = null; | |
| last = null; | |
| } | |
| return currentNode.element; | |
| } | |
| this.isEmpty = function () { | |
| return size === 0; | |
| }; | |
| this.toArray = function () { | |
| let array = []; | |
| let currentNode = first; | |
| while (currentNode !== null) { | |
| array.push(currentNode.element); | |
| currentNode = currentNode.next; | |
| } | |
| return array; | |
| } | |
| this.size = function (){ | |
| return size; | |
| }; | |
| this.first = function (){ | |
| return first.element; | |
| }; | |
| this.last = function () { | |
| return last.element; | |
| }; | |
| this.firstNode = function (){ | |
| return first; | |
| }; | |
| this.lastNode = function () { | |
| return last; | |
| }; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment