Technetra

Implementing a Stack with Two Queues: A Simple Ruby Demonstration

Robert Adkins,  December 4th, 2008 at 5:23 am

How do we turn pipes into stacks without resorting to index or pointer manipulation? That is, suppose we have only the ability to create FIFOs for pipe-like behavior but we want to create LIFOs for alternative stack-like behavior.

A FIFO is an opaque structure that allows items to be placed or pushed onto it at one end (head) and removed or pulled from it, one at at time and in sequence, from the other end (tail). A LIFO is a similarly opaque structure that allows items to be pushed onto it at one end (head or top) and removed or popped from it from that same end (head). This means that items of a LIFO are removed one at a time but in the reverse order of when they were entered. Let us further suppose that our only FIFO primitives are an append operator ‘push’ and a pull operator ’shift’. ‘push’ adds elements to the head of the FIFO and ’shift’ grabs (and removes) items from the tail of the structure.

Therefore, we want to build a stack (LIFO) using the pipe (FIFO) structure and its two primitive operators, ‘push’ and ’shift’. Essentially, we wish to combine ‘push’ (onto head) and ’shift’ (from tail) pipe operators in some fashion to simulate ‘push’ (onto head) and ‘pop’ (from head) stack operators.

The following short Ruby program demonstrates a simple solution to this puzzle. Basically we shift items between two FIFO structures to simulate the operations of a stack. But this program is notable less in the algorithm selected and more in the way Ruby expresses the steps required. Interesting Ruby idioms include parallel assignment, variable length argument lists, and simple method definitions and usage.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#!/usr/bin/env ruby
#
# Implementing a Stack with Two Queues: A Simple Ruby Demonstration
# -----------------------------------------------------------------
# 
# How do we turn pipes into stacks without resorting to index or
# pointer manipulation? That is, suppose we have only the ability to
# create FIFOs for pipe-like behavior but we want to create LIFOs
# for alternative stack-like behavior.
# 
# A FIFO is an opaque structure that allows items to be placed or
# pushed onto it at one end (head) and removed or pulled from it, one
# at at time and in sequence, from the other end (tail). A LIFO is a
# similarly opaque structure that allows items to be pushed onto it at one
# end (head or top) and removed or popped from it from that same end
# (head). This means that items of a LIFO are removed one at a time
# but in the reverse order of when they were entered. Let us further
# suppose that our only FIFO primitives are an append operator 'push'
# and a pull operator 'shift'. 'push' adds elements to the head of
# the FIFO and 'shift' grabs (and removes) items from the tail of
# the structure.
# 
# Therefore, we want to build a stack (LIFO) using the pipe
# (FIFO) structure and its two primitive operators, 'push' and
# 'shift'. Essentially, we wish to combine 'push' (onto head) and
# 'shift' (from tail) pipe operators in some fashion to simulate 'push'
# (onto head) and 'pop' (from head) stack operators.
# 
# The following short Ruby program demonstrates a simple solution to
# this puzzle. Basically we shift items between two FIFO structures
# to simulate the operations of a stack.  But this program is notable
# less in the algorithm selected and more in the way Ruby expresses the
# steps required. Interesting Ruby idioms include parallel assignment,
# variable length argument lists, and simple method definitions
# and usage.
#
# Copyright (c) 2008 Technetra Corp
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
#
# Implementation of Stack Using Two Queues
class Stack
  def initialize *s # splat operator allows variable length argument list
    @q1 = []
    @q2 = []
    s.each { |e| push e }
  end
  def push v
    # pure FIFO allows only 'push' (onto head) and 'shift' (from tail)
    # LIFO requires 'push' (onto head) and 'pop' (from head)
    empty_queue, full_queue = @q1.length == 0 ? [ @q1, @q2 ] : [ @q2, @q1 ]
    empty_queue.push v
    until (v = full_queue.shift).nil? # shift each item from non-empty queue,
      empty_queue.push v              # pushing it onto initially empty queue:
                                      # produces new full queue in reverse entry order
    end 
  end
  def pop
    full_queue = @q1.length > 0 ? @q1 : @q2
    # full queue has been maintained in reverse order
    # by the push method of the Stack class, so a simple
    # shift is all that is needed to simulate a stack
    # pop operation
    el = full_queue.shift
  end
  def empty?
    @q1.length == 0 && @q2.length == 0
  end
end
 
# test:
puts "STACK: tail/bottom -> x, y, z <- head/top"
stack = Stack.new
stack.push 'x'
stack.push 'y'
stack.push 'z'
# or equivalently, stack = Stack.new('x', 'y', 'z')
until stack.empty?
  puts "popping stack, item: #{stack.pop}"
end
# prints items in reverse order: 'z', 'y', 'x'

Copyright © 2008 Technetra. This code is covered by the MIT License. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pings are currently closed.

Building a Simple iPhone Web App: RedGreen…YellowBlue Article Index Pairing Stubborn Bluetooth Devices in Fedora 10 & Ubuntu Ibex

Comments

Be the first to post a comment.

Add a comment