Working with Stacks and Queues

 
   

Ruby Way
By Hal Fulton
Slots : 1.0
Table of Contents
 


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.


   

 

 



The Ruby Way
The Ruby Way, Second Edition: Solutions and Techniques in Ruby Programming (2nd Edition)
ISBN: 0672328844
EAN: 2147483647
Year: 2000
Pages: 119
Authors: Hal Fulton

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net