在Python中实现两个堆栈的队列。数据结构
了解堆栈和队列。然后用两个堆栈实现一个队列。
堆栈和队列都是列表。但它们有不同的、更严格的规则。本文将讨论堆栈和队列。首先，会有一个堆栈的实现，然后是用堆栈实现一个队列。
堆栈
堆栈是具有后进先出（LIFO）规则的列表。最后进去的元素，先出来。
你可能会想，这有什么用呢？一个很好的例子是编辑器中的撤销操作。当我们 "撤消 "时，它逆转了上次的操作。编译器使用一个堆栈来检查匹配的小括号。下面是堆栈所需的功能。
初始化一个空列表。
将元素添加到列表中。
从列表中跳出元素。
检查列表是否为空。
确定列表的顶部元素。
获取列表。
上述功能的Python实现。
class Stack():
def __init__(self):
self.elements = []
def push(self, element):
self.elements.append(element)
def pop(self):
return self.elements.pop()
def is_empty(self):
return self.elements == []
def peek():
if not self.elements.is_empty():
return self.elements[-1]
def get_elements(self):
return self.elements
队列
一个队列也是一个列表或容器。它遵循先进先出（FIFO）规则。一个很好的例子是杂货店里的排队。先来排队的人有机会付款并先离开。
当一个新的人想要排队时，他/她必须排在队伍的后面。队列有两个操作。Enqueue和dequeue。其中enqueue意味着在列表或容器中添加元素。Dequeue意味着从列表的底部删除一个元素。
这里的图片清楚地显示了堆栈和队列之间的区别。
我们可以用两个堆栈来实现一个队列。
对堆栈1中的元素进行queue。
Dequeue可能很棘手。因为堆栈会从顶部移除一个元素。但是队列从底部移除一个元素。我们需要从堆栈1中弹出所有的元素，并在堆栈2中不断添加它们。所以，stack1的底部元素将是stack2的顶部元素。现在，如果我们从栈2中弹出一个元素，我们就弹出了栈1的底部元素。所以，这就是我们的dequeue操作。操作完成后，我们应该把这些元素再次放回栈1。下面是代码的样子。
class Queue:
def __init__(self):
self.stack_1 = Stack()
self.stack_2 = Stack()
def enqueue(self, item):
self.stack_1.push(item)
def dequeue(self):
if not self.stack_1.is_empty():
while self.stack_1.size()> 0:
self.stack_2.push(self.stack_1.pop())
res = self.stack_2.pop()
while self.stack_2.size()>0:
self.stack_1.push(self.stack_2.pop())
return res
我想分享这个，因为它是学习算法和数据结构的一个很好的练习材料。
下面是一篇关于使用排序算法解决问题的文章。寻找两组坐标的交点并按颜色对桶进行排序。
用Python OOP寻找两组坐标的交点并按颜色排序
解决两个编程问题，一个用排序算法，另一个用Python的OOP。
这篇文章是关于一些编程练习。如果你是一个学习者，正在学习Python中的Data Stricture和OOP，它可能对你有帮助。我将解决两个问题，并尽可能多地解释。我假设你也知道Python编程的基础知识和OOP基础知识。这两个问题的思路来自于Coursera的《算法》课程，第一部分。
问题1
开发一个算法，接收两个坐标列表并返回它们的交集。我们需要找到这两个列表中的共同坐标。
解决方法
解决这个问题有4个步骤
合并两个列表，从两个列表中选出一个列表。
对这个合并的列表进行排序，先按x坐标排序，再按y坐标排序。因此，如果有任何共同的项目，它们将被并排排列。
然后返回重复的坐标。
下面是完整的代码。函数'concArray'将连接这些列表。函数'sortList'将对坐标进行排序。函数'clash'将返回两个连续坐标是否相同。
class Intersection():
def __init__ (self, sets):
self.sets = sets
def concArrays(self):
self.sets = self.sets[0] + self.sets[1]
return self.sets
def sortList(self):
self.sets = sorted(self.sets, key=lambda x: x[0])
return sorted(self.sets, key=lambda x: x[1])
def clash(self):
return [self.sets[i] for i in range(0, len(self.sets)-1) if self.sets[i] == self.sets[i+1]]
让我们检查一下该算法是否正常工作。
sets = [[(2,4),(5,3),(2,6),
(6,2),(4,9)],[(4,9),
(10,8),(9,3),(5,3),(1,7)]]
inter = Intersection(set)
inter.concArrays()
inter.sortList()
print(inter.clash())
返回[（4，9），（5，3）]
如果你注意到在我们的 sets 变量中，这就是两个共同的坐标。由于我们的列表不是太大，我们可以只通过观察来检查。
问题2
给出一个有n个桶的列表，每个桶里都有蓝色、白色或红色的卵石。请按照红、白、蓝的顺序对它们进行颜色排序。
解决方法
这个问题可能有不同的解决方法。我将展示两种解决方案。第一种是使用一种排序算法。这里我使用了插入式排序。任何其他的排序算法都会以同样的方式工作。
下面是步骤。
建立一个字典，颜色是键，值是整数。
在排序算法中，在比较两种颜色时使用字典中的值。
下面是完整的代码。
`
def sortColor(a):
color = {'red': 1, 'white': 2, 'blue': 3}
for i in range(1, len(a)):
value = a[i]
hole = i
while (hole > 0) and (color[a[hole -1]]>color[value]):
a[hole] = a[hole -1]
hole = hole -1
a[hole] = value
return a
用下面的颜色列表检查这个算法。
print(sortColor(['red', 'white', 'red',
'blue', 'white', 'blue']))
输出结果很完美。请试试吧。
如何使用lambda实现
def sortColor1(a):
color = {'red': 1, 'white': 2, 'blue': 3}
return sorted(a, key=lambda x: a[color[x]], reverse=True)
我希望这对你有帮助。
本文由mdnice多平台发布
