Queuing structures for graph traversals
Reading time20 minIn brief
Article summary
In this article, you will learn how about some common queuing structures, and how they can be used to shape the behavior of a traversal algorithm. You will learn about LIFO (Last-In First-Out) and FIFO (First-In First-Out), which respectively define a DFS and a BFS.
Main takeaways
-
Queuing structures are data structures in which data enters/exits in a specific order.
-
Some common structures are stacks and queues.
-
They can be used to shape the behavior of a traversal.
-
DFS and BFS can be seen as a unique algorithm, parametrized with either a stack or a queue.
-
Such data structures find applications in numerous situations in computer science.
Article contents
1 — Video
Please check the video below. You can also read the transcripts if you prefer.
There are some “codes” that appear in this video. Please keep in mind that these “codes” are what we call pseudo-codes, i.e., they are not written in a real programming language. Their purpose is just to describe the algorithms, not to be interpretable per se. You will thus need a bit of work to make them fully-functional Python codes if you wish to.
To go further
The content of this section is optional. It contains additional material for you to consolidate your understanding of the current topic.
2 — FIFOs and LIFOs in computer science
To appreciate the importance of these two data structures in computer science, we present two examples of real life situations in which they are used.
2.1 — FIFOs in communication systems
For two people to communicate, they must send messages to each other. And, for two people to understand each other, they must send messages to each other in a logical order. You will find it easier to understand the sentence “A computer lets you make more mistakes faster than any other invention with the possible exceptions of handguns and Tequila” than “Make and tequila you than a faster the possible any exceptions handguns of invention computer lets more with other mistakes”.
For machines, it’s the same: order is important, and must be taken into account. Some communication models (others are much more complex) use queues for this purpose. Imagine a model in which we have a computer $A$ that writes words in a queue, and a computer $B$ that reads them. If computer $A$ sends the words in order, then $B$ will read them in the same order (because the first element inserted in a queue is also the first to leave it), and communication will be possible.
You may be wondering why go through a FIFO and not send the information directly? The advantage is that computers $A$ and $B$ do not necessarily go at the same speed (quality of the processor, network card…). Thus, if computer $A$ sends messages to computer $B$ very quickly (directly), the latter will miss some of them. Going through a queue allows you to store messages, in order, to avoid these synchronization problems.
2.2 — LIFOs in programming languages
When an operating system runs a program, it allocates some memory to it so that it can do its calculations correctly. This memory is generally divided into two areas: the heap that stores data, and the stack that allows (among other things) to call functions in programs.
In most programming languages, when a function f(a, b)
is called at a code location, the following (simplified) sequence occurs:
- The return address is pushed on the stack.
This will allow coming back right after
f
is called once its execution ends. - Argument
a
is pushed on the stack. - Argument
b
is pushed on the stack. - The processor is told to process the code of
f
. - We pop an element from the stack to get
b
. - We pop an element from the stack to get
a
. - The code of
f
is executed. - Once
f
is over, we pop an element from the stack to get the return address and go back to whenf
was called. - The processor is told to jump to that address.
But why use a stack instead of variables to pass this information?
Well, the processor doesn’t know the details of f
!
It is possible that f
uses another function g
for example.
If variables were used, the return address of f
would be overwritten by the return address of g
, and when g
was finished, we could never return to the time of the call of f
.
How about a FIFO then?
Here again, the problem occurs if f
calls a function g
.
As the return address of f
is put before that of g
in the queue, when it is necessary to return from the call to g
, the processor will get instead the return address of f
(the oldest in the queue)!
We will therefore never execute the code of f
located after the g
call.
To go beyond
The content of this section is very optional. We suggest you directions to explore if you wish to go deeper in the current topic.
- Queuing theory.
Gives more results on queues (expected time before being popped, etc.) and has many applications.