Сложность времени для операций в реализации Stack и Queue

Question

Я изучаю структуры данных и имею некоторые сомнения в сложности времени в разных реализациях стеков и очередей.

Для очередей, если элемент может быть поставлен в очередь на голову или хвост, реализация динамического массива дает O (1) время амортизации в конце и начале. Реализация связанного списка дает реализацию O (1).

Для стеков узел мог быть добавлен в начале или в конце списка, отдельно связанный список и реализация массива будут одновременно давать сложность времени O (1).

Я прав, или я чего-то не хватает?

Answer 1

Если вы сохраняете индекс в следующем месте размещения, то операция вставки займет постоянное время, поэтому O (1) будет правильным.

Но если индексы не поддерживаются, нам необходимо найти правильное местоположение для вставки нового элемента, и время, необходимое для его вставки, будет линейно увеличиваться с количеством элементов в структуре данных, поэтому время вставки в этот случай был бы O (n)