在一个数组中实现两个堆栈

Question

如何在一个数组A[1..n]中实现两个堆栈，使得堆栈都不会溢出，除非总没有。两个堆叠在一起的元素的数量是 n。 PUSH 和 POP 应该在 O(1) 时间内运行 ?

这个算法有什么问题？

//A[1...n], top1 is pointer pointing to top of stack1.

top1=-1;
top2=-1;

STACK-EMPTY(A)

1. if(top1==0 && top2==0)
2.    return 1
3. else
4.    return 0

STACK-FULL(A)

1.  if(top1==S1.length && top2==S1.length)
2.     return 1
3.  else if(top1==S1.length)
4.     return -1
5.  else  if(top2==S2.length)
6.     return -2
7.  else
8.     return 0

PUSH (A,x)
1.  if(!STACK-FULL())
2.      if(STACK-FULL()==-1)
3.          top2=top2+1
4.          S2[top2]=x
5.      else if(STACK-FULL()==-2)
6.          top1=top1+1
7.          S1[top1]=x
8.      else
9.          top1=top1+1   
10.         S1[top1]=x
11. else
12.    OVERFLOW

Answer 1

如果您尝试以这种方式实现它，那么两个堆栈都从数组的左侧开始。推送和弹出不会是 O(1)。由于两个堆栈的元素将相互混合，您必须维护一个位置是属于 stack1 还是 stack2 以及它是否为空（枚举）。

当您尝试将一个元素插入其中一个堆栈时，您必须搜索一个空槽并将值放在那儿（为此，您可能会跳过其他堆栈中的元素，这些元素将介于两者之间).

当你试图从一个堆栈中删除一个元素时，你必须将该元素标记为空，并在弹出元素的左侧找到属于相应堆栈的元素，并将其作为顶部堆栈。

而且为了检查满或空，最好检查两个堆栈中元素的总和。

Push 和 Pop 是 O(n) 而不是你想要的 O(1)。

如果你仍然想在 O(1) 中实现压入和弹出，并且两个堆栈都来自数组的同一侧，我建议你保持两个堆栈的顶部，下一个空闲索引和上一个/（下一个空闲索引）对于每个元素。

如果元素已被占用，它将指向堆栈中的前一个索引，否则如果它是空闲的，它将包含下一个空闲索引。

例如：免费 = 0； top1 = -1 , top2 = -1 next[i] = i+1 next[n-1] = -1 initially

正在检查是否已满 == -1

检查堆栈是否为空将是 top1 == -1

将 x 插入前 1

a[free] = x
next[free] = top1 // useful while poping
top1 = free
free = next[free]

从堆栈 1 弹出

temp = top1 // storing top since we have to make this index as free and point next of this index to previous free
top1 = next[top1] // setting previous element as top
next[temp] = free
free = temp

此实现的缺点是我们使用了 O(n) 的额外内存

Answer 2

这也可以通过将 even_indexes 分配给 Stack1 并将 Odd 索引分配给 Stack2 来实现。这可能会解决使用动态数组大小实现的堆栈溢出问题。两个堆栈的 Top1 和 Top2 将始终指向相应偶数和奇数位置的索引。对于不同大小的筹码，我们将在相应的位置

有 NONE

在python

中使用一个列表实现两个堆栈

#Idea 是 Stack1 有 o 和偶数索引，Stack 2 有奇数索引

class ImplementTwoStacks:

def __init__(self):
    self.array = [None for count in range(2)]
    self.top1 = 0
    self.top2 = 1

def len_array(self):
    return len(self.array)

def pushStack1(self, item):
    if self.top1 == self.len_array() - 2:
        self.array = self.array + [None for count in range(10)]
    if self.top1 == 0:
        self.array[self.top1] = item
        self.top1 += 2
        return

    self.array[self.top1] = item
    self.top1 += 2
    return

def pushStack2(self, item):
    #all odd index
    if self.top2 == self.len_array() - 1:
        self.array = self.array.extend([1 for count in range(10)])

    if self.top2 ==1:
        self.array[self.top2] = item
        self.top2 += 2
        return

    self.array[self.top2] = item
    self.top2 += 2

    return

def popStack1(self):

    if self.top1 == 0:
        temp = self.array[self.top1]
        self.array[self.top1] = None
        return temp

    self.top1 -= 2
    temp = self.array[self.top1]
    self.array[self.top1] = None
    return temp

def popStack2(self):
    if self.top2 ==1:
        temp = self.array[self.top2]
        self.array[self.top2] = None
        return temp

    self.top2 -= 2
    temp = self.array[self.top2]
    self.array[self.top2] = None
    return temp


def display_stack1(self):

    for item in self.array[0:len(self.array):2]:
        if item:
            print(item, "", end= "->")

def display_stack2(self):
    for item in self.array[1:len(self.array):2]:
        if item:
            print(item, "", end="->")

在一个数组中实现两个堆栈

Implement two stack in one array

arrays

stack

data-structures

在python

#Idea 是 Stack1 有 o 和偶数索引，Stack 2 有奇数索引