Стек что такое

О стеке простыми словами — для студентов и просто начинающих

Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»

Теория

На Википедии определение стека звучит так:

Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

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

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

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

Итак, из чего же состоит стек.

Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.

На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.

С теорией закончили, перейдем к практике.

Практика

Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»

Код на C++

struct comp < //Структура с названием comp(от слова component) int Data; //Какие-то данные(могут быть любыми, к примеру можно написать int key; char Data; так-же можно добавить еще какие-либо данные) comp *next;//Указатель типа comp на следующий элемент >; 

Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.

После того как у нас задана «Ячейка», перейдем к созданию функций.

Функции

Функция создания «Стека»/добавления элемента в «Стек»

При добавлении элемента у нас возникнет две ситуации:

• Стек пуст, и нужно создать его
• Стек уже есть и нужно лишь добавить в него новый элемент

Код на C++

void s_push(comp **top, int D) < //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q типа структуры comp. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем необходимое число в Data элемента if (top == NULL) < //Если вершины нет, то есть стек пустой *top = q; //вершиной стека будет новый элемент >else //если стек не пустой < q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Обозначаем, что вершиной теперь является новый элемент > > 

Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.

-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.

Функция удаления элемента из «Стека» по данным

Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.

Здесь могут быть такие варианты:

• Ячейка, которую нам нужно удалить является вершиной стека
• Ячейка, которую нам нужно удалить находится в конце, либо между двумя ячейками

Код на C++

void s_delete_key(comp **top, int N) Data == N) next;//передвигаем вершину на следующий элемент free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чтение памяти невозможно" или числа "-2738568384" или другие, в зависимости от компилятора. q->next = NULL; > else//если элемент последний или находится между двумя другими элементами < prev->next = q->next;//Проводим связь от предыдущего элемента к следующему free(q);//очищаем ячейку q->Data = NULL;//обнуляем переменные q->next = NULL; > >// если Data элемента НЕ равна числу, которое нам нужно удалить prev = q; //запоминаем текущую ячейку как предыдущую q = q->next;//перемещаем указатель q на следующий элемент > > 

Указатель q в данном случае играет такую же роль, что и указатель в блокноте, он бегает по всему стеку, пока не станет равным NULL(while(q != NULL)), другими словами, пока стек не закончится.

Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);

Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).

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

Функция вывода данных стека на экран

Самая простая функция:

Код на C++

void s_print(comp *top) < //принимает указатель на вершину стека comp *q = top; //устанавливаем q на вершину while (q) < //пока q не пустой (while(q) эквивалентно while(q != NULL)) printf_s("%i", q->Data);//выводим на экран данные ячейки стека q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку) > > 

Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.

Главная функция

Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:

Код на C++

void main() < comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL //Дальше начинаем добавлять цифры от 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //после выполнения функций в стеке у нас будет 54321 s_print(top);//выводим s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321 printf_s("\n");//переводим на новую строку s_print(top);//выводим system("pause");//ставим на паузу >

Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.

Заключение

Полный код программы:

Код на C++

#include ; #include ; struct comp < //Структура с именем comp int Data; //Кикие то данные(могут быть любими, к примеру можно написать int key; char Data; или добавить еще какие то данные) comp *next;//Указатель типа comp на следующий эелемент >; void s_push(comp **top, int D) < //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q, который приравниваем к вершине стека. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем D в Data элемента if (top == NULL) < //Если вершины нет, тоесть стек пустой *top = q; //вершиной стека будет новый элемент >else //если стек не пустой < q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Пишем, что вершиной теперь является новый элемент > > void s_delete_key(comp **top, int N) Data == N) next;//передвигаем вершину на следующий элемент free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чение памяти невозможно" или числа "-2738568384" или других, в зависимости от компилятора. q->next = NULL; > else//если элемент последний или находится между двумя другими элементами < prev->next = q->next;//Проводим связь от предыдущего элемента к следующему free(q);//очищаем ячейку q->Data = NULL;//обнуляем переменные q->next = NULL; > >// если Data элемента НЕ равна числу, которое нам нужно удалить prev = q; //запоминаем текущую ячейку как предыдущую q = q->next;//перемещаем указатель q на следующий элемент > > void s_print(comp *top) < //принимает указатель на вершину стека comp *q = top; //устанавливаем q на вершину while (q) < //пока q не пустой (while(q) эквивалентно while(q != NULL)) printf_s("%i", q->Data);//выводим на экран данные ячейки стека q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку) > > void main() < comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL //Дальше начинаем добавлять цифры от 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //после выполнения функций в стеке у нас будет 54321 s_print(top);//выводим s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321 printf_s("\n");//переводим на новую строку s_print(top);//выводим system("pause");//ставим на паузу >

54321
5321

Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке

В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.

Что такое стек

Стек — это вид структуры данных, в котором элементы упорядочены и добавление или удаление элементов происходит с верхней части стека — по принципу «Последним пришел — первым ушел» (LIFO). Реализовать стек можно, например, С, JavaScript, С++, Java, Python, Lisp или C#.

Как работает стек

Визуально это похоже на стопку тарелок. Первую помытую взять сложно, как и находящуюся где-то внутри, проще начать с последней.

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

Четыре основные операции над стеком:

• push — добавление элемента
• pop — удаление верхнего элемента
• isEmpty — проверка стека на наличие в нем элементов
• peek — возвращение последнего элемента, не удаляя его.

Разновидности стеков

Существует несколько видов стека:

• Стек вызовов: область памяти, в которой хранится информация о точках перехода между элементами программного кода. Например: скрипт вызывает функцию, интерпретатор записывает ее в стек вызовов. Любые функции, вызванные этой функцией, добавляются в стек и выполняются по очереди. Когда основная функция отработает, интерпретатор извлечет ее из стека вызовов и продолжит выполнять код с того места, где он остановился ранее.
• Стек на основе массива: в этом типе стека элементы хранятся в массиве фиксированного размера, и доступ к ним осуществляется по индексу. Главным недостатком является ограниченность размера массива, что может привести к проблемам с добавлением новых элементов, если стек заполнен. Также этот тип стека может быть неэффективным, если требуется частое добавление и удаление элементов.
• Стек на основе связного списка: в нем элементы хранятся в связном списке, где каждый элемент содержит указатель на следующий элемент. Этот тип стека позволяет эффективно добавлять и удалять элементы, но может быть менее эффективным при доступе к элементам по индексу. Одним из преимуществ стека на основе связного списка является его динамичность — размер стека может быть изменен в любой момент времени.
• Стек на основе двухсторонней очереди (Deque): в этом случае элементы хранятся в двухсторонней очереди, где элементы могут быть добавлены или удалены с обоих концов.
• Стек на основе дерева: здесь элементы хранятся в дереве, где каждый узел содержит указатель на родительский узел. Этот тип стека может быть полезен для решения задач, связанных с деревьями, таких как обход дерева в глубину.
• Стек на основе кучи (Heap): в этом виде стека элементы хранятся в куче, где каждый элемент имеет приоритет. Этот тип стека может быть полезен для решения задач, связанных с приоритетами, таких как поиск минимального или максимального элемента.

Переполнение стека

Переполнение стека — это ситуация, когда стек заполняется элементами, превышающими его максимальный размер, установленный при создании стека. Когда стек переполняется, он не может больше хранить элементы, и любая попытка добавления нового элемента приведет к ошибке.

Причины переполнения стека

Рекурсия: если функция вызывает саму себя слишком много раз, то каждый новый вызов функции добавляет новый элемент в стек. Если глубина рекурсии слишком большая, то стек может переполниться.

Бесконечный цикл: если в цикле добавляются новые элементы в стек, то если цикл не останавливается, то стек может быстро заполниться.

Неправильно написанный код: некоторые ошибки в коде могут привести к тому, что стек будет заполняться слишком быстро. Например, если функция добавляет элементы в стек, но не удаляет их, то стек будет быстро заполнен.

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

Опасности переполнения стека

• Падение программы: переполнение стека может привести к аварийному завершению программы, что может привести к потере данных или другим негативным последствиям.
• Потеря данных: если стек переполнен, то данные, которые не помещаются в стек, могут быть потеряны.
• Уязвимость безопасности: переполнение стека может привести к уязвимостям безопасности, так как злоумышленник может использовать переполнение стека для выполнения вредоносного кода или других опасных действий.
• Непредсказуемое поведение программы: переполнение стека иногда запускает непредсказуемое поведение программы, включая зависание программы или ошибки в работе.

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

Реализация стека

Стек может быть выполнен с помощью связанного списка, массива фиксированной длины или динамического массива.

Пример стека на массиве в JavaScript

const arr = []; //Добавляем элементы в массив arr.push("Один"); console.log(arr); // выведет ["Один"] arr.push('Два'); console.log(); // выведет ["Один", "Два"] //Удаляем элемент arr.pop(); console.log(arr); // выведет ["Один"] //Добавим еще один элемент arr.push("Сосиска"); //Отобразим последний элемент, не удаляя его console.log(arr.peek()); // выведет Сосиска //Проверим, пуст ли наш стек console.log(arr.isEmpty()); // выведет false

Пример стека на связанном списке в Python

class Node: def __init__(self, data=None): self.data = data self.next = None class LinkedStack: def __init__(self): self.top = None # Проверим, пуст ли наш стек def is_empty(self): return self.top is None # Добавляем элемент в стек def push(self, item): new_node = Node(item) new_node.next = self.top self.top = new_node # Удаляем элемент из вершины стека и возвращаем его def pop(self): if self.is_empty(): raise Exception("Stack is empty") item = self.top.data self.top = self.top.next return item # Отобразим последний элемент, не удаляя его def peek(self): if self.is_empty(): raise Exception("Stack is empty") return self.top.data

Класс Node представляет узел связанного списка, а класс LinkedStack использует узлы, чтобы создать стек. Каждый узел содержит данные (data) и ссылку на следующий узел (next). При вызове метода push, создается новый узел с переданным элементом, и ссылка на этот узел устанавливается в вершину стека (top). При вызове метода pop, элемент извлекается из вершины стека, и вершина обновляется, чтобы указывать на следующий узел в списке.

Софья Пирогова

автор статей / копирайтер

Вам может также понравиться.

Курс Основы JAVASCRIPT онлайн

22 нояб. 2023 г.

Для чего и кому нужны Big Data

7 нояб. 2023 г.

Значение слова «стек»

Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека

• Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

В цифровом вычислительном комплексе стек называется магазином — по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).

В 1946 Алан Тьюринг ввёл понятие стека. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга.

• СТЕК [тэ], а, м. [англ. stick] (спорт.). Твердый, эластичный хлыст, употр. при верховой езде.
• стёк, -ся, екла́, -сь. Прош. вр. отстечь, -ся.

Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека

стек I

стек II

1. комп. структура данных, отличающаяся возможностью доступа исключительно к своему последнему элементу ◆ Стек вызовов 2. техн. комп. группа сетевых устройств, протоколов, каких-либо технических средств, логически интегрированных в единую систему ◆ Стек коммутаторов логически представляет собой одно устройство, которое управляется внутри стека главным коммутатором. ◆ Для совместной работы устройств, занимающихся передачей аудио- и видеотрафика, применяют несколько схем работы, которые используют разные рекомендации и стеки протоколов. «Протоколы, используемые в IP-телефонии», 2004 г. // «Информационные технологии» (цитата из НКРЯ) ◆ Отметим, что при помещении BP в стек относительные смещения параметров увеличатся на 2, поскольку стек теперь увеличится на два. Алексей Калугин 3. игр. количество денег или фишек, которым игрок располагает за столом для игры

Фразеологизмы и устойчивые сочетания

• короткий стек
• помещать в стек
• стек данных
• стек протоколов
• стек технологий

Стек

Стек — одна из основ организации и хранения данных. При этом она напрямую не взаимодействует ни с одним из языков программирования. Стек — это способ формирования структуры данных, а структура — это вариант хранения информации: списков, «веток», схем, множеств, таблиц.

«IT-специалист с нуля» наш лучший курс для старта в IT

Как работает стек

Главная особенность — в последовательном способе хранения. Элементы необходимо брать и использовать только по очереди. В рамках стека работает линейная связь: данные следуют друг за другом в строгом порядке, и нарушать эту последовательность нельзя. Ключевой принцип — информация, попавшая в стек последней по хронологии, должна использоваться первой по очереди. Элемент данных используется, и стек пропадает. Следующим в очереди к использованию становится более ранний по времени попадания элемент.

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

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

Разновидности стеков

Стеки можно разделить на две большие группы: стеки вызовов и стеки данных.

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

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

Стеки данных. У них очень много схожих со стеками вызовов черт. В их основе — одна переменная значительных размеров, которая похожа на массив или список. Используются они при работе с более массивными и разветвленными данными. Но принцип работы схож с классическим — сначала используется более поздний элемент кода.

Переполнение стека

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

1. безостановочная работа рекурсии;
2. добавление новых элементов в стек после очередного витка рекурсии;
3. переполнение из-за большого количества новых элементов и отсутствия места для их складирования.

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

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Реализация стека

Стек можно реализовать на массиве, на динамическом массиве и на списке.

Реализация на массиве. Стек состоит из цепи элементов с обозначением [s1…s.top]. s1 — это начальный элемент в очереди, s.top — последний. Если s.top равен нулю, то такой стек считается пустым. Протестировать на наличие пустых элементов можно с помощью команды stackEmpty. Если данные будут сниматься с пустого стека, то это может приводить к ошибке.

Реализация на динамическом массиве. При таком способе исчезает риск выйти за границы массива при выполнении вставки нового элемента: операция push.

Реализация на списке. Для выполнения реализации нужно создать сам список и перечень операций на нем. Добавляться элементы к нему будут через привязку к верхнему — команды head.data (текущий головной элемент) и head.next (добавляемый элемент, который становится головным).

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

Статьи по теме: