Что такое стек в программировании

Учебники. Программирование для начинающих.

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

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

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

Assembler

Глава 1. Архитектура реального режима

Стек

Стеком называют область программы для временного хранения произвольных данных. Разумеется, данные можно сохранять и в сегменте данных, однако в этом случае для каждого сохраняемого на время данного надо заводить отдельную именованную ячейку памяти, что увеличивает размер программы и количество используемых имен. Удобство стека заключается в том, что его область используется многократно, причем сохранение в стеке данных и выборка их оттуда выполняется с помощью эффективных команд push и pop без указания каких-либо имен.
Стек традиционно используется, например, для сохранения содержимого регистров, используемых программой, перед вызовом подпрограммы, которая, в свою очередь, будет использовать регистры процессора «в своих личных целях». Исходное содержимое регистров извлекается из стека после возврата из подпрограммы. Другой распространенный прием — передача подпрограмме требуемых ею параметров через стек. Подпрограмма, зная, в каком порядке помещены в стек параметры, может забрать их оттуда и использовать при своем выполнении.
Отличительной особенностью стека является своеобразный порядок выборки содержащихся в нем данных: в любой момент времени в стеке доступен только верхний элемент, т.е. элемент, загруженный в стек последним. Выгрузка из стека верхнего элемента делает доступным следующий элемент.
Элементы стека располагаются в области памяти, отведенной под стек, начиная со дна стека (т.е. с его максимального адреса) по последовательно уменьшающимся адресам. Адрес верхнего, доступного элемента хранится в регистре-указателе стека SP. Как и любая другая область памяти программы, стек должен входить в какой-то сегмент или образовывать отдельный сегмент. В любом случае сегментный адрес этого сегмента помещается в сегментный регистр стека SS. Таким образом, пара регистров SS:SP описывают адрес доступной ячейки стека: в SS хранится сегментный адрес стека, а в SP — смещение последнего сохраненного в стеке данного (рис. 1.10, а). Обратите внимание на то, что в исходном состоянии указатель стека SP указывает на ячейку, лежащую под дном стека и не входящую в него.

Рис. 1.10. Организация стека:
а — исходное состояние, б — после загрузки одного элемента (в данном примере — содержимого регистра АХ), в — после загрузки второго элемента (содержимого регистра DS), г — после выгрузки одного элемента, д — после выгрузки двух элементов и возврата в исходное состояние.

Загрузка в стек осуществляется специальной командой работы со стеком push (протолкнуть). Эта команда сначала уменьшает на 2 содержимое указателя стека, а затем помещает операнд по адресу в SP. Если, например, мы хотим временно сохранить в стеке содержимое регистра АХ, следует выполнить команду

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

переведет стек в состояние, показанное на рис. 1.10, в. В стеке будут теперь храниться два элемента, причем доступным будет только верхний, на который указывает указатель стека SP. Если спустя какое-то время нам понадобилось восстановить исходное содержимое сохраненных в стеке регистров, мы должны выполнить команды выгрузки из стека pop (вытолкнуть):

Состояние стека после выполнения первой команды показано на рис. 1.10, г, а после второй — на рис. 1.10, д. Для правильного восстановления содержимого регистров выгрузка из стека должна выполняться в порядке, строго противоположном загрузке — сначала выгружается элемент, загруженный последним, затем предыдущий элемент и т.д.
Совсем не обязательно при восстановлении данных помещать их туда, где они были перед сохранением. Например, можно поместить в стек содержимое DS, а извлечь его оттуда в другой сегментный регистр — ES;

Это распространенный прием для перенесения содержимого одного регистра в другой, особенно, если второй регистр — сегментный.
Обратите внимание (см. рис 1.10) на то, что после выгрузки сохраненных в стеке данных они физически не стерлись, а остались в области стека на своих местах. Правда, при «стандартной» работе со стеком они оказываются недоступными. Действительно, поскольку указатель стека SP указывает под дно стека, стек считается пустым; очередная команда push поместит новое данное на место сохраненного ранее содержимого АХ, затерев его. Однако пока стек физически не затерт, сохраненными и уже выбранными из него данными можно пользоваться, если помнить, в каком порядке они расположены в стеке. Этот прием часто используется при работе с подпрограммами.
Какого размера должен быть стек? Это зависит от того, насколько интенсивно он используется в программе. Если, например, планируется хранить в стеке массив объемом 10 000 байт, то стек должен быть не меньше этого размера. При этом надо иметь в виду, что в ряде случаев стек автоматически используется системой, в частности, при выполнении команды прерывания int 21h. По этой команде сначала процессор помещает в стек адрес возврата, а затем DOS отправляет туда же содержимое регистров и другую информацию, относящуюся к прерванной программе. Поэтому, даже если программа совсем не использует стек, он все же должен присутствовать в программе и иметь размер не менее нескольких десятков слов. В нашем первом примере мы отвели под стек 128 слов, что безусловно достаточно.

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

Стек — это вид структуры данных, в котором элементы упорядочены и добавление или удаление элементов происходит с верхней части стека — по принципу «Последним пришел — первым ушел» (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, элемент извлекается из вершины стека, и вершина обновляется, чтобы указывать на следующий узел в списке.

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

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

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

Книги для развития Soft Skills

7 янв. 2024 г.

Топ 11 книг как стать эффективнее

4 янв. 2024 г.

Что такое стек в программировании

Стек в программировании – это абстрактный тип данных, представляющий собой список элементов, организованный по принципу «последний пришел, первый ушел» (LIFO — Last In, First Out). Под этим подразумевается, что последний элемент, добавленный в стек, становится первым кандидатом на удаление. Действия с элементами стека обычно ограничиваются двумя основными операциями: добавлением (push) и удалением (pop) элементов.

Стек, как абстрактная структура данных, абсолютно не привязан к конкретному языку программирования. Его можно реализовать на большинстве из них, будь то Python, C++, Java, JavaScript и другие.

Зачем нужен стек в программировании

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

1. Выполнение функций и подпрограмм: При вызове функций стек используется для сохранения адресов возврата и локальных переменных. Это позволяет возвращаться к правильной точке после завершения работы функции и восстанавливать состояние исполнения.
2. Обратная польская нотация (ОПН): Стеки используются в вычислениях ОПН, которая является распространенным способом записи арифметических и логических выражений без использования скобок.
3. Рекурсия: В рекурсивных функциях стек помогает отслеживать и контролировать глубину рекурсии, сохраняя состояние выполнения при каждом вложенном вызове.
4. Управление памятью: Стек обеспечивает очень простой способ управления памятью. Данные, которые больше не нужны, автоматически удаляются из стека, когда функция или процедура завершается.

Примеры использования стека в программировании

Пример 1: Проверка правильности скобочной последовательности

Пусть задача состоит в том, чтобы проверить, правильно ли в тексте расставлены скобки различных типов: «()», «[]», «<>«. Для решения этой задачи можно использовать стек. Каждый раз, когда встречается открывающая скобка, она добавляется в стек, а когда встречается закрывающая скобка, проверяется, соответствует ли она скобке на вершине стека. Если да, то вершина стека удаляется, если нет, то скобочная последовательность некорректна. Если после просмотра всей строки стек пуст, то последовательность скобок правильна.

Пример 2: Реализация «Отменить действие»

Стеки используются в текстовых редакторах и IDE для реализации функции «Отменить». Каждое действие пользователя добавляется в стек. Когда пользователь нажимает «Отменить», выполняется операция pop, и состояние возвращается к предыдущему.

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

Пример 3: Обход деревьев и графов

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

Пример 4: Выполнение выражений в Обратной Польской Нотации (ОПН)

Рассмотрим выполнение арифметического выражения, записанного в Обратной Польской Нотации. Допустим, у нас есть выражение «5 3 4 + *». Это ОПН-форма выражения «5 * (3 + 4)». Алгоритм вычисления такого выражения с использованием стека выглядит следующим образом:

1. Читаем символы из выражения слева направо. Если символ — число, добавляем его в стек.
2. Если символ — операция (в данном случае «+» или «*»), извлекаем из стека два верхних элемента, выполняем операцию и помещаем результат обратно в стек.
3. Когда все символы выражения прочитаны, в стеке остается одно число — результат вычисления выражения.

Хотите быть успешным HR-специалистом или IT-рекрутером? Узнавайте о главных трендах и лайфхаках с нашим блогом в Telegram!

Для чего нужны стеки?

Когда я узнал, что такое стек, мне стало интересно его практическое применение. Оказалось, что чаще всего эта структура используется для имплементации операции “Отмена” ( то есть, ⌘+Z или Ctrl+Z).

Чтобы понять, как это работает, разберемся с определением стека.

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

Стек — список элементов, который может быть изменён лишь с одной стороны, называющейся вершиной стека.

Представьте приспособление для раздачи тарелок, в котором тарелки стоят в стопке. Новые тарелки можно добавлять только поверх уже имеющихся, а брать можно лишь сверху. Таким образом, чем позже тарелку положат в стопку, тем раньше её оттуда возьмут. В рамках структур данных это называется LIFO-принципом (последним пришёл — первым ушёл).

Если использовать терминологию, то стек поддерживает операции добавления (push) и удаления (pop) элементов на его вершине.

Зачем использовать стек для отмены?

Потому что обычно мы хотим отменить последнее действие.

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

Что произойдёт, если ни одно действие не будет отменено? Стек ведь станет огромным!

Верно. Если не удалять элементы из стека отмены, то есть не использовать операцию отмены, то он станет очень большим. Именно поэтому такие приложения, как Adobe Photoshop, с увеличением времени работы над файлом используют всё больше и больше оперативной памяти. Стек отмены хранит все действия, произведённые над файлом, в памяти до тех пор, пока вы не сохраните и не закроете файл.

Имплементация стека

Стек можно реализовать, используя либо связные списки, либо массивы. Я приведу пример реализации стека на обеих структурах на Python и расскажу о плюсах и минусах каждой.

Стек на связном списке:

from LinkedList import LinkedList
# LinkedList.py можно найти здесь: https://gist.github.com/nsafai/01395dc3d5fb48680fc0f14686f4b24e

class LinkedStack(object):
 
def __init__(self, iterable=None): 
"""Инициализация стека и добавление в него элементов, если они есть.""" 
self.list = LinkedList() # Инициализация связного списка для наследования методов 
if iterable is not None: 
for item in iterable: 
self.push(item)
 
def push(self, item): 
""""Добавление элементов в вершину стека 
Сложность: O(1), потому что мы меняем первый элемент списка""" 
self.list.prepend(item) 
 
def peek(self): 
"""Возвращает верхний элемент стека, не удаляя его, 
или None, если стек пустой.""" 
head = self.list.head 
return None if head is None else head.data 
 
def pop(self): 
"""Удаляет и возвращает верхний элемент, если он есть, иначе выдаёт ValueError 
Сложность: O(1), потому что мы меняем первый элемент списка""" 
head = self.peek() 
self.list.delete(head) 
return head

Стек на массиве:

class ArrayStack(object):
 
def __init__(self, iterable=None): 
"""Инициализация стека и добавление в него элементов, если они есть.""" 
self.list = list() # Инициализация списка (встроенного в Python динамического массива) для хранения элементов 
if iterable is not None: 
for item in iterable: 
self.push(item) 
 
def push(self, item): 
""""Добавление элементов на вершину стека 
Сложность: O(1), пока мы не заполним всю выделенную память, затем O(n)""" 
self.list.append(item)
 
def peek(self): 
"""Возвращает верхний элемент стека, не удаляя его, 
или None, если стек пустой.""" 
last_item_idx = len(self.list) - 1 
return None if last_item_idx < 0 else self.list[last_item_idx]
 
def pop(self): 
"""Удаляет и возвращает верхний элемент, если он есть, иначе выдаёт ValueError 
Сложность: O(1), так как нужно удалить лишь последний элемент""" 
if self.peek() == None: 
raise ValueError("list is empty") 
else: 
return self.list.pop()

Что лучше?

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

Однако есть некоторые нюансы, которые стоит учесть.

Массив

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

Связный список

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

Заключение

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

Как видим, между этими двумя реализациями стека практически нет различий — используйте ту, что нравится вам.