我有一個堆棧規範，其中---> *可以查看具有最高（或最低或左右）值的對象。 *堆棧上的每個對象都是可比較的。實現給定堆棧的最有效的方法
我會希望儘快
無效推送（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