我有一个堆栈规范，其中---> *可以查看具有最高（或最低或左右）值的对象。 *堆栈上的每个对象都是可比较的。实现给定堆栈的最有效的方法
我会希望尽快
无效推送（E E）执行下面的操作;
void pop（E e）;
E peekMidElement（）; [size（）/ 2）+1]
E peekHighestElement（）;
E peekLowestElement（）;
int size（）;
效率必须是中心。推荐的方式是什么？想法是受欢迎的。
编辑：经常调用的所有方法。而且它的时间效率很重要。
“效率”过于笼统，特别是面对6种方法？ CPU效率？内存占用？每个函数的调用次数是否相同？平均堆栈有多大？
总的来说，我认为单链表将是一个好主意，假设（似乎是合理的）size和peekMidElement不经常被调用。
其中一种方法是使用数组来实现堆栈。然而，这确实对堆栈中可以存在的元素的数量施加限制（即，阵列的最大大小是有限的）。你也可能需要为阵列分配空间（你可以做一些realloc魔术来重新增加阵列的大小，如果它增长得更多）
数组实现的优点是，你将不得不跟踪将成为堆栈顶部的一个变量。而窥视中间只是数组的索引。
希望这有助于
推送：顶部变量指定的索引到数组，其中顶层元素是......做一个推时...只是下一个单元的值存储顶部后（当然在做了限制检查之后）..然后你可以递增顶层的值
Pop：递减顶端...在（顶+ 1）
PeekMiddle返回值：这将始终是阵列[顶/ 2]
PeekHighest：它将永远是阵列[顶端]
PeekMiddle：它将始终是阵列[0]
尺寸：返回顶部
所有上述操作的是（1）
在附注中，如果您必须遵守堆栈规则 - >“您只能看到堆栈的顶部”，您将如何实现它？ –
@jsshah写道：PeekMiddle：它将始终是数组[0] –
如果知道堆栈大小良好的上限，使用了O一个数组（如另一个答案中概述的）可能是一个合理的事情。所有六个操作都是O（1），并且如果堆栈经常在最大尺寸附近运行，则每个元素的存储量是最佳的。另一方面，如果您不知道堆栈大小的上限，或者堆栈大小通常与上限相比较小，则使用双向链表，如下所述。另一方面，如果您不知道堆栈大小的上限，或堆栈大小通常比上限小，则使用双向链表，如下所述。同样，所有六个操作都是O（1）。如果堆栈的运行接近最小大小，则每个元素的存储空间是最佳的 - 您将不会有大量闲置的阵列空间。请注意，以下显示为“新”和“空闲”的内存分配可以由malloc（）和free（）调用组成，也可以是通过使用可用节点池限制开销的一些常用方法。
让H指向列表头，T指向尾部，M指向中间。 （M可以在每次更改时保持O（1），如下所示。）初始化列表大小s = 0和中间计数m = 0。
为您的操作1-6：
无效推送（E E）：
结交新节点X与E值; ++ S;如果（s == 1）设置H = T = M = X并设置链接，否则{附加X在H;设H = X; （s/2 + 1），则{++ m和设定M = M.next}}。
void pop（E e）：if s < 1 return null or error;如果（s == 0）H = T = M = null，否则如果m>（s/2），则返回H，H = H.next，取消链接并释放H.prev， +1），然后{--m并设置M = M.prev}}。
E peekMidElement（）; [大小（）/ 2）+1]：如果M，还给我否则返回null
ËpeekHighestElement（）：如果H，返回他（或Te）否则返回null
ËpeekLowestElement（）？如果T，返回特否则返回null
INT尺寸（）（或他）：返回小号
我不知道该堆栈的到底是 “高”;你看到它正在成长，还是在成长？无论如何，只要你喜欢修复操作，并更改为像peekHeadElement或peekFirstElement等名称
在这种情况下数组实现将是理想的，但我不确定您的描述仍然可以称为叠加。一些要注意的事项，同时实现它如下：在阵列的权结束
推。如果超出阵列容量，可以分配一个新阵列，复制所有元素并删除以前的分配。所有这些都由大多数语言中的一些基于数组的容器类自动处理。但是，有些方法可以避免大部分复制，同时扩展堆栈的容量，这可能会导致其他操作的效率降低。
如果您维护一个标记下一个插入的索引（即push（E e）），pop（）可以像“ - ;”一样简单地实现。
peekMiddle（）只是（size/2）索引上的元素。我希望你不是在寻找中值。对于peekLowest（），简单的解决方案是维护一堆最小值，即当你将一个值推入堆栈时，如果它是新的最小值，那么也将它推到最小堆栈上。这样，您的最小堆栈中最高的值将成为peekLowest（）的答案。当然，当你从原始堆栈中弹出一个值时，如果它是最小值（由peekLowest（）给出），它也会从最小堆栈中弹出。类似的方法可以用于peekHighest（）。
通过这个简单的实现，您应该能够获得所有操作的O（1）运行时间。推（E e），O（1）是摊销运行时间。
所有方法都要经常调用。而且它的时间效率也很重要。 –
只有时间效率？以数组的形式实现它。 – Malvolio