Каковы различия между реализацией deque и связного списка (+ vector) для очереди STL (стека OR)?

Question

Мы знаем, что стандартные шаблоны классов deque и list могут использоваться для реализации очереди и + vector для реализации стека. Но в чем разница между этими двумя реализациями, если мы всегда используем одни и те же методы для доступа, а также не можем получить доступ к произвольным элементам, используя at () или [], как мы делаем это с deque (vector).

Answer 1

Адаптеры контейнеров, такие как stack и queue, реализованы с использованием определенного подмножества операций - любой контейнер, который будет использоваться с конкретным адаптером, должен поддерживать все операции, которые требует адаптер.

vector нельзя использовать с контейнерным адаптером queue, поскольку:

Любая последовательность, поддерживающая операции front (), back (), push_back () и pop_front (), может использоваться для создания очереди.

И vector не поддерживает pop_front().

vector, deque или list можно использовать с stack, поскольку все три из этих контейнеров поддерживают операции, которые stack требует:

Любая последовательность, поддерживающая операции back (), push_back () и pop_back (), может использоваться для создания стека.