- Working with Arrays
- Working with Hashes
- Working with Stacks and Queues
- Working with Trees
- Working with Graphs
- Summary
This chapter is from the book
This chapter is from the book
This chapter is from the book
Working with Stacks and Queues
Stacks and queues are the first entities we have discussed that are not strictly built in to Ruby. By this we mean that Ruby does not have Stack and Queue classes as it has Array and Hash classes.
And yet, in a way, they are built in to Ruby after all. In fact, the Array class implements all the functionality we need to treat an array as a stack or a queue. You'll see this in detail shortly.
A stack is a last-in first-out (LIFO) data structure. The traditional everyday example is a stack of cafeteria trays on its spring-loaded platform; trays are added at the top and also taken away from the top.
There is a limited set of operations that can be performed on a stack. These include push and pop (to add and remove items) at the very least; usually there is a way to test for an empty stack, and there may be a way to examine the top element without removing it. A stack implementation never provides a way to examine an item in the middle of the stack.
You might ask how an array can implement a stack given that array elements may be accessed randomly and stack elements may not. The answer is simple: A stack sits at a higher level of abstraction than an array; it is a stack only so long as you treat it as one. The moment you access an element illegally, it ceases to be a stack.
Of course, you can easily define a Stack class so that elements can only be accessed legally. We will show how this is done.
It is worth noting that many algorithms that use a stack also have elegant recursive solutions. The reason for this becomes clear with a moment's reflection. Function or method calls result in data being pushed onto the system stack, and this data is popped upon return. Therefore, a recursive algorithm simply trades an explicit user-defined stack for the implicit system-level stack. Which is better? That depends on how you value readability, efficiency, and other considerations.
A queue is a first-in first-out (FIFO) data structure. It is analogous to a group of people standing in line at, for example, a movie theater. Newcomers go to the end of the line, whereas those who have waited longest are the next served. In most areas of programming, these are probably used less often than stacks.
Queues are useful in more real-time environments where entities are processed as they are presented to the system. They are useful in producer/consumer situations (especially where threads or multitasking is involved). A printer queue is a good example; print jobs are added to one end of the queue, and they "stand in line" until they are removed at the other end.
The two basic queue operations are usually called enqueue and dequeue in the literature. The corresponding instance methods in the Array class are called shift and unshift, respectively.
Note that unshift could serve as a companion for shift in implementing a stack, not a queue, because unshift adds to the same end from which shift removes. There are various combinations of these methods that could implement stacks and queues, but we will not concern ourselves with all the variations.
That ends our introductory discussion of stacks and queues. Now let's look at some examples.
Implementing a Stricter Stack
We promised earlier to show how a stack could be made "idiot-proof" against illegal access. We may as well do that now (see Listing 3.10). We present here a simple class that has an internal array and manages access to that array. (There are other ways of doing this—by delegating, for example—but what we show here is simple and works fine.)
Listing 3.10 Stack
class Stack
def initialize
@store = []
end
def push(x)
@store.push x
end
def pop
@store.pop
end
def peek
@store.last
end
def empty?
@store.empty?
end
end
We have added one more operation that is not defined for arrays; peek will simply examine the top of the stack and return a result without disturbing the stack.
Some of the rest of our examples will assume this class definition.
Converting Infix to Postfix
In writing algebraic expressions, we commonly use infix notation, with the operator in between the operands. Often it is more convenient to store an expression in postfix form, a parenthesis-free form in which the operator follows both the operands. (This is sometimes called Reverse Polish Notation.)
In Listing 3.11, we present a simple routine for converting infix to postfix notation using a stack. We make the simplifying assumptions that all operands are lowercase letters and the only operators are *, /, +, and -.
Listing 3.11 Infix to Postfix
# Define level of precedence
def level(opr)
case opr
when "*", "/"
2
when "+", "-"
1
when "("
0
end
end
# "Main"
infix = "(a+b)*(c-d)/(e-(f-g))"
postfix = ""
stack = Stack.new
infix.each_byte do |sym|
sym = "" << sym # Convert to string
case sym
when "("
stack.push sym
when /[a-z]/
postfix += sym
when "*", "/", "+", "-"
finished = false
until finished or stack.empty?
if level(sym) > level(stack.peek)
finished = true
else
postfix += stack.pop
end
end
stack.push sym
when ")"
while stack.peek != "("
postfix += stack.pop
end
stack.pop # Get rid of paren on stack
end
end
while !stack.empty?
postfix += stack.pop
end
puts postfix # Prints "ab+cd-*efg--/"
Detecting Unbalanced Punctuation in Expressions
Because of the nature of grouped expressions, such as parentheses and brackets, their validity can be checked using a stack (see Listing 3.12). For every level of nesting in the expression, the stack will grow one level higher; when we find closing symbols, we can pop the corresponding symbol off the stack. If the symbol does not correspond as expected, or if there are symbols left on the stack at the end, we know the expression is not well formed.
Listing 3.12 Detecting Unbalanced Punctuation
def paren_match str
stack = Stack.new
lsym = "{[(<"
rsym = "}])>"
str.each_byte do |byte|
sym = byte.chr
if lsym.include? sym
stack.push(sym)
elsif rsym.include? sym
top = stack.peek
if lsym.index(top) != rsym.index(sym)
return false
else
stack.pop
end
# Ignore non-grouped characters...
end
end
# Ensure stack is empty...
return stack.empty?
end
str1 = "Hello (yes, [um] you) there!"
str2 = "(((a+b))*((c-d)-(e*f))"
str3 = "[[(a-(b-c))], [[x,y]]]"
paren_match str1 # true
paren_match str2 # false
paren_match str3 # true
Detecting Unbalanced Tags in HTML and XML
The example shown in Listing 3.13 is essentially the same as Listing 3.12. We include it only to give a hint that this task is possible (that is, that a stack is useful for validating HTML and XML).
In the old days, a string was considered, at best, a special case of an array. Your opinion may vary depending on your language background. In Ruby, strings are not arrays; however, it is a tribute to the orthogonality of the language when we see how similar these two examples turned out. This is because, after all, there is a certain isomorphism between strings and arrays. They are both ordered sequences of elements, where in the case of a string, the element is a character.
Because we are talking about stacks and not HTML/XML, we have made a huge truckload of simplifying assumptions here. (If you're interested in real-life HTML and XML examples, refer to later chapters.) First of all, we assume that the text has already been parsed and stuck into an array. Second, we only care about a limited subset of the many tags possible. Third, we ignore the possibility of attributes and values associated with the tags.
In short, this is not a real-life example at all; however, like the previous example, it shows the underlying principle.
Listing 3.13 Detecting Unbalanced Tags
def balanced_tags list
stack = Stack.new
opening = %w[ <html> <body> <b> <i> <u> <sub> <sup> ]
closing = %w[ </html> </body> </b> </i> </u> </sub> </sup> ]
list.each do |word|
if opening.include? word
stack.push(word)
elsif closing.include? word
top = stack.peek
if closing.index(top) != opening.index(word)
return false
else
stack.pop
end
# Ignore other words
end
end
# Ensure stack is empty...
return stack.empty?
end
text1 = %w[ <html> <body> This is <b> only </b>
a test. </body> </html> ]
text2 = %w[ <html> <body> Don't take it <i> too </i>
seriously... </html> ]
balanced_tags(text1) # true
balanced_tags(text2) # false
Understanding Stacks and Recursion
As an example of the isomorphism between stack-oriented algorithms and recursive algorithms, we will take a look at the classic "Tower of Hanoi" problem.
According to legend, there is a Buddhist temple somewhere in the Far East, where monks have the sole task of moving disks from one pole to another while obeying certain rules about the moves they can make. There were originally 64 disks on the first pole; when they finish the task, the world will come to an end.
As an aside, we like to dispel myths when we can. It seems that in reality, this puzzle originated with the French mathematician Edouard Lucas in 1883 and has no actual basis in eastern culture. What's more, Lucas himself named the puzzle the "Tower of Hanoi" (in the singular).
So if you were worried about the world ending, don't worry on that account. Anyway, 64 disks would take 264-1 moves. A few minutes with a calculator will reveal that those monks would be busy for millions of years.
But on to the rules of the game. (We'll explain this even though every first-year computer science student in the world has already seen the puzzle.) We have a pole with a certain number of varying-sized disks stacked on it; call this the source pole. We want to move all these disks to the destination pole, using a third pole (called the auxiliary pole) as an intermediate resting place. The catch is that you can only move one disk at a time, and you cannot ever place a larger disk onto a smaller one.
The following example uses a stack to solve the problem. We use only three disks here because 64 would occupy a computer for centuries:
def towers2(list)
while !list.empty?
n, src, dst, aux = list.pop
if n == 1
puts "Move disk from #{src} to #{dst}"
else
list.push [n-1, aux, dst, src]
list.push [1, src, dst, aux]
list.push [n-1, src, aux, dst]
end
end
end
list = []
list.push([3, "a", "c", "b"])
towers2(list)
Here's the output that's produced:
Move disk from a to c Move disk from a to b Move disk from c to b Move disk from a to c Move disk from b to a Move disk from b to c Move disk from a to c
Of course, the classic solution to this problem is recursive. As we already pointed out, the close relationship between the two algorithms is no surprise because recursion implies the use of an invisible system-level stack. Here's an example:
def towers(n, src, dst, aux)
if n==1
puts "Move disk from #{src} to #{dst}"
else
towers(n-1, src, aux, dst)
towers(1, src, dst, aux)
towers(n-1, aux, dst, src)
end
end
towers(3, "a", "c", "b")
The output produced here is the same. And it may interest you to know that we tried commenting out the output statements and comparing the runtimes of these two methods. Don't tell anyone, but the recursive version is twice as fast.
Implementing a Stricter Queue
We define a queue here in much the same way we defined a stack earlier. If you want to protect yourself from accessing such a data structure in an illegal way, we recommend this practice (see Listing 3.14).
Listing 3.14 A Stricter Queue
class Queue
def initialize
@store = []
end
def enqueue(x)
@store << x
end
def dequeue
@store.shift
end
def peek
@store.first
end
def length
@store.length
end
def empty?
@store.empty?
end
end
We should mention that there is a Queue class in the thread library that works very well in threaded code.
A Token Queue Example: Traffic Light Simulation
We offer here a fairly contrived example of using a queue. This code will simulate the arrival of cars at a traffic light and store the arrival times in four queues. At the end, it prints some (presumably meaningful) statistics about the queue lengths and wait times.
A number of simplifying assumptions have been made. Time is granularized at the level of one second. There are no threads involved; all car movements are serialized in a reasonable way. Cars turn neither left nor right, they never go through a yellow or red light, and so on. The code is shown in Listing 3.15.
Listing 3.15 Traffic Light Simulation with a Queue
#
# Program: Traffic light simulation
# (Queue example)
#
# The traffic light has this behavior:
# Green north/south for 40 seconds
# Pause 2 seconds
# Green east/west for 45 seconds
# Pause 2 seconds
# Repeat
#
# The traffic behaves this way:
# A northbound car arrives at the traffic light
# every 3 seconds;
# Southbound, every 5 seconds;
# Eastbound, every 4 seconds;
# Westbound, every 6 seconds.
# All times are approximate (random).
# Assume no cars turn at the light.
#
# Cars pass through the light at a rate of
# one per second.
#
# Let's run for 8900 seconds (100 full cycles or
# more than two hours) and answer these questions:
# How long on the average is each line of cars
# when the light turns green? What is the average
# wait time in seconds? What is the longest wait
# time?
#
# Direction constants
NORTH, SOUTH, EAST, WEST = 0, 1, 2, 3
dirs = %w[North South East West]
# Probabilities for car arriving
# from each direction:
p = Array.new(4)
p[NORTH] = 1.0/3.0
p[SOUTH] = 1.0/5.0
p[EAST] = 1.0/4.0
p[WEST] = 1.0/6.0
# Queues:
waiting = Array.new(4)
waiting[NORTH] = Queue.new
waiting[SOUTH] = Queue.new
waiting[EAST] = Queue.new
waiting[WEST] = Queue.new
lengths = [0, 0, 0, 0] # How long is queue
# when light turns green?
greens = [0, 0, 0, 0] # How many times did
# light turn green?
times = [0, 0, 0, 0] # How long did cars wait?
ncars = [0, 0, 0, 0] # Count cars through light.
maxtime = [0, 0, 0, 0] # Max wait time?
# Looping...
time=0
while time < 8900
change = true # Light changed
for time in time..time+40 # North/south green
# Enqueue all arrivals
for dir in NORTH..WEST
waiting[dir].enqueue(time) if rand < p[dir]
end
# Record queue lengths, counts
if change
for dir in NORTH..SOUTH
lengths[dir] += waiting[dir].length
greens[dir] += 1
end
change = false
end
# N/S can leave, one per second...
for dir in NORTH..SOUTH
if !waiting[dir].empty?
car = waiting[dir].dequeue
wait = time - car
ncars[dir] += 1
times[dir] += wait
maxtime[dir] = [maxtime[dir],wait].max
end
end
end
for time in time..time+2 # Yellow/red
# Nothing happens...
end
change = true # Light changed
for time in time..time+45 # East/west green
# Enqueue all arrivals
for dir in NORTH..WEST
waiting[dir].enqueue(time) if rand < p[dir]
end
# Record queue lengths, counts
if change
for dir in EAST..WEST
lengths[dir] += waiting[dir].length
greens[dir] += 1
end
change = false
end
# N/S can leave, one per second...
for dir in EAST..WEST
if !waiting[dir].empty?
car = waiting[dir].dequeue
wait = time - car
ncars[dir] += 1
times[dir] += wait
maxtime[dir] = [maxtime[dir],wait].max
end
end
end
for time in time..time+2 # Yellow/red
# Nothing happens...
end
end
# Display results...
puts "Average queue lengths:"
for dir in NORTH..WEST
printf " %-5s %6.1f\n", dirs[dir],
lengths[dir]/greens[dir].to_f
end
puts "Max wait times:"
for dir in NORTH..WEST
printf " %-5s %4d\n", dirs[dir],
maxtime[dir]
end
puts "Average wait times:"
for dir in NORTH..WEST
printf " %-5s %6.1f\n", dirs[dir],
times[dir]/ncars[dir].to_f
end
Here is the output this example produces (which will vary because of the use of the pseudorandom number generator rand):
Average queue lengths: North 15.6 South 9.5 East 10.8 West 7.3 Max wait times: North 51 South 47 East 42 West 42 Average wait times: North 19.5 South 16.2 East 13.7 West 12.9
You may at once see a dozen ways in which this program could be improved. However, it serves its purpose, which is to illustrate a simple queue.