Section 9.3. Working with Trees

9.2. Working with Stacks and Queues

Stacks and queues are the first entities we have discussed that are not strictly built into Ruby. By this we mean that Ruby does not have Stack and Queue classes as it does Array and Hash classes (except for the Queue class in tHRead.rb, which we'll mention later).

And yet, in a way, they are built into Ruby after all. In fact, the Array class implements all the functionality we need to treat an array as a stack or a queue. We'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.

A limited set of operations 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 since 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 these data are popped upon return. Thus 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, while those who have waited the longest are the next served. In most areas of programming, queues 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 are 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 unpush and shift, 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. Various combinations of these methods 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.

9.2.1. 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. Here is 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.)

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 simply examines the top of the stack and returns a result without disturbing the stack.

Some of the rest of our examples assume this class definition.

9.2.2. 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. 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.

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 = "(((a+b))*((c-d)-(e*f))" str2 = "[[(a-(b-c))], [[x,y]]]" paren_match str1          # false paren_match str2          # true

The nested nature of this problem makes it natural for a stack-oriented solution. A slightly more complex example would be the detection of unbalanced tags in HTML and XML. The tokens are multiple characters rather than single characters, but the structure and logic of the problem remain exactly the same. Some other common stack-oriented problems are conversion of infix expressions to postfix form (or vice versa), evaluation of a postfix expression (as is done in a Java VM or many other interpreters), and in general any problem that has a recursive solution. In the next section, we'll take a short look at the relationship between stacks and recursion.

9.2.3. 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 an ancient 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 finished, the world would 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. And anyway, 64 disks would take 2⁶⁴-1 moves. A few minutes with a calculator reveals 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 disks stacked on it; call this the source pole. We want to move all of these to the destination pole, using a third (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 3 disks because 64 would occupy a computer for centuries.

def towers(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"]) towers(list)

The output produced here is:

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. And 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.

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.

9.2.4. 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.

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. There is even a SizedQueue variant.

These queues use the method names enq and deq rather than the longer names shown in the preceding example. They also allow the names push and pop, which seems misleading to me. The data structure is FIFO, not LIFO; that is, it is a true queue and not a stack.

Of course, the Queue class in tHRead.rb is thread-safe, which is a good enough reason for it to exist. If you need a thread-safe Stack class, I recommend you take the Queue class as a starting point. This should be a quick and easy fix.

The first edition of this book had a lengthy example of queue usage here. Like some of the stack examples, it has been omitted from this edition to save space.