Что такое стеки и очереди, непрерывные или связанные структуры данных?
Я на самом деле читаю книгу skiena "Руководство по проектированию Algothm", в которой говорится, что существует два типа структур данных:
• Непрерывно размещенные структуры состоят из отдельных блоков памяти и включать массивы, матрицы, кучи и хэш-таблицы.
• Связанные структуры данных состоят из отдельных фрагментов с привязкой к памяти. вместе указателями и включают списки, деревья и списки смежности графов.
Но я не видел стопки и очереди. смежные или связанные?
Ответы 1
Вы можете реализовать их обоими способами. Стеки и очереди - это абстрактные типы данных, а не структуры данных, поэтому они предоставляют только интерфейс, а не реализацию. Например, вы можете реализовать стек, используя связанный список или массив. Вы не знаете базовую реализацию при использовании стека, вместо этого вы знаете, какие данные он может хранить, и различные средства доступа.
Более конкретно, рассмотрим стек. Вы можете представить его с помощью массива, который может использовать стратегию удвоения по мере его увеличения. Вы можете взять целочисленное значение, представляющее индекс, до которого поднимается стек, и затем вы продолжите перемещать этот целочисленный указатель вперед. Точно так же для связанных списков вы можете выбрать, чтобы связанный список представлял стек, и у вас была бы обратная ссылка, чтобы вы могли всплывать.
Очереди и стеки также могут называться абстрактные структуры данных, поэтому я бы не стал утверждать, что очередь или стек не являются структурой данных, они не так четко определены.