Queues: Data Structures & Algorithms in JavaScript P.3

• Data Structures: List ADT | Stacks | Queues | Linked Lists | Trees, Tries & Graphs | Heaps | Hash Tables
• Algorithms: Breadth-First Search | Depth-First Search | Binary Search | Merge Sort | Quick Sort
• Concepts: Memory (Stack vs. Heap) | Recursion | Big O Time & Space

3. Queues

• A queue is a list of elements where elements are inserted to the back of the list but removed from the front of the list.
• As such, a queue is referred to as a First-in, First-out (FIFO) data structure.
• It is efficient and fast because we can add or remove data at a constant time operation.
• The enqueue operation adds an element to the back of the queue, while dequeue removes an element from the front of a queue.
• The peek method returns the value of the element at the front of the queue without removing it as dequeue does.
• The isEmpty method checks to see if the queue is empty, while the dataStore is an array used to store data internally.
• Eg. usage of queue data structure: the Event-loop of a web browser.
• Here is an implementation of a Queue class:

https://gist.github.com/tamg/372ecf40e861d1dcc98047f541f13686

An example using the Queue class::

https://gist.github.com/tamg/6b2dc06d67321b1ba7d16f8e9bda02f5

Priority Queue:

• A priority queue is a queue where elements are removed from the queue based on a priority constraint instead of the default FIFO principle.
• For instance the Emergency Department at a hospital might implement a priority queue. The hospital would then tend to patients not only on a first come first served basis(fifo) but also by assigning patients a priority code based on the severity of their emergency.

Implementing a Queue using only a Stack

• More on Stacks
• A Stack is a Last in, First out data structure.
• Using two Stacks we can implement a Queue data structure.
• We push new elements on to a first stack. Then, to reverse the order of the stack we can pop all its elements out and push them to a second stack.
• Now that the order of the first stack is reversed inside the second stack, we can start poping from the second stack.
• This way First in inside the first stack becomes First Out from the second stack ( aka Queue!)

Here is an implementation of a Queue using two Stacks:

https://gist.github.com/tamg/71de04b59251640ecb1c5037aa4299f7

Implementing a Stack using only a Queue

• As stated before, a queue is a First in, First out data structure.
• Using two Queues we can implement a Stack. (More on Stacks)
• First we simply push new elements to the first queue.
• When we pop however, we enqueue a second queue with the all the elements of the first queue except for the last element.
• The remaining last element from the first queue is then returned as the poped element.
• We then reassign first queue to be equal to the second queue(now with out the poped element).
• This way First in (last remaining element in the first queue) becomes First Out ( aka a Stack!)

Here is an implementation of a Stack using two Queues:

https://gist.github.com/tamg/0f503e90e47d050d15dcdac7ed133e45