栈和队列的特性：
栈：先进后出
队列：先进先出
1.用两个队列实现一个栈：（使用数组来实现）
class stack(): def __init__(self): self.queue1=[] self.queue2=[] def push(self,ele): self.queue1.append(ele) def pop(self): if len(self.queue2)==0: while len(self.queue1)>1: self.queue2.append(self.queue1.pop(0))###依次往队列2中放入队列1的元素,队列1只有一个元素了，就是最后一个元素 self.queue1,self.queue2=self.queue2,self.queue1###进行交换，上面的queue2有全部queue1的节点，最后一个没有 return self.queue2.pop() def top(self): if len(self.queue1)!=0: return self.queue1[len(self.queue1)-1] return None def empty(self): if len(self.queue1)==0: return True return False obj=stack() list=list(range(0,10)) print(list) for i in range(0,10): obj.push(list[i]) for i in range(0,7): print(obj.pop()) print(obj.top())
class Stack: def __init__(self): self.queue1=[] self.queue2=[] def push(self, x): self.queue1.append(x) def pop(self): if len(self.queue2)==0: while len(self.queue1)>1: self.queue2.append(self.queue1.pop(0))##依次加进去 self.queue1,self.queue2=self.queue2,self.queue1 return self.queue2.pop() def top(self): if len(self.queue1)!=0: return self.queue1[len(self.queue1)-1]##直接返回最后一个就好了 return None # if len(self.queue2)==0: # while len(self.queue1)>1: # self.queue2.append(self.queue1.pop(0)) # item=self.queue1.pop() # self.queue1,self.queue2=self.queue2,self.queue1 # self.queue1.append(item) # return item#top不应该不返回值过来 def isEmpty(self): return not len(self.queue1)##当为真的时候就是为空的时候
使用队列来实现：（使用队列来实现）
import queue class Mystack(): def __init__(self): self.queue1=queue.Queue() self.queue2=queue.Queue() def push(self,ele): self.queue1.put(ele) def pop(self): if self.queue2.empty(): while self.queue1.qsize()>1:######留下最后得一个元素，最后pop出来 self.queue2.put(self.queue1.get())####得到队列前面，留下队列1最后得一个元素，之前的全部元素放入队列2（除了最后一个元素） self.queue1,self.queue2=self.queue2,self.queue1##交换，队列2放入队列1的最后一个元素，队列2里面就一个元素，队列1里面有除掉最后元素的全部元素 return self.queue2.get()## # obj=Mystack() # list=list(range(0,10)) # for i in range(0,10): # obj.push(list[i]) # for i in range(0,10): # print(obj.pop())
用两个栈来实现队列：
class Queue(): def __init__(self): self.stack1=[] self.stack2=[] def push(self,element): self.stack1.append(element) def pop(self): if len(self.stack2)==0: self.stack2.append(self.stack1.pop())##放进最后一个值进去 return self.stack2.pop()
栈集||
描述
中文English
假如你有一堆的盘子。如果你堆得太高的话，就可能会垮掉。所以，在真实的生活中，如果盘子叠到一定高度，你会重新开始堆新的一堆盘子。
实现这样的一个数据结构，我们称之为栈集，来模拟这个过程。这个栈集包含若干个栈（可以理解为若干堆的盘子），如果一个栈满了，就需要新建一个栈来装新加入的项。你需要实现栈集的两个方法，push(item) 和 pop()，让这个栈集对外表现得就像是一个栈在进行操作一样。
您在真实的面试中是否遇到过这个题？
样例
例1:
输入：
SetOfStacks(2); // create a SetOfStacks object with capacity = 2
push(1)
push(2)
push(4)
push(8)
push(16)
pop() // return 16
pop() // return 8
pop() // return 4
例2:
输入：
SetOfStacks(5)
push(1)
push(2)
push(3)
push(4)
push(5)
push(32)
pop() // return 32
push(64)
pop() // return 64
挑战
后续问题: 为栈集实现一个popAt(int index)的方法，让他可以直接从给定的某个栈上进行pop。
链接: 栈集II
class SetOfStacks: """ @param: capacity: An inetger, capacity of sub stack """ def __init__(self, capacity): # do intialization if necessary self.stacks=[]#相当于是[[],[],[],[],[]]的效果 self.capacity=capacity """ @param: v: An integer @return: nothing """ def push(self, v): # write your code here if len(self.stacks)==0: self.stacks.append([]) if self.stacks[-1]==self.capacity:##加入最后的一个堆栈超过了最大限制的话 self.stacks.append([]) self.stacks[-1].append(v) """ @return: An integer """ def pop(self): # write your code here if len(self.stacks[-1]) is None:##只需要对最后的一个栈进行判断就好了 self.stacks.pop()##移除掉最后的一个[] v=self.stacks[-1].pop()##取出最后的一个值出来,[x,x,x,x]最后的值出来 return v