實現堆棧和隊列操作的時間複雜性

Question

我正在研究數據結構，並對堆棧和隊列的不同實現中的時間複雜性有所懷疑。

對於隊列，是一個元件可以在頭部或尾部進行排隊，動態數組實現給出O（1）時間攤銷用於插入在端部和開頭。鏈表實現給出了O（1）的實現。

對於棧，是一個節點可以在開始時或在列表中，單鏈表和陣列實施將兩者得到O（1）時間複雜度的結束時加入。

我是對的還是我錯過了什麼？

Answer 1

如果您維護下一個插入位置的索引，則插入操作將花費恆定的時間量，因此O（1）是正確的。

但是，如果沒有索引被維護，那麼我們需要搜索插入新元素的正確位置，插入此元素所需的時間會隨着數據結構中元素的數量線性增加，因此插入時間這種情況將是O（n）