Стеки и очереди - это линейная структура данных или нелинейная структура данных?

Question

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

В википедии задано, что очередь представляет собой линейную структуру данных. Я тоже считаю, что они линейны, так как нет отклонений, как в случае с деревьями. Однако при попытке выполнить онлайн-тестирование было отменено сообщение о том, что они нелинейные.

Пожалуйста, ответьте мне точно, что верно и почему.

Answer 1

Что вы подразумеваете под "линейным" здесь? Они, конечно, не круглые и не сферические.

Кроме того, ответ будет зависеть от того, о каких стеках / очередях вы говорите.

---

Вы имели в виду "смежные"?

Если вы имеете в виду std::stack и std::queue (затем удалите тег «C» из вашего вопроса, пожалуйста), то это все равно зависит. Они оба контейнерные адаптеры , что означает, что базовая реализация может быть указана в качестве параметра шаблона. По умолчанию std::stack и std::queue построены на std::deque & mdash; который не гарантированно является смежным.

Для некоторых других произвольных спецификаций контейнеров это будет зависеть.

---

Вы имели в виду "последовательность"?

Стандарт C ++ имеет три контейнера последовательности : std::vector, std::list и std::deque. Это означает, что std::stack / std::queue не является контейнером последовательности сам по себе, но его реализация может быть, в зависимости от того, какой вы выберете.

---

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

Answer 2

Это зависит! Очередь / стек может быть линейной, как в случае FIFO и LIFO, однако она может быть нелинейной, например, в случае очереди с приоритетами, где обслуживание элемента зависит от указанного вами параметра!
Таким образом, оба могут быть правдой! Все зависит от того, как вы реализуете используемую структуру данных!
Однако, скорее всего, стек считается линейным, очередь может быть как связанной, так и связанные списки и деревья нелинейны.

Answer 3

Линейная структура данных

не имеет ничего общего с деталями реализации или моделью памяти.Это просто означает, что все его элементы имеют свои предшествующие или последующие, исключая голову и конец.Не как дерево или граг.

Линейная структура данных включает в себя очередь, стек.

Если кто-то неправильно использует вкладыш в качестве «Непрерывной памяти», он / она ошибается.

Answer 4

Либо может быть правдой.Слова «стек» и «очередь» определяют только разрешенные шаблоны доступа, но не детали реализации.Например, вы можете реализовать как связанный список.

Answer 5

Для меня очередь или стек - это только спецификация.Реализация может варьироваться.