У чому різниця між масивом і стеком?

Згідно з Вікіпедією, стек :

- це останній, перший (LIFO) абстрактний тип даних і лінійна структура даних.

Хоча масив :

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

Наскільки я розумію, вони досить схожі. Отже, які основні відмінності? Якщо вони не збігаються, що може зробити масив, який не може зробити стек, і навпаки?

9
Різниця полягає в тому, як вони використовуються. Обидва містять n частини інформації, одна з яких обмежує доступ до останнього вставленого елемента, тому що, можливо, це те, про що ви маєте справу, перш ніж перейти до наступного.
додано Автор Justin Poliey, джерело
-1 Ви відповідали на власний запит. Що знову ви запитуєте?
додано Автор Mike McAllister, джерело
Я тільки що прочитав метапрограмістів і зрозумів, чому ви задали це питання, що не викликає сумніву: це конкурс. Я серйозно сумніваюся, що Ви не зрозуміли статтю Вікіпедії. Ганьба тобі :/
додано Автор Mike McAllister, джерело
@Dynamic Вибачте, я не вірю вам:/Це дуже основний матеріал, який ви просите (і відповідайте самостійно). Але я відкину це питання.
додано Автор Mike McAllister, джерело
Як ваше відповідь не відповідає тому, що ви знайшли у Вікіпедії? Ви можете отримати доступ до елементів масиву в будь-якому порядку; доступ до стека в порядку LIFO.
додано Автор Caleb, джерело
@Caleb Просто тому, що ви щось читаєте, це не означає, що ви розумієте цю концепцію. На мій погляд, я цього не розумів повністю, поки не запитав.
додано Автор Dynamic, джерело
@AndresF. Я не можу зрозуміти, що це означає ... Якщо ви могли б подивитися на статтю Вікіпедії і зрозуміти, що вони говорять в перший раз, світ буде ідеальним.
додано Автор Dynamic, джерело
@AndresF. Неправда. Я насправді не розумів і хотів роз'яснення ... Не кладіть слова в мої рот.
додано Автор Dynamic, джерело

8 Відповіді

Ну, звичайно, можна реалізувати стек з масивом. Різниця в доступі. У масиві є список елементів, і ви можете отримати доступ до будь-якого з них у будь-який час. (Подумайте про купу дерев'яних блоків, розкладених поспіль).

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

45
додано
Ви повинні смоктати в Jenga.
додано Автор wilhelmtell, джерело
@Mason, я знаю. Це був жарт.
додано Автор wilhelmtell, джерело
стеки, безумовно, реалізовані з довільним доступом
додано Автор Tom Walker, джерело
@DisgruntledGoat: Я насправді дуже добре. Але в Jenga є більше одного блоку на вертикальний шар, тоді як в аналогії, яку я намагаюся намалювати тут, є тільки один.
додано Автор JanC, джерело
Ви скажете "в стеку, немає операції з випадковим доступом", але я не згоден, і додаду більше подробиць у свою відповідь.
додано Автор John L., джерело
дерев'яні блоки - приємна аналогія
додано Автор Jesse Black, джерело

У чистому стеку єдиними дозволеними операціями є Push , Pop і Peek , але з практичної точки зору це не зовсім так. Вірніше, операція Peek часто дозволяє переглядати будь-яку позицію у стеку, але уловлює те, що він по відношенню до одного кінця стека.

Таким чином, як казали інші, масив є випадковим доступом, а все посилається на початок масиву .

У стеку можна додавати/видаляти лише у робочому кінці стека, але ви все ще маєте довільний доступ , але він посилається на робочий кінець . Це принципова різниця.

Наприклад, коли ви передаєте параметри в стек функції, абонент не повинен вимикати параметри, щоб дивитися на них. Він просто виштовхує локальні змінні в стек і посилається на всі локальні змінні і параметри на основі зміщення від покажчика стека. Якщо ви використовували тільки масив, то як би викликаний знає, де шукати його параметри? Коли виклик завершено, він вискакує свої локальні змінні, штовхає повернене значення, повертає управління виклику, а абонент виводить повернене значення (якщо воно є), а потім виводить параметри зі стека. Краса в тому, що вона працює незалежно від того, наскільки ви вкладені у ваші виклики функцій (якщо ви не вичерпаєте простору стека).

Це один конкретний варіант використання/реалізації, але він ілюструє різницю: масив завжди посилається з початку, але стеки завжди посилаються на деякі робочі кінцеві позиції.

Однією з можливих реалізацій стека є масив плюс індекс для запам'ятовування місця роботи.

5
додано

Я думаю, що найбільша плутанина, що відбувається тут, - це реалізація порівняно з основними структурами даних.

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

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

Ви можете створити стек з безлічі різних типів структур даних: масиви (з деяким максимальним розміром), динамічні масиви (можуть зростати, якщо їх немає) або пов'язані списки. Особисто я відчуваю, що пов'язаний список представляє обмеження стека краще, як ви повинні вкласти трохи зусиль, щоб побачити речі поза першим елементом, і це дуже легко додати на фронт і видалити з фронту.

Таким чином, ви можете використовувати масив, щоб зробити стек, але вони не є еквівалентними

4
додано

Їхні обов'язки різні:

  • Стек повинен мати змогу розміщувати елементи зі стека в елементах стека та натискати їх, тому чому він зазвичай має методи Pop() і Push()

  • Відповідальність Array полягає в тому, щоб отримати/встановити елемент за вказаним індексом

3
додано

Ви можете отримати елемент з будь-якого індексу масиву A.

У стеку можна отримати елемент у середині стека A, використовуючи інший стек: B.

Ви продовжуєте брати верхню позицію з А і розміщувати її в B, доки ви не знайдете потрібний пункт A, після чого ви кладете елементи з B на вершину стека A.

Отже, для даних, які вимагають можливості отримання довільного індексу, стек важче працювати.

У ситуації, коли ви хочете "останнього в, перший вихід" поведінку, стек дасть вам менше накладні витрати, ніж масив.

3
додано

Масив з точки зору програмістів, зафіксований на місці і розмірі, ви знаєте, де ви знаходитеся в ньому і де все це. Ви маєте доступ до всього цього.

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

Якщо ви хочете потрапити в апаратну сторону, то це, звичайно, специфічний для процесора, але, як правило, масив базується на відомій початковій точці/адресі, розмір якого відомий компілятору/програмісту, і в нього обчислюються адреси, іноді використовуючи адресат зміщення регістра (завантажувати значення з адреси, визначеного цим значенням базового регістра плюс це значення зміщення регістра, аналогічно, коли він компілюється, може бути негайним зміщенням, не обов'язково заснованим на реєстрації, залежить від процесора, звичайно), який в зборі дуже багато нагадує доступ до масиву в коді високого рівня. Подібно до стека, якщо доступно, ви можете використовувати регістр або негайне зсув, часто, хоча він використовує спеціальний реєстр, або сам стек-покажчик, або регістр, зарезервований компілятором/програмістом для використання для доступу до стекового кадру. функції. А для деяких процесорів використовуються спеціальні функції доступу до стеків та/або необхідні для доступу до стека. У вас є поштовх і поп-інструкції, але вони не використовуються так часто, як ви думаєте, і дійсно не стосуються цього питання. Для деяких процесорів push і pop є псевдонімами для інструкцій, які можна використовувати з будь-яким реєстром, в будь-якому місці, а не тільки з покажчиком стека на стеку, додатково видаляючи push і pop з пов'язаних з цим питанням.

0
додано

Доступ до даних в масиві можна отримати за допомогою ключа або індексу. Доступ до даних у стеку можна отримати, коли він вискочив з вершини стека. Це означає, що доступ до даних з масиву простий, якщо ви знаєте його індекс. Доступ до даних зі стека означає, що вам доведеться зберігати елементи, доки не знайдете той, який ви шукали, а це означає, що доступ до даних може тривати довше.

0
додано

Я б не пішов так далеко, щоб сказати, що вони "дуже схожі".

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

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

Так що я міг би використовувати масив як стек (хоча я б не хотів), але я не можу використовувати стек в якості масиву (якщо я не працюю дуже важко на це).

0
додано
У сфері «структур для зберігання колекцій об'єктів» я б не сказав, що вони дуже схожі. У сфері концепцій програмування, я б сказав, що вони досить схожі. В області речей взагалі, я б сказав, що вони майже ідентичні.
додано Автор Alexander Taran, джерело