在Python中实现两个堆栈的队列

在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多平台发布