1. 一个列表实现两个栈
class twostacks(object):
def __init__(self):
self.stack=[]
self.a_size=0
self.b_size=0
self.top=0
def a_isempty(self):
return self.a_size==0
def a_push(self,item):
self.stack.insert(self.a_size,item)
self.a_size+=1
def a_pop(self):
if self.a_size>=1:
item=self.stack[self.a_size-1]
self.stack.remove(item)
self.a_size-=1
return item
def b_isempty(self):
return self.b_size==0
def b_push(self,item):
self.stack.insert(self.a_size,item)
self.b_size+=1
def b_pop(self):
if self.b_size>=1:
item=self.stack[self.a_size]
self.stack.remove(item)
self.b_size-=1
return item
2. 两个栈实现一个队列
有两个栈s1，s2。入队时，将元素压入s1。出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
class stack(object):
def __init__(self):
self.stack=[]
def isempty(self):
return self.stack==[]
def push(self,item):
self.stack.append(item)
def pop(self):
if self.isempty():
raise indexerror,'pop from empty stack'
return self.stack.pop()
def size(self):
return len(self.stack)
class queue_with_stacks(object):
def __init__(self):
self.stacka=stack()
self.stackb=stack()
def isempty(self):
return self.stacka.isempty() and self.stackb.isempty()
def enqueue(self,item):
self.stacka.push(item)
def dequeue(self):
if self.stackb.isempty():
if self.stacka.isempty():
raise indexerror,'queue is empty.'
while self.stacka.size()>=2:
self.stackb.push(self.stacka.pop())
return self.stacka.pop()
else:
return self.stackb.pop()
3. 两个队列实现一个栈
class queue(object):
def __init__(self):
self.queue=[]
def isempty(self):
return self.queue==[]
def enqueue(self,x):
self.queue.append(x)
def dequeue(self):
if self.queue:
a=self.queue[0]
self.queue.remove(a)
return a
else:
raise indexerror,'queue is empty'
def size(self):
return len(self.queue)
class stack_with_queues(object):
def __init__(self):
self.queuea=queue()
self.queueb=queue()
def isempty(self):
return self.queuea.isempty() and self.queueb.isempty()
def push(self,item):
if self.queueb.isempty():
self.queuea.enqueue(item)
else:
self.queueb.enqueue(item)
def pop(self):
if self.isempty():
raise indexerror,'stack is empty'
elif self.queueb.isempty():
while not self.queuea.isempty():
cur=self.queuea.dequeue()
if self.queuea.isempty():
return cur
self.queueb.enqueue(cur)
else:
while not self.queueb.isempty():
cur=self.queueb.dequeue()
if self.queueb.isempty():
return cur
self.queuea.enqueue(cur)
以上就是python数据结构——栈、队列的实现(二)的内容。