I’m learning about data structures and algorithms in JavaScript. I’m using various online resources and going to be sharing my notes as a series of blog posts. The topics are below:
- 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