Queues
P.J. Drongowski
27 November 2004

Queue

  * Quite simply, it's a list that's open at both ends!
  * First in, first out (FIFO) access discipline
    - Contrast with stack which has last in, first out (LIFO) access
    - Variants allow other access disciplines like priority
  * Queues are important for resource management
    - Use of resources must be controlled/scheduled
    - A queue usually holds an object of a particular type (class)
  * Uses
    + Waiting line
    + Operating systems
      - Processes waiting to run on CPU
      - Disk operations awaiting service
      - Print queue to hold print jobs
    + Communications
      - Telephone calls awaiting circuits
      - Incoming and outgoing data packets
    + Simulation
      - Model real-world behavior (customer service, amusement park, ...)
      - Perform "what if" experiments

Queue operations

  * Create a new empty queue                Queue()
  * Destroy an existing queue               ~Queue()
  * Add an item to end of a queue           enqueue(PtrItem item)
  * Remove an item from front of queue      PtrItem dequeue()
  * Determine if a queue is empty           bool isEmpty()
  8 Return number of items in queue         int length()
  * Return front item without removal       PtrItem front()

Variations

  * Double-ended queue
    + Allow addition at either end (addFront, addEnd)
    + Allow removal at either end (removeFront, removeEnd)
  * Priority queue
    + Items are arranged in order according to priority
    + Two approaches
      - Maintain order explicitly at all times
      - Be lazy, don't maintain order at all times; Return minimum item
        (front) upon request

Pointer-based implementations and variations

  * Linear linked list
    + Pointer to front of list
    + Pointer to end of list
  * Circular linear linked list
    + Single pointer to end of list
    + last element in list points back to the front item
  * Doubly linked list
    + Each list item has two pointers
      - Pointer to previous item in list
      - Pointer to next item in list
    + Makes insertions and deletions easier, especially when inserting
      or deleting an item in the middle of a list
    + Often uses two special items
      - Header node: Points to front of list; previous pointer is NULL
      - Trailer node: Points to end of list; next pointer is NULL
    + All operations can be completed in O(1) time

Array-based implementation

  * Uses an array of a particular size (capacity)
  * An inefficient approach - O(n) time
    + Let the first element in the array be the first item in the queue
    + Keep the index of the last item in the queue
    + Shuffle items up when the first item is removed
    + The dequeue operation is O(n) due to the shuffle (where n is
      the number of items in the queue)
  * Circular array - an efficient approach - O(1) time
    + Maintain two indices
      - Front: Index of front item in queue
      - Back: Index of first available element in the array
    + A queue is empty when front == back == 0
    + Dequeue operation increments the front index
    + Enqueue operation increments the back index
    + Need to perform "wrap around" when either index exceeds the
      array bounds (use modulus operation)
    + How to handle a full array?
      - Do not allow more than N-1 items, where N is size of the array
      - Keep a count of the number of items in the queue
      
Input/output buffers

  * A common practical situation
  * Input or output proceeds at different rates
    + Disk input and output is much slower than CPU
    + Don't make program wait for disk I/O to complete
  * Buffers are used for "non-blocking" input/output
    + Let disk write data at its own speed without making program wait
    + Store data in a buffer
    + Write buffer to disk when a buffer is full
    + Use multiple buffers to hold data allowing several outstanding
      output operations
      - Typical approach for "block-oriented" devices like disk
      - Buffer chain is a queue of buffers
  * Simple keyboard interrupt processing
    + Incoming characters are stored in a circular (array) buffer
    + Buffer is managed by the operating system
    + Interrupt routine puts characters into the buffer
    + Application program removes characters from buffer via OS call
    + A buffer is effectively a queue implemented as a circular array
  * Practical issue
    + Rate balancing - maintain a continuous flow of data without waiting
      - How many buffers should be allocated?
      - How big should the buffers be?
    + Determine sizes experimentally -- code, run, observe, analyze
    + Determine sizes through simulation!