Source code online books for professionals by professionals

BLaCK BOX: DeQUe
as mentioned briefly several times already, python lists make nice stacks (lifo queues) but poor (fifo) queues. 
appending to them takes constant time (at least when averaged over many such appends), but popping from  
(or inserting at) the front takes linear time. What we want for algorithms such as Bfs is a double-ended queue, 
or deque. such queues are often implemented as linked lists (where appending/prepending and popping at either 
end are constant-time operations), or so-called circular buffers—arrays where we keep track of the position of 
both the first element (the head) and the last element (the tail). if either the head or the tail moves beyond its end 
of the array, we just let it “flow around” to the other side, and we use the mod (
%
) operator to calculate the actual 
indices (hence the term circular). if we fill the array completely, we can just reallocate the contents to a bigger 
one, like with dynamic arrays (see the “Black Box” sidebar on 
list
 in Chapter 2).
luckily, python has a deque class in the 
collections
 module in the standard library. in addition to methods such 
as 
append
, 
extend
, and 
pop
, which are performed on the right side, it has left equivalents, called 
appendleft
, 
extendleft
, and 
popleft
. internally, the deque is implemented as a doubly linked list of blocks, each of which 
is an array of individual elements. although asymptotically equivalent to using a linked list of individual elements, 
this reduces overhead and makes it more efficient in practice. for example, the expression 
d[k]
 would require 
traversing the first 
k
 elements of the deque 
d
 if it were a plain list. if each block contains 
b
 elements, you would 
only have to traverse 
k//b
 blocks.
Strongly Connected Components
While traversal algorithms such as DFS, IDDFS, and BFS are useful in their own right, earlier I alluded to the role of 
traversal as an underlying structure in other algorithms. You’ll see this in many coming chapters, but I’ll end this one with 
a classical example—a rather knotty problem that can be solved elegantly with some understanding of basic traversal.
The problem is that of finding strongly connected components (SCCs), sometimes known simply as strong 
components. SCCs are a directed analog for connected components, which I showed you how to find at the beginning 
of this chapter. A connected component is a maximal subgraph where all nodes can reach each other if you ignore edge 
directions (or if the graph is undirected). To get strongly connected components, though, you need to follow the edge 
directions; so, SCCs are the maximal subgraphs where there is a directed path from any node to any other. Finding 
SCCs and similar structures is an important part of the data flow analysis in modern optimizing compilers, for example.
Consider the graph in Figure 
5-7
. It is quite similar to the one we started with (Figure 
5-1
); although there are 
some additional edges, the SCCs of this new graph consist of the same nodes as the connected components of the 
undirected original. As you can see, inside the (highlighted) strong components, any node can reach any other, but 
this property breaks down if you try to add other nodes to any of them.
a
b
c
d
e
f
g
h
i
A
B
C