Queue

Think of it like a queue (line) for a restaurant. First person in line will get their order first, last person in line will get their order last.

Specification

Implementation

General Implementation with a Linked List

See Linked List.

• init:
  • Initialize a first and last node as nullptr
• enter:
  1. Create a new node and set its value
  2. If isEmpty, set the first and last pointer to this node, else set the next field of the last node to the current node, and set the last pointer to the new node
• isEmpty:
  • Check if first node is nullptr
• leave:
  1. Store the address of the first node
  2. Set the first node the next node
  3. If the next node is null, set the last pointer to null as well
  4. Delete the stored address of the first node in (1)
• first
  • Return the first node
• nuke
  • Nuke the linked list by deleting each node one by one (could be done by calling leave over and over again)

Runtimes (see Big O):

• init:
• enter:
• isEmpty:
• leave:
• first:
• nuke:

General Implementation with a Dynamic Array

See Computer Science/Programming/Arrays

Implementing queue with a dynamic array will either result in huge space complexity or bad runtime complexity due to elements shifting. This implementation will sacrifice space complexity, by using a "first" index that just increments along the array.

• init:
  • Initialize the array
• enter:
  • Push to the back of the array
• isEmpty:
  • Check if the length of the array is equal to firstIndex
• leave:
  • Increment firstIndex by 1
• first
  • Return firstIndex element of the array
• nuke
  • Delete each element of the array if necessary, delete the array if necessary

Runtimes:

• init:
• enter: (amortized)
• isEmpty:
• leave:
• first:
• nuke: