在一个数组中实现两个堆栈(Implement two stack in one array)

在一个数组中实现两个堆栈(Implement two stack in one array)

如何在一个数组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

How to implement two stack in one array A[1..n] in such a way that neither stack overflows unless total no. of elements in both stack together is n. PUSH and POP should run in O(1) time ?

What's wrong with this algo ?

//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

最满意答案

如果您尝试以这种方式实现它，两个堆栈都从数组的左侧开始。 推和流行不会是O（1）。 由于两个堆栈的元素将在彼此之间混合，因此您必须维护一个位置是属于stack1还是stack2，以及它是否为空（枚举）。

当您尝试将一个元素插入其中一个堆栈时，您必须搜索一个空插槽并将值放在那里（为此您可能会跳过其他堆栈中的元素）。

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

而且对于检查完全或空，最好检查两个堆栈中的元素总和。

Push和Pop将是O（n）而不是你想要的O（1）。

如果您仍然希望在O（1）中实现push和pop以及来自数组同一侧的两个堆栈，我建议您保持每个元素的堆栈，下一个自由索引和前一个/（下一个自由索引）的顶部。

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

例：自由= 0; top1 = -1，top2 = -1 next [i] = i + 1 next [n-1] = -1

检查完整只是完整== -1

检查堆栈空虚将是top1 == -1

将x插入前1

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

从stack1弹出

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）额外的内存

If you are trying to implement it this way that both stacks start from left side of the array. Push and pop won`t be O(1). Since the elements of both stacks will be intermixed among each other and you have to maintain whether a position belongs to stack1 or stack2 and if it is empty(enum).

When you are trying to insert an element into one of the stack you have to search for an empty slot and place the value over there (for this you might you might have skip elements of other stack which will be in between).

When you are trying to delete an element from one of the stack you have to mark the element as empty and find the element on the left side of the popped element which belongs to the corresponding stack and make it as top of the stack.

And also for checking full or empty it`s better to check with the sum of elements in both stacks.

Push and Pop would be O(n) instead of what you want as O(1).

If you still want to implement push and pop in O(1) and both stacks from same side of the array I suggest you to maintain top of both the stacks, next free index and previous/(next free index) for every element.

if element has been occupied it will point to previous index in stack else if it is free it will contain next free index.

Ex: free = 0; top1 = -1 , top2 = -1 next[i] = i+1 next[n-1] = -1 initially

checking for full is just full == -1

checking for stack emptiness would be top1 == -1

insert x into top 1

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

popping from stack1

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

Drawback for this implementation is we are using O(n) extra memory