如何在O(1)时间复杂度中删除堆栈的中间元素

Question

好吧，我用数组在GeeksforGeeks上试过这个问题。但是GeeksforGeeks中的解决方案说，我们必须使用链表来删除O(1(时间复杂性中堆栈的中间元素。但我也有一个使用数组的解决方案，我想确认它是否正确。删除中间元素的解决方案是：-

假设我们有一个名为stk[]的堆栈

1. 通过计算m=(Top+1(/2找到中间元素
2. 交换stk[Top]和stk[m]的值
3. 移除最上面的元素
4. 然后再次交换值stk[Top]和stk[m]

如果堆栈元素的数量小于3，只需从堆栈中删除最顶部的元素。我认为这个解决方案的时间复杂度也为O(1(，因为这里没有循环。那么，有人能说出这是否是解决这个问题的正确方法吗？

Answer 1

我想你指的是这个谜题。你的方法改变了元素的顺序。例如，如果堆栈是

1 2 3 4 5 6 7

(底部有1个，顶部有7个(，然后在步骤2之后，我们有

1 2 3 7 5 6 4

并且在步骤3之后

1 2 3 7 5 6

最后在步骤4 之后

1 2 3 6 5 7

，这不是我们想要的(我们想要1 2 3 5 6 7(。

此外，您的方法打破了难题提出的抽象，即只使用堆栈操作push()、pop()和empty()。您不应该直接访问底层数组。再说一遍，这个谜题在使用递归时打破了自己的抽象。递归有自己的堆栈，它实际上是一个额外的数据结构。