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

客官°小女子只卖身不卖艺 2024-04-06 13:33 64阅读 0赞

在Python中实现两个堆栈的队列。数据结构 了解堆栈和队列。然后用两个堆栈实现一个队列。 堆栈和队列都是列表。但它们有不同的、更严格的规则。本文将讨论堆栈和队列。首先，会有一个堆栈的实现，然后是用堆栈实现一个队列。

堆栈 堆栈是具有后进先出（LIFO）规则的列表。最后进去的元素，先出来。

你可能会想，这有什么用呢？一个很好的例子是编辑器中的撤销操作。当我们 "撤消 "时，它逆转了上次的操作。编译器使用一个堆栈来检查匹配的小括号。下面是堆栈所需的功能。

![alt][]

初始化一个空列表。 将元素添加到列表中。 从列表中跳出元素。 检查列表是否为空。 确定列表的顶部元素。 获取列表。 上述功能的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意味着从列表的底部删除一个元素。

这里的图片清楚地显示了堆栈和队列之间的区别。

![alt][alt 1]

我们可以用两个堆栈来实现一个队列。

对堆栈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 ][mdnice]多平台发布

[alt]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/d5c76762193748bfb4beb30f3ad05952.png
[alt 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/1cff678df50d4965a1024e77ed2bdc80.png
[mdnice]: https://mdnice.com/?platform=4