如何以及为什么在两个堆栈上排队

哈Ha！

这篇文章是为奥林匹克编程的初学者和准备进行算法面试的新手编写的。 在奖金难题的结尾。 如果有兴趣，我要一只猫:)

首先，让我们回顾一下基本知识：

叠放

堆栈实现了LIFO的原理（英语，后进先出，“后进先出”）。

堆栈有两个主要操作：

• 推-将项目推入堆栈
• 弹出-从堆栈中获取元素

堆栈通常在数组上实现（仍然可以在链表上实现）。 您可以在此处阅读有关堆栈及其实现的更多信息。

列

队列是一种可以访问FIFO元素的数据结构（先进先出-“先到先出”）

队列在其接口中有两种主要方法：

• 推-将项目放在队列的末尾
• pop-从队列的最前面获取一个元素

在此处阅读有关常规队列的更多信息。

通常，考虑两种实现队列的基本方法：

1. 在阵列上
2. 在链表上

为什么堆栈比生产线凉爽

想象一下，我们的数据结构应支持以下一组操作：

• 最低支持量（分钟）
• 最大支持（最大）
• GCD支持（英语最大公约数-最大公约数）
• LCM支持（最小公倍数）

所有这些操作都是关联的（形成一个半群），但是它们都不具有逆元素（不构成一个群）。

对于堆栈，您可以非常简单地支持以下任何操作：只需将几个存储在其顶部即可：

$$

$$（element，operationResult）$$

该对中的第二个元素是应用于堆栈中所有元素的运算结果。

以下是Python中最低堆栈支持实现的示例：

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

现在考虑如何对队列执行相同的操作？ 如果您尝试在阵列上组织经典队列，则不太可能解决问题。 这是由于最小运算不具有逆运算的事实（例如，加法运算具有减法运算）。 您可能已经猜到了，那么我将讨论两个堆栈上队列的不太经典的实现。

两个堆栈队列

必须满足的主要条件是必须对摊销的O（1）执行所有操作。

取两个堆栈：s1和s2。

推操作将始终在s1堆栈上完成。

弹出操作的组织方式如下：如果s2堆栈为空，则通过连续调用pop和push来将所有元素从s1转移到s2。 现在，s2堆栈包含相反顺序的元素（最上面的元素是轮到我们的第一个元素）。

如果s2不为空，我们会愚蠢地从中获取元素。 一旦s2再次为空，我们将重复相同的操作。

Python代码：

 class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

工作时间

推入操作 ：我们愚蠢地将项目推入s1堆栈。 运行时间O（1）。

弹出操作 ：对于每个元素，我们在一个堆栈之间进行的转移不超过一个，因此，摊销的工作时间将为O（1）。

操作get_min ：s1和s2堆栈已知最小值，因此我们仅取最小值。 运行时间O（1）。

奖金挑战

给定N个数字序列。 给定数字M <N。在线性时间内需要找到长度为M的段，其乘积min * max为最大值。

结论

感谢您阅读到底！

如果您对该主题感兴趣，则可以在此处阅读如何在两个堆栈上建立持久队列，或者等待下一个主题的发布。

在评论中写下在面试或竞赛中必须解决的两个任务上的任务。