Стек — структура данных, которая широко используется в программировании и информатике. В этой статье мы рассмотрим, что такое стек, как он работает и где его можно применять в программировании.
Что такое стек
Это структура данных, которая работает по принципу «последним пришел — первым вышел» (Last In, First Out). Элементы хранятся друг на друге, как стопки книг. Чтобы вам взять книгу, которая лежит в середине, сначала нужно убрать все книги сверху. Последняя книга, которую положили, будет первой, которую возьмут. Так и работают стеки.
Если говорить на языке программирования, базовые команды стеков выглядят так:
🔹 Push (добавить) — кладете элемент на вершину стека.
🔹 Pop (удалить) — убираете элемент с вершины стека.
🔹 Peek/Top (просмотреть верхний элемент) — смотрите, какой элемент находится на вершине стека, но не убираете его.
Пример процесса
- Начинаете с пустого стека.
- Push 1: кладете число 1 в стек.
- Push 2: кладете число 2 в стек.
- Push 3: кладете число 3 в стек.
Стек выглядит так:
text
[3] <- верхний элемент
[2] <- средний элемент
[1] <- нижний элемент
Когда делаете команду Pop (удалить), элемент 3 удаляется, и стек будет выглядеть так:
text
[2] <- верхний элемент
[1] <- нижний элемент
Где используют стеки
Стеки используются во многих областях информатики и программирования, особенно там, где нужно учитывать порядок элементов. Их применяют, чтобы:
🟡 Отслеживать историю браузера
Когда открываете новую веб-страницу в браузере, она добавляется в стек. Когда нажимаете кнопку «Назад», браузер убирает текущую страницу из стека и показывает предыдущую страницу. Это помогает браузеру отслеживать истории страниц, которые вы посетили, и управлять ими.
🟡 Контролировать повторение процесса
Представьте, что вы делаете задачи из списка, который составили на листе бумаги. Каждый раз, когда начинаете новую задачу, вы записываете ее наверху списка. Когда задача выполнена, зачеркиваете ее. Так вы всегда знаете, какая задача сейчас в работе и что делать дальше.
Так работает и со стеком. Когда программа вызывает новую функцию, информация о ней «записывается» в стек. Когда функция заканчивает работу, она «вычеркивается» из стека. Это помогает компьютеру помнить порядок, в котором функции должны выполняться, особенно когда одни функции вызывают другие. Это как аккуратно организованный список дел, но для компьютера.
🟡 Проверять корректность скобок
Вы укладываете в коробку разные пары обуви: сначала кроссовки, потом туфли, а сверху ботинки. Чтобы всё было правильно, нужно сначала достать ботинки, потом туфли, и только потом кроссовки. Если начать доставать не с того конца, то обувь будет без пары.
Стек помогает «запомнить» скобки и убедиться, что каждая открывающая скобка имеет свою закрывающую пару и что они расставлены правильно — как пары обуви.
🟡 Отменять действия
В текстовых редакторах и других программах стек выполняет функцию команды «Отмена». Каждое действие добавляется в стек, и, когда нажимаете «Отмена», последнее действие удаляется из стека и возвращает программу в предыдущее состояние.
Представьте, что пишете текст в редакторе и выполнили следующие действия: написали слово «Привет». Вставили фразу «Как дела?». Удалили слово «Привет». Стек действий будет выглядеть так:
Когда нажимаете Ctrl + Z, то «отменяете» последнее действие в стеке, то есть удаляете его из стека и возвращаете текст к предыдущему состоянию. После первого нажатия Ctrl + Z слово «Привет» возвращается обратно в текст, потому что удаление этого слова было последним действием.
Теперь стек выглядит так:
Если нажать Ctrl + Z еще раз, то отменяется вставка фразы «Как дела?», и стек снова изменится:
Стек помогает управлять последовательностью действий и возвращаться к предыдущим шагам работы. Это очень удобно, когда нужно исправить ошибки или изменить что-то, что было сделано недавно.
Разобраться, где еще используют стеки, можно в онлайн-университете Skypro на курсе «Python-разработчик». Вы научитесь разрабатывать логику программ, создавать базы данных и автоматизировать их работу, использовать готовые библиотеки и работать с Git.
Как реализовать стек
Есть несколько способов реализовать стек. Рассмотрим три основных.
✅ С помощью массива (Array)
Массив — это коробка, куда можно положить несколько предметов, например книги, ручки и карандаши. Каждый предмет занимает свое место внутри коробки и имеет свой номер. Точно так же в массиве программирования можно хранить различные данные — числа, буквы, слова и другие объекты. Каждый элемент данных занимает свое место внутри массива с числовым индексом. Как и в коробке, в массиве можно легко найти любой элемент и получить доступ к любому элементу по его индексу и положению внутри. Например, книга 1, ручка 2, карандаш 3 и так далее. Чтобы получить ручку, просто пишете массив[2], и программа «выдаст» ручку.
В программировании это выглядит так:
// Создаем пустой стек
let stack = [];// Добавляем элементы в стек (push)
stack.push(1);
stack.push(2);
stack.push(3);// Теперь стек выглядит так: [1, 2, 3]
// Удаляем элемент из стека (pop)
let removedElement = stack.pop(); // removedElement = 3// Теперь стек выглядит так: [1, 2]
// Просматриваем верхний элемент (peek)
let topElement = stack[stack.length — 1]; // topElement = 2
- Создаем пустой массив stack.
- Когда добавляем stack.push(element), новый элемент попадает в конец массива, как новая книга в стопку.
- Когда добавляем stack.pop(), верхний элемент стека удаляется из массива и снова возвращается. Это позволяет использовать или проверить значение элемента перед тем, как удалить его из стека. Например, если хотим выполнить какое-то действие с верхним элементом стека перед тем, как его удалить, команда pop() позволяет это сделать.
- Когда вызываем stack[stack.length — 1], мы получаем доступ к верхнему элементу 2 в массиве, не удаляя его.
✅ С помощью связанного списка (Linked List)
Вместо массива можно реализовать стек с помощью связанного списка. Это как карточки с названием городов. В связанном списке у каждой карточки (узла) есть значение и ссылка на следующую карточку. Если это последняя карточка, то ссылка указывает на «ничего» или null.
Такой способ позволяет легко добавлять новые карточки в любое место списка или удалять старые, просто изменяя ссылки между узлами. Это очень гибкая структура, которую используют в программировании для эффективного управления данными.
Выглядит это так:
// Определяем элементы списка
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}// Определяем элемент стека
class Stack {
constructor() {
this.top = null; // Верхний элемент стека
}// Добавляем элемент в стек (push)
push(value) {
let newNode = new Node(value);
newNode.next = this.top;
this.top = newNode;
}// Удаляем элемент из стека (pop)
pop() {
if (!this.top) return null; // Если стек пустой, возвращаем null
let removedValue = this.top.value;
this.top = this.top.next;
return removedValue;
}// Просматриваем верхний элемент (peek)
peek() {
if (!this.top) return null; // Если стек пустой, возвращаем null
return this.top.value;
}
}
- constructor(): создает новый стек, добавляет верхний элемент (top) в null.
- push(value): добавляет новый узел с заданным значением (value) в начало связанного списка. Новый узел становится верхним элементом стека.
- pop(): удаляет верхний элемент стека и возвращает его значение. Если стек пустой, возвращает null.
- peek(): возвращает значение верхнего элемента стека, не удаляя его. Если стек пустой, возвращает null.
✅ С помощью объекта (Object)
Объект — это набор данных, которые соединены в пару «ключ — значение». Это как записная книжка, где ключ — название строки, например имя, фамилия, год рождения. Значение — данные, которые связаны с ключом: Иван Иванов, 1985 года рождения. Объекты организовывают и хранят данные в структурированном виде — это делает программы более понятными и управляемыми.
// Определяем объект стека
let stack = {
items: [], // Массив для хранения элементов// Добавляем элемент в стек (push)
push(element) {
this.items.push(element);
},// Удаляем элемент из стека (pop)
pop() {
if (this.items.length === 0) return null; // Если стек пустой, возвращаем null
return this.items.pop();
},// Просматриваем верхний элемент (peek)
peek() {
return this.items[this.items.length — 1];
}
};
- Создаем объект под названием stack, который представляет стек. Внутри объекта есть свойство items — это массив для хранения элементов стека.
- Когда вызываем метод push(element), добавляем новый элемент в конец массива items.
- Когда вызываем метод pop(), извлекаем и возвращаем последний элемент, добавленный в массив items. Если массив пустой, возвращаем null.
- Когда вызываем метод peek(), возвращаем значение последнего элемента в массиве items, не удаляя его.
Основную часть курса «Python-разработчик» составляет практика. Все проекты — это реальные задания от работодателей. Оттачивать навыки вы будете на основе того, что нужно будет делать потом в реальной работе. После курса у вас будет портфолио из девяти проектов и одной большой дипломной работы. Этого хватит, чтобы устроиться на работу.
Для чего нужен стек вызова
Это структура данных в программировании, которая помогает отслеживать, в каком порядке функции отображаются в программе. Представьте, что убираетесь в комнате, и вам нужно выполнить несколько дел. Начинаете с одного дела, потом переключаетесь на другое, а потом на третье. Когда заканчиваете последнее дело, возвращаетесь к предыдущему — и так далее, пока не выполните все дела.
Стек вызова в программировании работает примерно так же. Когда вызываете одну функцию из другой, эта новая функция «помещается» на «верх» стека. Когда функция заканчивает работу, она «снимается» со стека, и управление возвращается к предыдущей функции.
- Вызывается функция main().
- Внутри main() вызывается функция square(5).
- Внутри square(5) вызывается функция multiply(5, 5).
- multiply(5, 5) выполняется и возвращает результат.
- square(5) получает результат от multiply(5, 5) и возвращает его.
- main() получает результат от square(5) и выводит его в консоль.
Так стек вызовов отслеживает, в каком порядке были вызваны функции, и дает правильное возвращение к предыдущим вызовам. Это помогает программе работать в правильном порядке и исправлять ошибки, если они возникают.
Стек данных похож на стек вызова. Это одна большая переменная, которая похожа на список, где данные «складываются» один на другой. Новые данные добавляются на вершину стека, а извлекаются всегда с вершины.
Почему стек переполнен и как это исправить
Это случается, если в программе много вызовов функций или много внутренних данных. Представьте стопку тарелок. Если класть на нее всё больше и больше тарелок, в какой-то момент стопка просто упадет, потому что для нее не хватит места или она станет слишком тяжелой. То же самое происходит со стеком в программе: когда вызываете одну функцию из другой, новая функция «кладется» на стек вызова. Если продолжаете вызывать больше функций, стек вызова «переполняется»: он не может вместить все эти функции.
Когда такое происходит, программа выдает ошибку Stack Overflow — значит, стек больше не может вместить все необходимые данные, и программа не будет продолжать работу. Чтобы этого избежать, нужно следить, чтобы в программе не было много повторяющихся функций или большого количества внутренних данных.
Главное, что нужно знать про стеки
🟢 Стек — простая и эффективная структура данных, которую используют в различных областях программирования. Он помогает организовать данные в удобном порядке и управлять ими для выполнения задач.
🟢 Выбор способа реализации зависит от конкретных требований и условий задачи. Массив проще и требует меньше памяти, но ограничен размером. Список гибок, но требует больше памяти из-за хранения ссылок на следующие элементы.
🟢 Стеки вызова и стеки данных тесно связаны и работают вместе для правильной работы программы.
Добавить комментарий