[Tutor] When am I ever going to use this?

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Wed Aug 2 05:19:37 CEST 2006

On Tue, 1 Aug 2006, Christopher Spears wrote:

> I've been working through a tutorial: 
> http://www.ibiblio.org/obp/thinkCSpy/index.htm. Lately, I have been 
> learning about abstract data types (linked lists, stacks, queues, trees, 
> etc.).  While I do enjoy the challenge of creating these objects, I am 
> not sure what they are used for.

Hi Chris,

Let say that we are trying to write a navigator program, one that helps 
plan road trips.  One portion of the input to this program would be a map 
of the roads.

For example:

     map = [('a', 'b'),
            ('a', 'c'),
            ('c', 'f'),
            ('b', 'd'),
            ('d', 'e'),
            ('d', 'f')]

might represent the following street map:

     a ------ b
     |        |
     |        |
     c        d ------ e
      \       |
       \      |
        ----- f

where 'a', 'b', 'c', 'd', 'e', and 'f' are points of interest.  (I'm 
oversimplifying, but I hope you don't mind!)

A simple question we might ask this system is: how far is it from point 
'a' to point 'f'?  We'd like to ask the system:

     distance('a', 'f', map)

and be able to get 2, since there's a hop from 'a' to 'c', and from 'c' to 

This problem is ripe to be attacked with an algorithm called 
"breadth-first search", and breadth-first search typically is implemented 
by keeping a queue of places.  We can talk about this in more detail if 
you'd like.


This is a long hand-wavy example for a short explanation: queues and and 
other data structures are "background" support tools: they themselves 
aren't so interesting, but they're the tools that a programmer often will 
reach for when working on non-string related problems.

If you remember Starcraft: there was a four-level queue of movement 
commands that you could set up by holding "shift" while navigating your 
forces.  You could also "queue" up production orders in factories.

Same data structure.  *grin*

Best of wishes!

More information about the Tutor mailing list