Коротко про те, що таке стек. Це такий тип даних, в якому вони організовані за принципом LIFO (last in - first out). По русски кажучи, останнім прийшов, першим вийшов. Відмінний приклад для візуалізації це книжкова стопка, верхня книга остання прийшла і, якщо ви не збираєтеся лякати кішку гуркотом, перша пішла.
Реалізація найпростіших структур даних - це відмінний спосіб їх вивчити. Можна прочитати сотню книг про стек, але поки ви його не напишіть самостійно, ви не подружитеся. Я писав реалізацію на мові програмування С ++, використовуючи класи. Два стека - два класи і при великому бажанні можна запакувати їх в окремий файл і підключати до інших проектів.
Дорогі читачі, давайте заводити дружбу зі стеком, поїхали!
Функції роботи зі стеком
push - покласти елемент на вершину стека;
pop - прибрати елемент з вершини;
top - повернути елемент на вершині, не забираючи його звідти;
size - повернути розмір стека.
Реалізація стека на базі масиву
Сенс в тому, що дані зберігаються в звичайному масиві, але доступ до них суворо регулюється нами за допомогою функцій. Величезний недолік в тому, що розмір стека обмежений. Вона вирішується за допомогою розширюваних масивів. Коли місце в масиві закінчується, просто виділяється нова ділянка пам'яті більшого розміру і все копіюється туди. Наскільки мені відомо, в бібліотеці STL стек реалізований саме на розширюваних масивах.
Вихідний код на C ++
Реалізація стека на базі лінійного списку
Лінійний список це дуже популярна структура даних, навіть не дивлячись на те, що не дуже швидка. Дуже часто зустрічається в реалізації системних функцій. Швидкість роботи компенсується гнучкістю. Список використовуємо однозв'язний, реалізуємо мінімальний набір функцій, про які я говорив раніше. Незаперечна перевага перед масивом - максимальний розмір стека не обмежений.
Вихідний код на C ++
тестування продуктивності
Реалізували два стека, гріх з ними не побавитися. Давайте подивимося, який з них працює швидше. І порівняємо швидкість їх роботи зі стеком з STL. а раптом нам вдалося реалізувати швидше?
функція тестування
висновок
Такий розмір стека був обраний експериментально, при більшому розмірі моя система просто падала, весь системний ресурс йшов в тест (підозрюю, що це косяк Убунту). Що ми бачимо? Наш стек на базі масиву всіх уделал, і це не дивно, адже STL-стек розширюваний, і бог знає, скільки ресурсів він витратив на розширення в цьому тесті. Наш стек на масиві виявився найшвидшим, але абсолютно не гнучким. В принципі, якщо розмір вхідних даних заздалегідь відомий і незмінний, можна скористатися і цієї реалізацією.
Тема побита і стара, як світ, але я вніс свою лепту. Чи не пропадати ж коду, вірно? Сподіваюся, що кому небудь стане в нагоді мій досвід, спасибі за увагу!