[stacks & queues] queues

Queues

• just for adding a removing (just like stack)
• FIFO(First In First Out) data structure
• eg. game waiting list, uploading - download background task on your computer, printer

Array implementation : it is not ideal! performance wise, class is better

• push - 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.
  • It just means indexing the new item at the very end.
  • But removing from the beginning shifts everything over.
    
    
• unshift - 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.

Linked list - queue class

• Add to the end to the tail(enqueue), and remove from the head(dequeue)

Enqueue

• function accepts a value we've done that create a new node using the value passed in.
• And then if there are no nodes in the queue
• set this node to be the first and last property.
• Otherwise, set the next property on the current last to be the new node, and then move the last pointer to be that new node at the end.
•  increment the size of the Q by one and return that

Dequeue

• So Q looks like this we define the function takes no arguments.  If there is no first property, just return null store the first property in a variable.
• This is identical to what we did in the stack section 'pop'.

Big 0

• insertion- O(1)
• removal- O(1)
• searching- O(N)
• access - O(N)