JS - Linear Data Structures 02

Linear Data Structures

Queues

A queue is a linear collection of nodes that exclusively
- adds (enqueues) nodes to the tail,
- removes (dequeues) nodes from the head of the queue
- peek (reveals) data from the “front” of the queue without removing it
FIFO: first-in-first-out
Bounded queues have a limited size.
Enqueueing onto a full queue causes a queue overflow
Dequeueing from an empty queue causes a queue underflow

Queues Implementation

Queues can be implemented using a linked list as the underlying data structure.
The front of the queue is equivalent to the head node of a linked list.
The back of the queue is equivalent to the tail node.

Queue

const LinkedList = require('./LinkedList');
 
class Queue {
  constructor() {
    this.queue = new LinkedList();
    this.size = 0;
  }
 
  enqueue(data) {
    this.queue.addToTail(data);
    this.size++;
    console.log(`Added ${data}! Queue size is now ${this.size}.`);
  }
 
  dequeue() {
    const data = this.queue.removeHead();
    this.size--;
    console.log(`Removed ${data} from queue! Queue size is now ${this.size}.`);
    return data;
  }
}
 
module.exports = Queue;
 
const restaurantOrder = new Queue();
restaurantOrder.enqueue('apple pie');
restaurantOrder.enqueue('roast chicken');
restaurantOrder.enqueue('quinoa salad');
console.log('\nFood preparing...\n');
restaurantOrder.dequeue();
restaurantOrder.dequeue();
restaurantOrder.dequeue();
console.log('All orders ready!');

Underflow & Overflow

Underflow occurs when we try to remove elements from an already empty queue.
Overflow occurs when we add an element to a queue that does not have room for a new node.
Creating bounded queues with a .maxSize property
prevents queue overflow and underflow by keeping track of the queue size

Add Underflow & Overflow

const LinkedList = require('./LinkedList');
 
class Queue {
  constructor(maxSize = Infinity) {
    this.queue = new LinkedList();
    this.maxSize = maxSize;
    this.size = 0;
  }
 
  isEmpty() {
    return this.size === 0;
  }
 
  hasRoom() {
    return this.size < this.maxSize;
  }
 
  enqueue(data) {
    if (this.hasRoom()) {
      this.queue.addToTail(data);
      this.size++;
      console.log(`Added ${data} to queue! Queue size is now ${this.size}.`);
    } else {
      throw new Error('Queue is full!');
    }
  }
 
  dequeue() {
    if (!this.isEmpty()) {
      const data = this.queue.removeHead();
      this.size--;
      console.log(
        `Removed ${data} from queue! Queue size is now ${this.size}.`
      );
      return data;
    } else {
      throw new Error(`Queue is empty!`);
    }
  }
}
 
module.exports = Queue;
 
const boundedQueue = new Queue(3);
boundedQueue.enqueue(1);
boundedQueue.enqueue(2);
boundedQueue.enqueue(3);
boundedQueue.dequeue();
boundedQueue.dequeue();
boundedQueue.dequeue();
boundedQueue.dequeue();

Stacks

Like a queue, a stack is a linear collection of nodes that adds (pushes) data to one end of the data structure.
However, unlike a queue, a stack removes data (pops) from the same end of the data structure.
First In, Last Out (FILO)

Keys = [{"id":'YKSGDDOT:NGC38','category':'investment'},{'id':'Juneli Rai','category':'pm'}]
Keys =[{"id":{"S":'YKSGDDOT:NGC38'}}]