algorithm - 使用两个队列和有限队列大小实现堆栈

Question

跟进这个问题:Implement Stack using Two Queues

我正在寻求实现版本 A(高效推送)的答案，但是我还需要考虑队列大小，即我不能“永远排队”，但在某个时候队列将用完空间。

我需要确保所有推送操作都以恒定的时间复杂度完成。

我将如何继续实现它？一旦队列满了就复制队列显然会导致 O(n) 的复杂度。

我可以创建一个新的空队列并开始向那里推送，但是它需要代表一个堆栈，并且在弹出操作的某个点，它将到达新队列的末尾并且不知道其余的项目在旧队列中。

Answer 1

同意确定队列中要排队的项目数的上限。同样的事情也适用于 Stack。我们有一个“堆栈溢出”异常 - 可以在运行时发生 @push 操作来处理这种情况。类似地，我们有一个弹出操作的“堆栈下溢”异常。

检查取决于数据结构的大小(可以存储的项目数)。在这种情况下，它将是队列的大小。让我们将其表示为“n”。

带有异常的伪代码如下所示:

n = QUEUE_SIZE

def push()
  if len(queue1) >= n:
    print 'Stack Overflow'
    return
  else:
    #enqueue in queue1


def pop()
  if len(queue1) == 0:
    print 'Stack Underflow'
    return

  #while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
  #dequeue and return the last item of queue1, then switch the names of queue1 and queue2

在这里，在任何时间点，您的 Stack DataStructure(使用队列实现)将最多有“n”个项目，并且所有推送操作都是 O(1)。

它还会抛出“堆栈溢出”和“堆栈下溢”异常

希望对您有所帮助!