Lecture Notes for SE 598, Data Structures and Algorithms

28 June 2000, Dequeue Algorithms

1. dequeue structure

   1. sequential - linear; value after another

   2. limited access - enter at the end, leave at the beginning

      1. values can enter and leave a dequeue at either end

   3. queues are order preserving; values leave in the same order they arrived

      1. first in, first out - fifo; strict queue order

      2. longest waiting next

2. dequeue algorithms

   1. breadth-first searches

      1. traversing a graph, visiting each node once

         1. start at city A and look the shortest way to get to city B

      2. at each node, how to rembmer the nodes to visit next

      3. use a queue to store the to-be-visited nodes

      4. the tranversal spreads out in rings around the initial node - breadth-first search

   2. buffering between independently executing components

      1. a produce makes things used by a consumer

         1. a web browser sending requests to a http server

      2. what happens when one side is faster than the other

      3. use a buffer to store the things made by the producer but not yet used by the consumer

      4. doesn't work on its own if the difference in speed is too great

      5. producers and consumers of similar speed, a queue capable of holding two things is enough

      6. most buffers are strictly bounded

   3. re-ordering queue components - priority queues

      1. some things are more important than others and should jump the queue

         1. background (or batch) processes vs. foreground (or interactive) processes

      2. how to re-order the queue so that the next most important, rather than the longest waiting, comes next

      3. this requires a speical data structure called the priority queue

This page last modified on 26 June 2000.