Outline

• queue implementation: array queue
• data structure traversal
• double-ended queues
• queue application: simulation of an airline counter
• random numbers

queue implementation strategies

• similar to stack
• linked list implementation, or
• array implementation
• as for other collections, we don't need to know the type of the elements, only that they are objects, so a generic implementation is fine

array implementation of queues

• like stack: store all the elements in an array
• when inserting a new element (offer), just like stack, add the element at the end of the queue
• two choices when removing an new element from the front of the list (poll, remove):
  1. copy all subsequent elements down by one index, so the first element is still at the beginning of the array, or
  2. keep track of where the head of the queue is, with another index variable
• for example, removing the front element (a) from this queue:
• can be done by copying:
• or by keeping track of where the first element is:
• in-class exercise: what are the advantages and disadvantages of these two strategies?

in-place array implementation

• two integer variables, one the index of the head of the queue (front), the other the index of the tail of the queue (end)
• so valid elements are found from array[front] through array[end - 1]
• queue contents get ever higher in the array, while lower-numbered indices will no longer contain valid data
• eventually, even if the queue only has a few values, we run out of indices to put new data into
• solution: once we reach the end of the array, put the data beginning at index 0 again
• the modulo operation can be used to make this simple:

  index = (index + 1) % QUEUE_SIZE;
  

• for example, if queue size is 15 and index = 14,
  14 + 1 = 15,
  15 % 15 = 0
  so the new value of the index is 0
• the number of elements in the array is
  (end - front + QUEUE_SIZE) % QUEUE_SIZE,
  but it is easier to simply maintain a size field
• this is an example of adding elements 's' and 't' to a queue:

implementation of the method offer

• if there is room,
  • insert at end
  • increment end modulo MAX_SIZE
• offer calls the private method full to make sure room is available
  • if no room, simply returns false
  • implementation in textbook (p. 323) doubles the size of the array: what is the runtime of this method?

amortized runtime analysis

• so far, we have only considered worst-case runtime in our big-O analysis
• consider the offer method:
  • if there is room, it takes O(1) (constant time)
  • if more room is needed, it takes O(n) (linear time)
• how long does it take on average?
• assume we just doubled the size of the array, to size 2n
• so for the next n calls to offer, the calls will take constant time
• then, on the following calls to offer, it will take time n
• the total time for n calls is O(n)
• so the average time per calls must be O(1)
• this is known as the amortized runtime: sometimes the call is expensive, but this cost is amortized across a large (enough) number of inexpensive calls, so the average is low
• the hard part is guaranteeing that there will be all those inexpensive calls
• for example, assume that instead of doubling the array size, the array size increases by a constant, say 10 new elements
• then, O(n) time is spent for every 10 calls
• on average, the time is O(n/10), which is still O(n) or linear
• no constant is large enough to amortize the linear cost
• so the array size has to at least double to give O(1) amortized time

implementation of the method poll

• if there is at least one element,
  • element is taken from front
  • increment front modulo MAX_SIZE
• if there is no element, simply returns null
• peek is even simpler: no increment, no size change
• what is the runtime of this method?
• what is the runtime of the empty method?

linked list implementation of queues

• a queue can be implemented as either a singly-linked or doubly-linked list
• either way, the head of the list is usually the front of the queue, and the tail of the list is the back of the queue
• either way, we keep a head node (for removal) and a tail node (for insertion)
• there is a special case when the list is empty (method offer) or when removing the last element from the list (method poll)
• In-class exercise: write the code for either the offer or poll method (or if you have time, for both) for a queue implemented using a singly-linked list

data structure traversal

• in a linked list, each node has a link to at most one other node
• in a doubly-linked list, each node has a link to at most two other nodes
• there are more general data structures in which nodes can have links to multiple other nodes
• these data structures go by different names, including trees and graphs
• in some cases, we need to have a program start at one node and visit all the other nodes in the data structure: tree traversal or graph traversal
• in general, I can start from a given node and put all the nodes it is connected to into a queue
• then, I repeatedly remove one node from the queue, visit it, and put into the queue all the nodes it is connected to
• if I keep doing this, staying away from nodes that have already been visited, I will eventually visit all connected nodes
• this is called breadth-first traversal:
  • visually arranging the first node at the top
  • the nodes it is connected to right below it,
  • the nodes they are connected to right below them,
  • nodes are visited in left-to-right and top-to-bottom order

depth-first traversal

• for a traversal, I could push the nodes in a stack instead of a queue
• then, the node I will visit next is the node I put on the stack most recently
• that means visiting every node connected to the most recently visited node, before visiting any node that was pushed onto the stack earlier
• this is called depth-first traversal because the traversal tends to go top-to-bottom, then climb back up and explore the side branches

double-ended queues

• sometimes, it is useful to be able to add and remove elements at either end of a queue
• this double-ended queue, or deque (pronounced "D-Q"), can do everything either a stack or a queue can do
• implementation, using either arrays or linked lists, is similar to the implementation of either a stack or a queue

Simulation of an airline counter

• two queues: regular and frequent flyer passengers
• random arrivals: during each minute, one passenger arrives with a given probability, arrivalRate
• this is computed by testing

  if (Math.random < arrivalRate) { // passenger arrives
  

• one agent, requiring a time that is uniformly random between 0 and some defined maximum number of minutes
• every minute,
  1. check to see whether to add passengers to each queue
  2. check to see whether the agent is done taking care of the current passenger, and if so, select the next passenger if any
  3. update the time
• once a passenger is selected, that passenger's statistics (waiting time) must be updated
• selecting the next passenger can be done in different ways if there are passengers in both queues

Random numbers

• tossing a fair coin is truly random -- there is no way to predict what the next toss will give
• computers do not find it easy to toss coins
• instead, beginning with a specific number (the seed), they apply a complicated function to yield a new number
• this new number is a pseudo-random value: it is computed, and therefore not random, but there is no easy way to predict the new number from the old (without knowing the exact function), and so it looks like a sequence of random numbers
• the initial seed can be a fixed value (e.g. 1), to give a repeatable sequence of random numbers (good for debugging code)
• or, the initial seed can be selected almost at random, e.g. the time of day when the program is run, to give a different sequence each time
• Java's Math.random() returns a double with a value uniformly distributed between 0 and 1
• Java Random by default is initialized to the current day and time, but the programmer can explicitly specify the seed