QUEUE

https://cs.slides.com/colt_steele/queues

A FIFO data structure!

First In First Out

We’ve Seen this before

Queues exist everywhere! Think about the last time you waited in line..
How do we use them in programming?
- Background tasks
- Uploading resources
- Printing / Task processing

Enqueue

Adding to the beginning of the queue!

Remember, queues are a FIFO data structure

Enqueue pseudocode

This function accepts some value
Create a new node using that value passed to the function
If there are no nodes in the queue, set this node to be the first and last property of the queue
Otherwise, set the next property on the current last to be that node, and then set the last property of the queue to be that node
Increment the size of the queue by 1

Dequeue

Removing from the beginning of the Queue!

Remember, queues are a FIFO data structure

Dequeue psuedocode

If there is no first property, just return null
Store the first property in a variable
See if the first is the same as the last (check if there is only 1 node). If so, set the first and last to be null
If there is more than 1 node, set the first property to be the next property of first
Decrement the size by 1
Return the value of the node dequeued

Building a Queue With an Array

var queue = [];
queue.push("First")
queue.push("Second")
queue.push("Third")
queue.shift()
queue.shift()
queue.shift()

Of course, one thing that's not great when we do this is if we had 10,000 items in there, they each have an index and removing from the beginning means that every single item is re indexed. So adding to the end of the array doesn't require re indexing anything.

But removing from the beginning shifts everything over.

queue.unshift("First");
queue.unshift("Second")
queue.unshift("Third")
queue.pop()
queue.pop()
queue.pop()

However, in the second case, if we think about how it's working as we grow this to 10,000 items,

if we're adding to the beginning, every time we insert that means re indexing the entire queue, which

also is not good because that means shifting everything over giving a new index to if we have 10,000

items, that means reassigning every single item popping from the end works well.

So unlike when we talked about stacks, you could use push and pop to make a stack and you would never

need to re index the entire thing, the entire array.

Writing our own queue from scratch

Queue Class

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class Queue{
    constructor() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){
	    var newNode = new Node(val);
	    if(!this.first){
		    this.first = newNode;
		    this.last = newNode;
	    }else{
		    this.last.next = newNode;
		    this.last = newNode;
	    }
	    return ++this.size;
    }
    dequeue(){
	    if(!this.first) return null;
	    var temp = this.first;
	    if(this.first === this.last){
		    this.last = null;
	    }
		    this.first = temp.next;
		    this.size--;
		    return temp.val;
	    
    }
}

Big O of Queues

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)

Operation	Time Complexity	Space Complexity	Description
`enqueue()`	O(1)	O(1)	Add an element to the back of the queue
`dequeue()`	O(1)	O(1)	Remove the front element from the queue
`peek()` / `front()`	O(1)	O(1)	View the front element without removing it
`isEmpty()`	O(1)	O(1)	Check if the queue is empty
`size()`	O(1)	O(1)	Return the number of elements in the queue
`search()`	O(n)	O(1)	Search for an element in the queue (linear search)

RECAP

Queues are a FIFO data structure, all elements are first in first out.
Queues are useful for processing tasks and are foundational for more complex data structures
Insertion and Removal can be done in O(1)