Lecture Notes for SE 598, Data Structures and Algorithms

28 June 2000, Dequeue Applications

1. simulations

   1. an entity obtains some service from a station

   2. a station can service only one entity at a time, others must wait in a queue

   3. a system is an interconnection (a graph) of queues and stations

   4. statistical properties determine how often an entity arrives at a station for service, and how long it takes to service an entity

   5. the objective is to find overall properties of the system - how many entities services per unit time, the longest wait for service, and so on

   6. closed form equations for even simple systems are usually impossible, so we simulate with programs

2. packet routers

   1. a router has connections to two or more networks

   2. an packet enters a(n internal) router and is sent out via another network

   3. only one packet can exit a network at a time; extra packets must wait in a queue

   4. routers usually have several queues, and queues are bounded

   5. queue management is an important aspect of router design

3. radix sorting - punch card sorting

   1. sort a list of numbers - zip codes, for example.

   2. set up a vector of ten queues, initially empty

   3. let the rightmost digit in a number (the ones digit) be the first digit, other digits are numbered increasing by one to the left

   4. numbers with fewer digits than others are padded to the left with zeros; assume all numbers have n digits.

   5. sort as follows:

      1. if the first digit of number i is d, put i in queue d; repeat for all numbers

      2. empty each queue 0 through 9 in order into a new queue

      3. repeat with the second digit

      4. repeat for all digits

This page last modified on 27 June 2000.