| 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 thisby delegating, for examplebut 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. | 
