May 25, 2017

Queues: Data Structures & Algorithms in JavaScript P.3

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:

An example using the Queue class::

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:

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: