代码之家  ›  专栏  ›  技术社区  ›  tamir

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

  •  0
  • tamir  · 技术社区  · 7 年前

    关于这个问题的后续行动: Implement Stack using Two Queues

    我希望实现答案的A版(高效推送),但我还需要考虑队列大小,即我不能“永远排队”,但在某个时候队列将耗尽空间。

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

    我将如何继续实现这一点?一旦队列满了,复制它显然会导致O(n)的复杂性。

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

    1 回复  |  直到 7 年前
        1
  •  1
  •   arunk2    7 年前

    同意确定要在队列中排队的项目数的上限。同样的道理也适用于堆栈。我们有一个“堆栈溢出”异常,它可能在运行时的推操作中发生,以处理这种情况。类似地,对于pop操作,我们有一个“堆栈下溢”异常。

    检查取决于数据结构的大小(可以存储的项目数)。在这种情况下,它将是队列的大小。让我们把它说成“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
    

    在这里,您的堆栈数据结构(使用队列实现)在任何时候都最多有“n”个项目,并且所有推送操作都是O(1)。

    它还引发“堆栈溢出”和“堆栈下溢”异常

    希望有帮助!