使用 2 个堆栈实现队列，具有恒定的时间复杂度

Question

我想知道是否可以使用两个堆栈来实现一个队列，以便每个队列操作都需要摊销常数时间。

Answer 1

class QQ: 
    def __init__(self): 
        self.s = [] 
        self.ss = [] 
    def enque(self, val): 
        self.s.append(val) 
    def deque(self): 
        if not self.s and not self.ss: return None 
        if not self.ss: 
            while self.s: 
                self.ss.append(self.s.pop()) 
        return self.ss.pop()

当我们将 s 的元素弹出到 ss 时，第二个堆栈 ss 以相反的顺序保存第一个堆栈 s 的内容。反向堆栈只是一个队列。每当 ss 为空时，我们将 s 中的所有元素加载到 ss 中。如果它不为空，我们只是 deque 其中的一个元素。

时间复杂度是摊销常量，因为我们只进行了 enqueing 的一次移动，而在长运行中，dequeing 只进行了 2 次移动。

Answer 2

我们使用 2 个带有标签“正面”和“背面”的堆栈。

在栈前我们应该使用size 和clear 方法，其中size returns 栈的指针，clear 将指针设置为0。

对于enqueue()，我们应该将新元素压入栈顶。所以时间复杂度将是 O(1).

对于dequeue()，如果后栈为空，我们应该用前栈中的元素填充它，对于前栈中的每个元素我们应该调用pop()函数然后使用 push() 函数将其插入后栈，因为我们知道前栈的大小（并且它是常数）并且 pop 和 push 函数的时间复杂度为 O(1)，出队的整个复杂度将是 O(1).

对于size()，会return前后端栈之和size()。对于 isEmpty() 它应该 return 如果大小等于或不等于零。

使用 2 个堆栈实现队列，具有恒定的时间复杂度

implement queue using 2 stacks, with constant time complexity

data-structures

queue

stack

time-complexity