Home > Articles > Programming > Ruby

  • Print
  • + Share This
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.

  • + Share This
  • 🔖 Save To Your Account