1.单纯用list就可以实现，但并未用到队列相关知识。
class MyStack: def __init__(self): """ Initialize your data structure here. """ self.stack = [] def push(self, x): """ Push element x onto stack. :type x: int :rtype: void """ self.stack.append(x) def pop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ if self.stack == []: return False else: return self.stack.pop() def top(self): """ Get the top element. :rtype: int """ if self.stack == []: return False else: return self.stack[-1] def empty(self): """ Returns whether the stack is empty. :rtype: bool """ return self.stack == []
2.用两个队列(实际上是两个list)实现栈。
思路：
queue1用来存放数据，每次入栈就插入queue1索引值为0的地方。queue2为出栈时的辅助队列，将queue1[1:-1]的元素出队然后入队queue2(也就是queue1逆序压入queue2)，然后queue1仅剩队首元素，
这个时候出队即出栈。
class MyStack(object): def __init__(self): """ Initialize your data structure here. """ self.queue1 = [] self.queue2 = [] def push(self, x): """ Push element x onto stack. :type x: int :rtype: void """ self.queue1.insert(0, x) def pop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ for _ in range(len(self.queue1) - 1): self.queue2.insert(0, self.queue1.pop()) res = self.queue1.pop() self.queue1 = self.queue2 self.queue2 = [] return res def top(self): """ Get the top element. :rtype: int """ for _ in range(len(self.queue1) - 1): self.queue2.insert(0, self.queue1.pop()) res = self.queue1.pop() self.queue2.insert(0, res) self.queue1 = self.queue2 self.queue2 = [] return res def empty(self): return self.queue1 == [] obj = MyStack() obj.push(2) obj.push(0) obj.push(5) obj.push(-3) print(obj.pop()) print(obj.top()) print(obj.queue1) print(obj.empty())
3. Queue()和deque()区别：
queue:
-
queue是多线程中的使用的栈，但是Python 解释器有一个全局解释器锁(PIL)，导致每个 Python 进程中最多同时运行一个线程，因此 Python 多线程程序并不能改善程序性能，不能发挥多核系统的优势。
-
multiprocessing.Queue是Python 2.6 引入的用来实现多进程的一种高性能栈。
deque：
-
collections.deque是为了高效实现插入和删除操作的双向列表，适合用于队列和栈。
双端队列，两端均可操作。 extendleft将结合元素从“左边”加入到集合中。 appendleft(x)-append(x), popleft()-pop()等分别对左右端进行操作。
原理： 双端队列的数据被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中，此外容器还需要维护一个存放这些数组首地址的索引数组 ，简单的理解，你可以想成一个大的array，分拆成几段，然后主要维护一个索引表。 大家看了下面的图应该就理解了。
from Queue import Queue class MyStack(object): def __init__(self): """ Initialize your data structure here. """ #q1作为进栈出栈，q2作为中转站 self.q1=Queue() self.q2=Queue() def push(self, x): """ Push element x onto stack. :type x: int :rtype: void """ self.q1.put(x) def pop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ while self.q1.qsize()>1: self.q2.put(self.q1.get()) #将q1中除尾元素外的所有元素转到q2中 if self.q1.qsize()==1: res=self.q1.get() #弹出q1的最后一个元素 #while self.q2.qsize>0:#将q2的元素转移到q1中 # self.q1.put(self.q2.get())#这会出现超出时间显示错误,有实例不通过 tmp=self.q2 #交换q1,q2 self.q2=self.q1 self.q1=tmp return res def top(self): """ Get the top element. :rtype: int """ while self.q1.qsize()>1: self.q2.put(self.q1.get())#将q1中除尾元素外的所有元素转到q2中 if self.q1.qsize()==1: res=self.q1.get()#弹出q1的最后一个元素 self.q2.put(res)#与pop唯一不同的是需要将q1最后一个元素保存到q2中 #while self.q2.qsize>0:#将q2的元素转移到q1中 # self.q1.put(self.q2.get()) tmp=self.q2#交换q1,q2 self.q2=self.q1 self.q1=tmp return res def empty(self): """ Returns whether the stack is empty. :rtype: bool """ return not bool(self.q1.qsize()+self.q2.qsize())#为空返回True，不为空返回False
思路与上述方法2一样，只不过用的是queue，相关操作也变成了put等。