This problem is from the book *Algorithms, 4th Edition*.

Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations.

Warning : high degree of difficulty.

When I search the Internet to find a solution, I find varieties of this problem, such as "implement a queue with ONE stack", "implement a queue with TWO stack", etc.

It is fun, indeed. I spent the whole morning to finding the solution of these problems. So, let's rock.

## Build a test environment

I choose python as a programming language.

So firstly, I implement an **ABstract Class**(ABC) of a queue as the template of all classes of queue, called `QueueTpl`

.

```
import abc
class QueueTpl(object):
__metaclass__ = abc.ABCMeta
@abc.abstractmethod
def __init__(self):
pass
@abc.abstractmethod
def clear(self):
pass
@abc.abstractmethod
def push(self, value):
pass
@abc.abstractmethod
def pop(self, value):
pass
```

Secondly, I write an **Adapter** for `Queue.Queue()`

class of python, called `QueueAdapter`

, to make it returns `None`

when we get items from an empty instance.
And we use `put_nowait`

and `get_nowait`

to speed up because there's no need to get the guarantee of **thread safe**.

```
import Queue
class QueueAdapter(QueueTpl):
def __init__(self):
self.clear()
def clear(self):
self.q = Queue.Queue()
def push(self, value):
self.q.put_nowait(value)
def pop(self):
if self.q.empty():
return None
return self.q.get_nowait()
```

At last, use `python unittest`

to verify my solution.

```
class TestStQueue(unittest.TestCase):
def test_push_and_pop(self):
sq = QueueAdapter()
sq.push(1)
self.assertEqual(sq.pop(), 1)
self.assertFalse(sq.pop())
for i in xrange(10):
sq.push(i)
for i in xrange(10):
self.assertEqual(sq.pop(), i)
self.assertFalse(sq.pop())
def get_rand_command(self):
cmd = random.choice(['push', 'pop'])
value = random.randint(0, 1 << 31)
return cmd, value
def test_brute_force(self):
step = 10000
qs = [QueueAdapter(), StQueue3(), StQueue2(), StQueue1()]
for i in xrange(step):
a, b = self.get_rand_command()
if a == 'push':
map(lambda q: q.push(b), qs)
else:
rs = map(lambda q: q.pop(), qs)
self.assertTrue(all(x == rs[0] for x in rs))
```

## Implement a queue with ONE stack

It's said that it's an interview problem of Microsoft.(gossip, perhaps)

The problem asks us to implement a queue with ONLY ONE stack. It seems hard, but it is actually an easy problem.

The `push`

function is easy, just push the value into the stack. And the `pop`

function is a little bit hard, but we can do it with recursion to get the first element of the "queue", and put every items else in their origin order in the stack.

The code is short, too.

```
class StQueue1(QueueTpl):
def __init__(self):
self.clear()
def clear(self):
self.a = []
def push(self, value):
self.a.append(value)
def pop(self):
if not self.a:
return None
if len(self.a) == 1:
return self.a.pop()
else:
v = self.a.pop()
res = self.pop()
self.a.append(v)
return res
```

The time complexity of a `push`

is O(1) with no extra memory space; a `pop`

is takes O(n) of time, and O(n) extra memory space in the **stack area**(not the stack).

## Implement a queue with TWO stacks

This problem is so classic and so popular, so I just paste my solution here as everyone knows the answer.

```
class StQueue2(QueueTpl):
def __init__(self):
self.clear()
def clear(self):
self.a = []
self.b = []
def push(self, value):
self.b.append(value)
def pop(self):
if not self.a:
while self.b:
self.a.append(self.b.pop())
if not self.a:
return None
return self.a.pop()
```

## Implement a queue with THREE stacks

As it is said in the book, it's a hard problem. And here is a discuss in the Stackoverflow where I find this solution.

```
| | | |3| | | |
| | | |_| | | |
| | |_____| | |
| | | |
| | |2| | |
| | |_| | |
| |_________| |
| |
| |1| |
| |_| |
|_____________|
```

This solution uses nested stacks to perform as a **linked-list**, and use the **linked-list** to perform as a queue.

A queue of "1, 2, 3" looks like this:

```
[1,
[2,
[3]
]
],
```

We use three stack pointers `stack_a`

`stack_b`

and `stack_c`

, `stack_a`

points to the stack which stores the nested stacks, and `stack_b`

is a pointer to the last stack the nested stack, `stack_c`

as a temporary stack pointer.

So, `push`

function is just push the new value in the last stack in the stack which is pointed by pointer `stack_b`

, and then push a new stack in `stack_b`

and make `stack_b`

to point to the new stack. (complicated, \<(=*/ω＼*=)>)

The `pop`

function is to get the first element of the nested stack, just get the first element, and make `stack_a`

point to the rest of the data.

This code is easy but may hard to understand.

```
class StQueue3(QueueTpl):
def __init__(self):
self.clear()
def clear(self):
self.a = []
self.b = self.a
self.c = None
def push(self, value):
self.c = [value]
self.b.append(self.c)
self.c = []
self.b.append(self.c)
self.b = self.c
def pop(self):
if len(self.a) == 0:
return None
self.c = self.a.pop()
self.a = self.a.pop()
res = self.a.pop()
self.a = self.c
return res
```

## The main function

```
if __name__ == '__main__':
unittest.main()
```

## Comments

comments powered by Disqus