В чем разница между deque и кольцевым буфером?

Question

Я заранее прошу прощения за отсутствие образования в области структуры данных.

Из моего понимания:

• у фиксированной размерной памяти, которая служит памятью, может быть свой заменено самое старое значение (хотя мы удаляем новые значения)

• в циклическом буфере, который служит памятью, также могут быть заменены его самые старые значения

Что чем разница между двумя понятиями? Это одно и то же? Является ли одно подмножеством другого?

Answer 1

Хороший связанный с этим вопрос будет такой: в чем разница между очередью и связанным списком с указателем хвоста? Очередь добавляется в конец и удаляется спереди, это то же самое, что вы можете сделать со связанным списком с указателем хвоста.

Разница в том, что одним из них является абстракция и один из них - конкретный способ реализации этой абстракции . Существует несколько способов реализации очереди, включая связанный список с указателем хвоста, циклический буфер или даже дерево отображения. Точно так же есть вещи, которые вы можете сделать со связанным списком с указателем хвоста, которые вы бы не сделали для deque, например, вставка больших разделов в список или из него.

В вашем случае, "deque" "это абстракция. Вы можете думать о deque как о «чем-то, что вы можете добавлять и удалять с обоих концов», и это может быть реализовано с помощью кольцевого буфера, или связанного списка, или дерева сплайнов, et c. Циклический буфер является одним из многих способов реализации deque, и есть другие вещи, которые вы можете сделать с циклическим буфером, помимо реализации deque.

Надеюсь, это поможет!

Answer 2

Deque - это абстрактный тип данных , потому что он определяется тем, что вы можете с ним делать; какие операции он поддерживает. Вы можете добавлять и удалять элементы на любом конце очереди.

Круговой буфер - это структура данных , потому что он определяется тем, как он представлен в памяти, и каким должно быть его состояние. манипулировать для выполнения операций deque.

Соотношение между ними состоит в том, что кольцевой буфер является реализацией deque.