как очереди обеспечивают производительность O (1) при взятии / сдаче?

Question

Я полагаю, что постоянное время выполнения операций приема / передачи достигается путем предоставления потребителям и производителям доступа к хвосту / началу очереди, не блокируя друг друга. Как это достигается для очередей в памяти? Меняется ли ответ для длительных очередей (возможно)? Как это решается в системе, которая накладывает ограничение на производителей и потребителей по 1 на каждого? Как насчет того, когда система разрешает параллельный доступ?

Answer 1

Queue использует двусвязный список в качестве структуры данных. Фактически очередь в Java объявлена ​​так:

Queue<SomeClass> q = new LinkedList<>();

LinkedList в Java - это двусвязный список по умолчанию.

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

Теперь как Что касается одновременного доступа, он не должен влиять на временную сложность кода.