В чем разница между массивом и стеком?

Согласно Википедии, стек :

является абстрактным типом данных «последний вошел - первым вышел» (LIFO) и линейной структурой данных.

Пока массив :

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

Насколько я понимаю, они довольно похожи. Итак, каковы основные различия? Если они не одинаковы, что массив может сделать, чего не может стек, и наоборот?

Ну, вы, конечно, можете реализовать стек с массивом. Разница в доступе. В массиве у вас есть список элементов, и вы можете получить доступ к любому из них в любое время. (Подумайте о куче деревянных блоков, выложенных в ряд.)

Но в стеке нет операции произвольного доступа; есть только Push, Peekи Pop, все из которых имеют дело исключительно с элементом на вершине стека. (Подумайте о деревянных блоках, сложенных вертикально. Вы ничего не можете коснуться под вершиной башни, иначе она упадет.)

В чистом стеке, только допустимые операции Push, Popи , Peekно с практической точки зрения, это не совсем верно. Или, скорее, Peekоперация часто позволяет вам просматривать любую позицию в стеке, но выгода заключается в том, что она относится к одному концу стека.

Итак, как уже говорили другие, массив является произвольным доступом и все ссылается на начало массива .

В стеке вы можете добавлять / удалять только на рабочем конце стека, но у вас все еще есть чтение с произвольным доступом, но оно относится к рабочему концу . Это принципиальная разница.

Например, когда вы передаете параметры в стеке функции, вызываемый объект не должен извлекать параметры, чтобы просмотреть их. Он просто помещает локальные переменные в стек и ссылается на все локальные переменные и параметры на основе смещения от указателя стека. Если бы вы использовали только массив, то как бы вызываемый узнал, где искать его параметры? Когда вызываемый объект готов, он выталкивает свои локальные переменные, отправляет возвращаемое значение, возвращает элемент управления вызывающей стороне, и вызывающая сторона извлекает возвращаемое значение (если оно есть), а затем выталкивает параметры из стека. Прелесть в том, что он работает независимо от того, насколько далеко вы вложены в вызовы функций (при условии, что у вас не осталось свободного места в стеке).

Это одно конкретное использование / реализация, но оно иллюстрирует разницу: на массив всегда ссылаются с начала, а на стеки всегда ссылаются с некоторой рабочей конечной позиции.

Одной из возможных реализаций стека является массив плюс индекс для запоминания рабочего конца.

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

В большинстве (более базовых языках) массив представляет собой набор элементов фиксированной длины, к которым вы можете обращаться в любой момент времени. Тот факт, что у вас есть куча таких элементов, ничего не говорит вам о том, как он должен использоваться (и, честно говоря, компьютер не будет знать / заботиться о том, как вы его используете, если вы не нарушаете его).

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

Вы можете сделать стек из множества различных типов структур данных: массивы (с некоторым максимальным размером), динамические массивы (могут расти, когда не хватает места) или связанные списки. Лично я считаю, что связанный список наилучшим образом представляет ограничения стека, так как вам нужно приложить немного усилий, чтобы увидеть вещи, выходящие за рамки первого элемента, и их очень легко добавить вперед и удалить с фронта.

Таким образом, вы можете использовать массив, чтобы сделать стек, но они не эквивалентны

Их обязанности разные:

• Стек должен иметь возможность вставлять элементы в стек и выталкивать элементы из стека, поэтому он обычно имеет методы Pop()иPush()

• Обязанность массива - получить / установить элемент по указанному индексу

Вы можете извлечь элемент из любого индекса массива A \.

С помощью стека вы можете получить элемент в середине стека A, используя другой стек: B.

Вы продолжаете брать верхний предмет из A и помещать его в B, пока не доберетесь до нужного предмета A, затем вы помещаете предметы из B обратно на верх стопки A.

Таким образом, для данных, для которых требуется возможность получения произвольного индекса, с стеком работать сложнее.

В ситуации, когда вам нужно поведение «первым пришел - первым обслужен», стек даст вам меньше накладных расходов, чем массив.

Я бы не сказал, что они «очень похожи».

Массив используется для хранения вещей, к которым впоследствии будет осуществляться доступ последовательно или через индекс. Структура данных не предполагает какого-либо метода доступа (FIFO, LIFO, FILO и т. Д.), Но при желании его можно использовать таким образом.

Стек - это способ отслеживать вещи по мере их создания. Метод доступа подразумевается / требуется в зависимости от типа созданного стека. Стек кадров был бы примером LIFO. Отказ от ответственности - возможно, я смешиваю свою таксономию структуры данных, и стек действительно может разрешать только LIFO. В противном случае это был бы другой тип очереди.

Таким образом, я мог бы использовать массив в качестве стека (хотя я бы не хотел), но я не могу использовать стек в качестве массива (если я не очень усердно над этим работаю).

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

Массив с точки зрения программистов, фиксирован по месту и размеру, вы знаете, где вы находитесь и где все это находится. У вас есть доступ ко всему этому.

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

Если вы хотите перейти к аппаратной части, то это, конечно, зависит от процессора, но обычно массив основан на известной начальной точке / адресе, размер известен компилятору / программисту, и адреса вычисляются в нем, иногда используется адресация смещения регистра (загрузка значения с адреса, определенного этим базовым значением регистра плюс это значение регистра смещения, также при компиляции это может быть непосредственное смещение, необязательно основанное на регистре, зависит, конечно, от процессора), которое в сборке очень сильно напоминает доступ к массиву в коде высокого уровня. Аналогично со стеком, если он доступен, вы можете использовать регистр или немедленную адресацию смещения, часто хотя он использует специальный регистр, либо сам указатель стека, либо регистр, зарезервированный компилятором / программистом, который будет использоваться для доступа к кадру стека для этого функция. А для некоторых процессоров используются специальные функции доступа к стеку, и / или они необходимы для доступа к стеку. У вас есть инструкции push и pop, но они используются не так часто, как вы думаете, и на самом деле не применимы к этому вопросу. Для некоторых процессоров push и pop являются псевдонимами для инструкций, которые можно использовать с любым регистром, где угодно, а не только с указателем стека в стеке, что еще больше убирает связь push и pop с этим вопросом.