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
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
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 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.
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
| | | |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,  ] ],
We use three stack pointers
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.
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, \<(=/ω＼=)>)
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()
To sum up