栈和队列的相互转化

最近面试被问到一道题，如何用两个Queue实现一个Stack,没有回答上来，十分惭愧，回来赶紧上网查看，发现这是一道很普遍的面试题，包括“如何用两个Stack实现一个Queue”

面试的时候我一直纠结于“巧妙的方法”可以让两个列表实现一个栈，直到现在到处翻查，也并没有找到一个巧妙的方法。目前能看到的解法依然只有：‘将一个队列A不断pop到另一个队B里中去，直到最后一个元素，将其删除，然后再将队列B赋值回队列A’，代码如下：

class Stack(object): 
    def __init__(self): 
        self.stack = Queue() 
        self.tmp = Queue() 

    def isEmpty(self): 
        return self.stack.isEmpty() 

    def push(self,x): 
        self.stack.push(x) 

    def pop(self): 
        while self.stack.size() > 1: 
            self.tmp.push(self.stack.pop()) 
        a = self.stack.pop() 
        while not self.tmp.isEmpty(): 
            self.stack.push(self.tmp.pop()) 
        return a 

    def top(self): 
        while self.stack.size() > 1: 
            self.tmp.push(self.stack.pop()) 
        a = self.stack.front() 
        while not self.tmp.isEmpty(): 
            self.stack.push(self.tmp.pop()) 
        return a 

网上流传一种使用AB双列表，并用一个指示器指向当前正在使用的列表的方法，可以在pop的时候减少一次列表的捣腾，不过我认为也没必要了。既然我们非得用两个队列来实现一个栈的话，只是一种用两个先进先出结构别扭的转化成一个先进后出的结构的智力游戏（如果日后找到了一个我真的想找的巧妙方法，我再来更改这句话），就没有必要追求所谓的效率了

有了这个方案，两个栈实现一个列表显然变得容易了

class Queue(object): 
    def __init__(self): 
        self.queue = Stack() 
        self.tmp = Stack() 

    def isEmpty(self): 
        return self.queue.isEmpty() 

    def push(self,x): 
        self.queue.push(x) 

    def pop(self): 
        while not self.queue.isEmpty(): 
            self.tmp.push(self.queue.pop()) 
        a = self.tmp.pop()
        while not self.tmp.isEmpty(): 
            self.queue.push(self.tmp.pop()) 
        return a 

    def front(self): 
        while not self.queue.isEmpty(): 
            self.tmp.push(self.queue.pop()) 
        a = self.tmp.top()
        while not self.tmp.isEmpty(): 
            self.queue.push(self.tmp.pop()) 
        return a 

也许面试题是用两个栈来实现一个队列的话，我想我应该当场就答出来了，因为用两个栈相互取反一下达到一个负负得正的效果是大多数人都能想到的，又比较唯一的方法

但是用一个队列向另一个队列输出，然后还留了一个在里面来达到栈的效果，大多数人都会觉得这种方法难道不是很不妥吗，有点二

这里也有用一个有意思的讨论，就是传说某google的面试官说Stack是更基础的结构而非Queue,然后大家就讨论到底哪一个是更基础的结构。

当时，之所以说Stack更基础就是因为用Stack可以构造出Queue，而反之不行。其实显然上面已经证明了这是可以的，但也显然证明了大家对用两个Queue构造一个Stack的做法更不认同吧，比用两个Stack构造一个Queue更不适应

其实，本质还是在我的心目中，所谓数据结构，意味着好的存储方式，高的效率，好的逻辑结构。一个数据结构，重的是内在的处理方式，而不是外在的表现形式。我想，一如上面那个可以实现‘先进后出’的‘栈’一样，其实无论如何也不能称之为一个‘栈’吧

附上队列和栈的单独实现

队列的python实现

class Queue(object):

    def __init__(self):
        self.queue = []

    def isEmpty(self):
        return self.queue == []

    def push(self,x):
        self.queue.append(x)

    def pop(self):
        if self.queue:
            a = self.queue[0]
            self.queue.remove(a)
            return a
        else:
            raise IndexError, 'queue is empty'

    def front(self):
        if self.queue:
            return self.queue[0]
        else:
            raise IndexError,'queue is empty'

    def size(self):
        return len(self.queue)

栈的python实现

class Stack(object):

    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return self.stack == []

    def push(self,x):
        self.stack.append(x)

    def pop(self):
        if self.stack:
            a = self.queue[-1]
            self.queue.remove(a)
            return a
        else:
            raise IndexError, 'stack is empty'

    def top(self):
        if self.stack:
            return self.queue[-1]
        else:
            raise IndexError,'stack is empty'

    def size(self):
        return len(self.stack)