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

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

Посте­пен­но осва­и­ва­ем спо­со­бы орга­ни­за­ции и хра­не­ния дан­ных. Уже было про дере­вья, попро­бу­ем про сте­ки. Это для тех, кто хочет в буду­щем серьёз­но рабо­тать в ИТ: одна из фун­да­мен­таль­ных кон­цеп­ций, кото­рая вли­я­ет на каче­ство ваше­го кода, но не каса­ет­ся какого-то кон­крет­но­го язы­ка программирования.

👉 Стек — это одна из струк­тур дан­ных. Струк­ту­ра дан­ных — это то, как хра­нят­ся дан­ные: напри­мер, свя­зан­ные спис­ки, дере­вья, оче­ре­ди, мно­же­ства, хеш-таблицы, кар­ты и даже кучи (heap).

Как устроен стек

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

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

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

Когда кому-то пона­до­бит­ся тарел­ка, он не будет брать её сни­зу или из сере­ди­ны — он возь­мёт первую свер­ху, потом сле­ду­ю­щую и так далее.

🤔 Есть струк­ту­ра дан­ных, похо­жая на стек, — назы­ва­ет­ся оче­редь, или queue. Если в сте­ке кто послед­ний при­шёл, того пер­вым забе­рут, то в оче­ре­ди наобо­рот: кто рань­ше при­шёл, тот рань­ше ушёл. Мож­но пред­ста­вить оче­редь в мага­зине: кто рань­ше её занял, тот пер­вый дошёл до кас­сы. Оче­редь — это тоже линей­ный набор дан­ных, но обра­ба­ты­ва­ет­ся по-другому.

Стек вызовов

В про­грам­ми­ро­ва­нии есть два вида сте­ка — стек вызо­вов и стек данных.

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

Что­бы это реа­ли­зо­вать, ком­пью­тер исполь­зу­ет стек вызо­вов — спе­ци­аль­ную область памя­ти, где хра­нит дан­ные о точ­ках пере­хо­да меж­ду фраг­мен­та­ми кода.

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

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

А вот как стек помо­га­ет это реа­ли­зо­вать на практике:

Про­грам­ма дошла до синей функ­ции, сохра­ни­ла точ­ку, куда ей вер­нуть­ся после того, как закон­чит­ся функ­ция, и если функ­ция вер­нёт какие-то дан­ные, то про­грам­ма тоже их полу­чит. Когда синяя функ­ция закон­чит­ся и про­грам­ма полу­чит верх­ний эле­мент сте­ка, он авто­ма­ти­че­ски исчез­нет. Стек сно­ва пустой.

С зелё­ной функ­ци­ей всё то же самое — в стек зано­сит­ся точ­ка воз­вра­та, и про­грам­ма начи­на­ет выпол­нять зелё­ную функ­цию. Но внут­ри неё мы вызы­ва­ем крас­ную, и вот что происходит:

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

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

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

  • рекур­сия всё рабо­та­ет и работает;
  • при каж­дом новом вит­ке рекур­сии в стек добав­ля­ют­ся новый элемент;
  • когда эле­мен­тов будет слиш­ком мно­го, память закон­чит­ся, новые эле­мен­ты неку­да будет скла­ды­вать и про­изой­дёт пере­пол­не­ние стека.

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

Стек данных

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

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

Что дальше

А даль­ше пого­во­рим про тип дан­ных под назва­ни­ем «куча». Да, такой есть, и с ним тоже мож­но эффек­тив­но рабо­тать. Стей тюнед.

Текст и иллю­стра­ции:
Миша Поля­нин

Редак­тор:
Мак­сим Ильяхов

Кор­рек­тор:
Ира Михе­е­ва

Иллю­стра­тор:
Даня Бер­ков­ский

Вёрст­ка:
Маша Дро­но­ва

Достав­ка:
Олег Веш­кур­цев

Основные принципы программирования: стек и куча

Рассказывает Аарон Краус 


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

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

Стек

Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out),  то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.

Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.

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

Куча

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

Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.

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

Заключение

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

Не смешно? А здесь смешно: @ithumor

Перевод статьи «Programming Concepts: The Stack and the Heap»

Для чего нужны стеки?. Кратко и просто об одной из самых… | by not eisenheim | NOP::Nuances of Programming

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

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

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

Верно. Если не удалять элементы из стека отмены, то есть не использовать операцию отмены, то он станет очень большим. Именно поэтому такие приложения, как 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()

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

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

Массив

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

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

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

Заключение

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

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

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

Что мы называем «stack» в Python? Это стек C из CPython? Я читал, что Python стековых кадра выделяются в куче. Но я думал, что цель стека-это … складывать стековые кадры. Что же тогда делает стек?

python

cpython

python-internals

Поделиться

Источник


usual me

23 августа 2014 в 00:35

2 ответа


  • Что такое «стек трэш»?

    Что такое стек трэш? Или стек трэш? (Поскольку я не знаю определения, я не уверен, является ли это счетным или несчетным термином.)

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

    Возможный Дубликат : Как работает функция jQuery pushStack? В jQuery API я увидел функцию pushStack . Описание sais: Add a collection of DOM elements onto the jQuery stack. Кто-нибудь знает, что такое стек jQuery и для чего он может быть использован? Имеет ли это отношение к DOM?



8

Кадры стека Python распределяются в куче. Но они связаны друг с другом, образуя стек. Когда функция a вызывает функцию b, кадр стека b указывает на кадр стека a в качестве следующего кадра (технически, a является атрибутом f_back кадра b .)

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

Поделиться


Ned Batchelder

23 августа 2014 в 01:21



5

Немного упрощая:

В CPython, когда PyEval_EvalFrameEx вычисляет код кадра стека Python и приходит к прямому вызову функции, он выделяет новый кадр стека Python, связывает его… а затем рекурсивно вызывает PyEval_EvalFrameEx на этом новом кадре.

Итак, стек C — это стек рекурсивных вызовов цикла интерпретатора.

Стек Python — это стек объектов кадра Python, реализованный в виде простого связанного списка объектов, выделенных кучей.

Они не совсем не связаны, но это не одно и то же.

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

Поделиться


abarnert

23 августа 2014 в 01:23


Похожие вопросы:

Что такое двойной стек?

Сейчас я готовлюсь к выпускному экзамену и вижу следующий вопрос в конце слайдов ppt профессора, которые говорят о стеке: What is a Double Stack? Я знаю, что стек — это упорядоченная коллекция…

Что такое «виртуальный стек выполнения»?

Я читаю о CIL и постоянно вижу ссылку на virtual execution stack (например, при создании локальных переменных и присвоении им значений). Но я не совсем понимаю, что такое виртуальный стек…

Что такое стек драйверов в ОС Windows?

Что такое стек драйверов в Windows OS? Я читал материал в NDIS году и не знал, что это такое.

Что такое «стек трэш»?

Что такое стек трэш? Или стек трэш? (Поскольку я не знаю определения, я не уверен, является ли это счетным или несчетным термином.)

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

Возможный Дубликат : Как работает функция jQuery pushStack? В jQuery API я увидел функцию pushStack . Описание sais: Add a collection of DOM elements onto the jQuery stack. Кто-нибудь знает, что…

Что такое стек и почему malloc предотвращает его переполнение?

Возможный Дубликат : Что и где находятся стек и куча Я новичок в языке C, я в основном использую Python для ежедневного использования, поэтому я не очень хорошо знаком с этими понятиями. Предыдущий…

Стек-что это такое?

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

Что такое стек операндов?

Я читаю об архитектуре JVM. Сегодня я прочитал о концепции стека операндов. Согласно статье: Стек операндов используется при выполнении инструкций байтового кода аналогично тому, как регистры общего…

Что делает метод getTrace() в php ? Что такое стек?

Я новичок в php и учусь этому у php.net . Может ли кто-нибудь сказать, что такое стек и почему мы используем метод getTrace() в php ? Когда я использую следующий код: try{ throw new Exception(Custom…

Что такое скомпилированный стек?

Я наткнулся на указанную терминологию и уже понял, что она каким-то образом используется на микроконтроллерах, но не нашел никакого объяснения. Что такое скомпилированный стек, для чего он…

что это такое и как использовать?

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

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

Стек — что это такое?

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

Итак, стек — это метод представления однотипных данных в порядке LIFO (Last In — First Out, то бишь, «первый вошел — последний вышел»). Некоторые ассоциируют стек с оружейным магазином для патронов, так как принцип работы схож, и первый вставленный в магазин патрон будет использоваться в последнюю очередь (у термина стек бывают и другие значения, поэтому, если речь идёт не об информационных технологиях, то смысл лучше уточнить).

Стек и простой жизненный пример

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

Стек и особенности его работы

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

Благодаря природе, которую имеет стек, управление памятью становится весьма простым и логичным для выполнения на центральном процессоре. Это повышает скорость и быстродействие ЦП, и в особенности такое происходит потому, что время цикла обновления байта весьма незначительно (данный байт, скорее всего, привязан к кэшу центрального процессора).

Тем не менее у данной довольно строгой формы управления имеются и свои недостатки. Например, размер стека — это величина фиксированная, в результате чего при превышении лимита памяти, выделенной на стеке, произойдёт переполнение стека. Как правило, размер задаётся во время создания потока, плюс у каждой переменной имеется максимальный размер, который зависит от типа данных. Всё это позволяет ограничивать размеры некоторых переменных (допустим, целочисленных).

Кроме того, это вынуждает объявлять размер более сложных типов данных (к примеру, массивов) заранее, так как стек не позволит потом изменить его. Вдобавок ко всему, переменные, которые расположены на стеке, являются всегда локальными.

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

Главное предназначение стека — решение типовых задач, предусматривающих поддержку последовательности состояний или связанных с инверсионным представлением данных. В компьютерной отрасли стек применяется в аппаратных устройствах (например, в центральном процессоре, как уже было упомянуто выше).

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

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

Стеки и операции стека

Если говорить об основных операциях, то стек имеет таковых две:
1. Push — ни что иное, как добавление элемента непосредственно в вершину стека.
2. Pop — извлечение из стека верхнего элемента.

Также, используя стек, иногда выполняют чтение верхнего элемента, не выполняя его извлечение. Для этого предназначена операция peek.

Как организуется стек?

Когда программисты организуют или реализуют стек, они применяют два варианта:
1. Используя массив и переменную, указывающую на ячейку вершины стека.
2. Используя связанные списки.

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

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

Стек и куча

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

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

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

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

Что такое стек в покере? Типы покерного стека. Стек в кэше и турнире

Правила покера подразумевают строгую регламентацию всех этапов процесса игры. Это в равной степени относится и к финансовой ответственности участников игры. В данном случае подразумевается то количество фишек (денег), которое покерист может использовать в игре. Есть некоторая разница в этом отношении между кэш-игрой и турнирным покером. И в первом, и во втором случае игрок использует стек. Что это такое и какие особенности игры связаны с покер стеком – в нашем обзоре.

Стек в покере

Определение

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

Размер стека

Понятно, что он может быть разным, и каждый имеет свое название и особенности, о которых мы поговорим далее. Пока же следует уяснить, что размер стека в покере всегда измеряется блайндами, которые приняты за столом, за которым идет игра.
Предположим, вы играете за столом $1/$2. У вас фишек на $100. Следовательно, размер вашего стека составляет 50 Больших блайндов (ББ). Однако, как мы уже говорили, от размера стека напрямую зависит стратегия игры – чем больше стек, тем аккуратнее и осмотрительнее должна быть игра. Но об этом позже. Пока разберемся с тем, в чем заключается разница, которую имеют стеки в кэш-игре и в турнирах.

Покерный стек в кэш-играх и турнирах

В кэш-играх обычно устанавливается минимальный и максимальный лимит стека. То есть каждый участник игры соблюдает некий диапазон, меньше или больше которого фишек брать нельзя. Это ограничение преследует прежде всего цель создать более или менее равные условия для всех покеристов – чтобы никто из них не имел возможности «задавить» большим стеком оппонентов. Начинающим покеристам рекомендуется при определении кэш-стола, за которым они собираются играть, убедиться, что бай-ин (в данном случае его сумма и будет стеком) для них комфортный.

К примеру, в игре Безлимитный Холдем с размером ББ $0,04 можно более или менее комфортно играть и при стеке в $1,5, но оптимальным решением здесь будет стек в $4. Естественно, речь идет о начальном стеке, который будет меняться по ходу игры – при проигрышах уменьшаться, при выигрышах – расти.

Для управления стеком в кэш-играх следует знать некоторые нюансы этого формата:

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

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

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

С турнирным покером и стеком в нем дела обстоят несколько иначе. Здесь каждый участник ивента знает, сколько фишек у него будет на старте и соответственно на все событие. Правда, не редки турниры с возможностью ребая (докупки фишек), но это обстоятельство должно быть указано в условиях турнира. Если такой пометки нет, значит в игре будет участвовать только то количество фишек, которое было у всех участников с самого начала. Их количество не изменится, а вот распределение по игрокам будет меняться от раздачи к раздаче.

Типы стеков

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

Глубокий стек

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

Полный стек

Этот тип стека содержит, как правило, 100 ББ. Понятно, что по ходу игры эта сумма фишек может быть увеличена и доходить до 140-150 ББ. В этом случае это будет уже увеличенный стек. Если же говорить об обратном — 80-90 ББ, то такой стек называется укороченным.

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

Неполный

Спектр такого типа — 30-70 ББ. Играть с таким количеством фишек непросто, прежде всего потому что нет возможности в полной мере применять базовые стратегии и тактики, рассчитанные на полный стек.

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

Короткий стек

Этот тип отличается наличием у игрока фишек в районе 25 ББ. В покере, а именно в Техасском Холдеме есть специальные стратегии игры с коротким стеком. Эти тактики отличаются агрессивным вхождением в раздачу. Однако и здесь есть свои нюансы: многое зависит от позиции, силы карманки и так далее.

Ультракороткий стек

Это 10 ББ или менее. Самая оптимальная игра — выставление в олл-ин уже на префлопе. Во многом такая манера может напоминать игру по принципу «пан или пропал», но в определенных случаях она оправдана. Во всяком случае сторонником такой стратегии выступает один из лучших покерных аналитиков Дэвид Склански и математик Висконсинского университета Андрей Чубуков.

Стек и стратегия кэш-игры

То количество денег, которое игрок берет с собой за кэш-стол, должно опираться прежде всего на планы по его стратегии на игру. Если у покериста от 20 до 40 ББ, то он вынужден играть по стратегии короткого стека. То есть его активность предполагает агрессивную игру на префлопе, так как на улицах постфлопа, имея малое количество средств, он уже не того маневра, который предполагает игра с полным стеком.

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

Можно прийти к мнению, что игра с полным и глубоким стеком может привести к скорой потере части банкролла. Ведь, если кто-либо из оппонентов за столом выставиться и игрок с полным стеком ответит на олл-ин и проиграет ва-банк, его банкролл заметно просядет. Такое суждение справедливо, но только с точки зрения новичка в покере, для которого потеря стека в 100 ББ и больше видится катастрофой. Мы же говорим об опытных покеристах, которые придерживаются стратегии долгосрочной перспективы. Даже пара проигрышей полного стека в долгосрочной перспективе с высокой вероятностью окупится и в ровно такой же ситуации с олл-ином.

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

Но в некоторых ситуациях фишки необходимо сбрасывать. Это обязательно необходимо делать, если количество фишек в вашем стеке значительно превышает первоначальный показатель. Предположим, в игру на $0,1/$0,2 вы взяли с собой в качестве стека фишек на $20. То есть у вас полный стек. На каком-то этапе у вас скопилось $100.

В этой ситуации стоит быть осмотрительнее. Если у всех остальных игроков за столом стек по-прежнему в районе $20, можно продолжать играть. Если же у кого-либо из оппонентов стек также перешел из разряда полного в глубокий и более, то рекомендуем вам прерваться на время и скинуть излишек фишек, доведя стек до первоначального размера в $20.

Объясняется это довольно просто. Судите сами, если в ответ на агрессивный олл-ин оппонента со стеком в $120 вы ответите и проиграете свою сотню, то вы не сможете за один раз докупить проигранные фишки на $100. В игре стоит ограничение по докупке – $20. Следовательно, вы не сможете в полной мере реализовать математические ожидания от ситуации. Другими словами, впоследствии ваши $20 против его уже $220 на лимите $0,1/$0,2 так или иначе превратятся в пыль. К проигранным $100 добавятся еще $20.

А если вы вовремя сбросите выигранные $80, и останетесь в раздаче с $20, то, во-первых, сохраните выигрыш, к которому всегда можно будет вернуться, во-вторых, вернетесь в раздачу с полным стеком, который предоставляет вам все возможности реализовывать задуманные тактики. То есть не спешите переходить из разряда лидера в разряд догоняющего.

Стек в турнирном покере

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

И совсем наоборот дела обстоят тогда, когда количество ББ в стеке тает, тем более это ощутимо на фоне роста ставок в турнирном покере. Игроку приходится не только ограничивать себя в стратегии, но даже выплата обязательных ставок становится для него в тягость.

Эффективный стек

В покере есть такое понятие как эффективный стек. И для новичка в покере это понятие более чем актуально.
Эффективный стек — это то количество фишек либо реальных денег, которые игрок собирается вкладывать в игру против соперника. Что это означает? Предположим, ваш стек $150, у вашего противника – $100. Если вы идете олл-ин, то используете только $100, ведь большим противник ответить не сможет. Получается, что прибыль вы рассчитываете не из своих $150, а только из $100 из них. Вот как раз эти $100 в данном случае — для вас эффективный стек.

Знакомство с понятием «эффективный стек в покере» поможет научиться выбирать выгодные для себя столы. Останавливайте свой выбор на тех столах, за которыми играют покеристы, против которого ваш стек был бы максимально эффективным. Возвращаясь к нашему примеру, если у вас стек $150, то не стремитесь за столы, за которыми сидят противники с фишками на $80-100. Вам нужны столы, где большинство соперников имеют стек пусть и не намного, но все же выше вашего. Только в этом случае ваш стек будет эффективным, отвечать математическим ожиданиям от реализации конкретных решений, которые опять-таки полностью зависят от величины стека.

625

Как реализовать стек в Python

Возможно вы что то слышали о стеках и задавались вопросом, что это такое? У вас есть общее представление об этом, но вам интересно, как реализовать стек в Python? Тогда вы пришли в нужное место!

В этой статье вы узнаете:

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

Это руководство предназначено для питонистов, которые хорошо разбираются в сценариях, знают, что такое списки и как их использовать, и интересуются, как реализовать стек в Python.

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

Стек — это структура данных, в которой элементы хранятся в порядке поступления. Его еще часто называют LIFO (Last-In/First-Out). Это отличается его от очереди, в которой элементы хранятся в порядке «первым пришел / первым обслужен» (FIFO).

Вероятно, проще всего понять стек, если вы представите сценарий использования, с которым вы, вероятно, знакомы: функция отмены (Undo) в вашем редакторе.

Давайте представим, что вы редактируете вашу программу на Python. Сначала вы добавляете новую функцию. Это добавляет новый элемент в стек отмены:

Вы можете видеть, что в стеке теперь есть операция Add Function. После добавления функции вы удаляете слово из комментария. Это также добавляется в стек отмены:

Обратите внимание, как элемент «Delete Word» помещается на вершину стека. Наконец, вы делаете отступ для комментария, чтобы он выстроился правильно:

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

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

Ваш редактор отменяет отступ, а стек отмены теперь содержит два элемента. Эта операция противоположна push и обычно называется pop.

Когда вы снова нажмете кнопку «Отменить», из стека выскочит следующий предмет:

Удалится элемент «Delete Word», оставляя только одну операцию в стеке.

Наконец, если вы нажмете Отменить в третий раз, то последний элемент будет вытолкнут из стека:

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

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

Есть несколько вариантов, когда вы реализуете стек в Python. Эта статья не охватывает все из них, только основные, которые будут соответствовать почти всем вашим потребностям. Мы сосредоточимся на использовании структур данных, которые являются частью библиотеки Python, и не используют сторонних пакетов.

Мы посмотрим на следующие реализации стека:

  • list
  • collections.deque
  • queue.LifoQueue

Использование list для создания стека

Встроенная структура list, которую вы, вероятно, часто используете в своих программах, может использоваться и в качестве стека. Вместо .push() можно использовать .append() для добавления новых элементов в верхнюю часть стека, в то время как .pop() удаляет элементы в порядке LIFO:

>>> myStack = []

>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')

>>> myStack
['a', 'b', 'c']

>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'

>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from empty list

В последней команде вы можете видеть, что список вызовет IndexError, если вы вызовете .pop() в пустом стеке.

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

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

Если ваш стек становится больше, чем блок памяти, в котором он находится на данный момент, то Python должен сделать некоторое дополнительное выделения памяти. Это может привести к тому, что некоторые вызовы .append() будут занимать намного больше времени, чем другие.

Есть и менее серьезная проблема. Если вы используете .insert() для добавления элемента в ваш стек в позиции, отличной от конца, это может занять гораздо больше времени. Однако обычно это не то, что вы делаете со стеком.

Следующая структура данных поможет вам обойти проблему перераспределения памяти.

Использование collection.deque для создания стека

Модуль collection содержит deque, который полезен для создания стеков. deque переводиться как «колода» и означает «двусторонняя очередь».

Вы можете использовать те же методы для deque, которые мы видели выше для list, .append() и .pop():

>>> from collections import deque
>>> myStack = deque()

>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')

>>> myStack
deque(['a', 'b', 'c'])

>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'

>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from an empty deque

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

Зачем нужен deque если есть list?

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

Это отлично работает для нескольких операций, таких как индексация в списке. Так получение элемента по индексу myList[3] работает быстро, так как Python точно знает, где искать в памяти. Эта схема памяти также позволяет хорошо работать со срезами списков.

Непрерывное расположение памяти — причина, по которой списку может потребоваться больше времени для .append() одних объектов, чем других. Если блок смежной памяти заполнен, то ему потребуется получить другой блок, который может занять намного больше времени, чем обычный .append():

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

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

Добавление новой записи в структуру связанного списка требует только установки ссылки на новую запись так, чтобы она указывала на текущую вершину стека, а затем указывала вершину стека на новую запись:

Однако это постоянное добавление и удаление записей в стеке сопряжено с компромиссом. Получение данных по индексу myDeque[3] медленнее, чем для списка, потому что Python должен пройти через каждый узел списка, чтобы добраться до третьего элемента.

К счастью, вы редко будете выполнять случайную индексацию или использовать срезы в стеке. Большинство операций над стеком будут push или pop.

Операции .append() и .pop() с постоянным временем делают deque отличным выбором для реализации стека Python, если ваш код не использует многопоточность.

Python стеки и многопоточность

Стеки Python могут быть полезны и в многопоточных программах.

Два варианта, которые вы видели до сих пор, list и deque, ведут себя по-разному, если в вашей программе есть потоки.

Начнем с более простого, запомните вы никогда не должны использовать list для какой-либо структуры данных, к которой могут обращаться несколько потоков. Список не является потокобезопасным.

Примечание. Если вам нужно освежить в памяти информацию о безопасности потоков и условиях гонки, ознакомьтесь с Введение в потоки в Python (An Intro to Threading in Python).

Однако, с deque немного иначе. Если вы прочтете документацию по deque, в ней будет четко указано, что обе операции .append() и .pop() являются атомарными, то есть они не будут прерваны другим потоком.

Так что если вы ограничитесь использованием только .append() и .pop(), то у вас не будет проблем с потоками.

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

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

Хорошо, если вы работаете с потоками, вы не можете использовать list для стека и, вероятно, не захотите использовать deque для стека, так как же вы можно построить стек Python для многопоточной программы?

Ответ находится в модуле очереди, queue.LifoQueue. Помните, как вы узнали, что стеки работают по принципу «последний пришел / первый вышел»? Ну, вот что означает «Lifo» в LifoQueue.

В то время как интерфейс для list и deque похожи, LifoQueue использует .put() и .get() для добавления и удаления данных из стека:

>>> from queue import LifoQueue
>>> myStack = LifoQueue()

>>> myStack.put('a')
>>> myStack.put('b')
>>> myStack.put('c')

>>> myStack
<queue.LifoQueue object at 0x7f408885e2b0>

>>> myStack.get()
'c'
>>> myStack.get()
'b'
>>> myStack.get()
'a'

>>> # myStack.get() <--- waits forever
>>> myStack.get_nowait()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
  File "/usr/lib/python3.7/queue.py", line 198, in get_nowait
    return self.get(block=False)
  File "/usr/lib/python3.7/queue.py", line 167, in get
    raise Empty
_queue.Empty

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

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

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

Стеки Python: какую реализацию следует использовать?

В общем случае, вы должны использовать deque, если вы не используете многопоточность. Если вы используете многопоточность, то вам следует использовать LifoQueue.

Список может быть прост, но его следует избегать, потому что он может иметь проблемы с перераспределением памяти. Интерфейсы для deque и list идентичны, и deque не имеет этих проблем, что делает deque лучшим выбором для вашего непоточного стека Python.

Заключение

Теперь вы знаете, что такое стек, и видели ситуации, когда их можно использовать в реальных программах. Мы оценили три различных варианта реализации стеков и увидели, что deque — отличный выбор для непоточных программ. Если вы реализуете стек в среде многопоточности, то, вероятно, будет хорошей идеей использовать LifoQueue.

Теперь вы можете:

  • Распознать, когда стек будет хорошей структурой данных
  • Выбрать, какая реализация лучше подойдет для вашей проблемы

Оригинальная статья: Jim Anderson  How to Implement a Python Stack

Была ли вам полезна эта статья?

[8 / 3.5]

Определение стека

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

Когда объект добавляется в стопку, он помещается поверх всех ранее введенных элементов. Когда элемент удаляется, его можно удалить сверху или снизу стопки. Стек, в котором элементы удаляются сверху, считается стеком «LIFO» (последний пришел, первый ушел).Вы можете представить стопку LIFO как колоду карт, в которой вы кладете отдельные карты в колоду, а затем берете карты сверху. В стеке «FIFO» («первым пришел — первым ушел») элементы удаляются снизу. Вы можете представить стопку FIFO в виде ряда в торговом автомате, где предметы выдаются в том порядке, в котором они были помещены в автомат.

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

Хотя стеки обычно используются программистами, вы, как правило, не замечаете их при использовании программы. Это связано с тем, что создание стеков, а также операции push и pop выполняются в фоновом режиме во время работы приложения и не видны пользователю. Однако, если стеку не хватает памяти, это вызовет «переполнение стека». Если программа не обрабатывает правильно, переполнение стека может вызвать сообщение об ошибке или вызвать сбой программы.

ПРИМЕЧАНИЕ: Термин «стек» может также относиться к стеку протоколов, который состоит из нескольких сетевых протоколов, работающих вместе.Каждый протокол делится на один из семи различных уровней, определенных в модели OSI.

Обновлено: 23 июля 2014 г.

TechTerms — Компьютерный словарь технических терминов

Эта страница содержит техническое определение слова «стек». Он объясняет в компьютерной терминологии, что означает стек, и является одним из многих технических терминов в словаре TechTerms.

Все определения на веб-сайте TechTerms составлены так, чтобы быть технически точными, но также простыми для понимания. Если вы найдете это определение стека полезным, вы можете ссылаться на него, используя ссылки для цитирования выше.Если вы считаете, что термин следует обновить или добавить в словарь TechTerms, отправьте электронное письмо в TechTerms!

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

Подписаться

Определение стека по Merriam-Webster

\ ˈStak

\

1

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

: упорядоченная куча или куча

б

: большое количество или количество

3

: английская единица измерения, особенно для дров, равная 108 кубическим футам.

: ряд дымоходов, образующих одну конструкцию, возвышающуюся над крышей.

б

: вертикальная труба (для отвода дыма)

c

: выхлопная труба двигателя внутреннего сгорания.

: Конструкция книжных полок для компактного хранения книг.

— обычно используется во множественном числе

б
множественное число

: Часть здания, в которой размещены такие конструкции.

6

: куча покерных фишек

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

также

: структура данных, имитирующая стек

стопка с опусканием вниз

б

: память компьютера, состоящая из массивов элементов памяти, установленных один поверх другого.

сложены; штабелирование; стеки

переходный глагол

: в стопку : стопку

б

: для наложения или наложения

сложил стол с книгами стопку посудомоечной машины

: тайно организовать мошенничество

складывать колоду карт

б

: упорядочить или исправить так, чтобы был вероятен конкретный результат.

шансы складываются против нас, присяжные будут складываться в соответствии с их собственными предпочтениями, — Патрис Хорн

: присвоить (самолету) по радио определенную высоту и позицию в группе, кружащей перед приземлением.

б

: поставить в очередь ожидания

еще дюжина буров сложена и ждет — П.Х. Хатчинс-младший

4

: сравнить

— использованное с против , такое преступление — ничто, если противопоставить убийство — Пит Ценски

Структура данных стека — что это такое и как она используется в JavaScript? | Элис Мэтьюз

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

Стек — это линейная структура данных, элементы наложены друг на друга. Доступен только последний добавленный элемент, то есть элемент наверху стека. То есть стек представляет собой структуру LIFO (Last In First Out). Это противоположно очереди, которая работает в порядке очереди (FIFO). Позже мы увидим, что среда выполнения JavaScript использует оба из них.

Распространенная аналогия стека данных — стопка (или стопка!) Тарелок в столовой; тарелки укладываются друг на друга. Покупатель берет тарелку сверху. Если по какой-то причине они хотели получить доступ ко второй пластине, им пришлось бы сначала удалить верхнюю.

Визуализация структуры стека данных

Стеки данных работают аналогично. У них есть три основные операции:

  • Push () — новый элемент добавляется наверху стека
  • Pop () — удаляет и возвращает элемент наверху стека
  • Top () / peek () — Посмотрите в стек и верните последний элемент, помещенный в стек.Эта операция не изменяет стек.

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

Реализация

  1. Массив
  2. Связанный список

Приложения

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

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

В оставшейся части статьи мы рассмотрим пример стека вызовов более подробно.

Стек вызовов — это механизм, с помощью которого интерпретатор (например, интерпретатор JavaScript в веб-браузере) отслеживает свое место в сценарии, который вызывает несколько функций .

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

  1. Сценарий вызывает функцию
  2. Функция добавляется в стек вызовов, и функция выполняется
  3. Если внутри вызывается другая функция, она добавляется в верхнюю часть стека вызовов и выполняется до завершения.
  4. По завершении текущая функция удаляется из стека, а исходная функция возобновляет выполнение.

Визуальное представление стека вызовов в различных частях среды выполнения

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

Стек — Computer Science Wiki

из Вики по информатике

Перейти к навигации
Перейти к поиску

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

Название «стек» для этого типа структуры происходит от аналогии с набором физических предметов, уложенных друг на друга, что позволяет легко снимать элемент с вершины стека, при этом добраться до элемента глубже в стопке может потребоваться снятие нескольких других предметов сначала [2] .

[3]

Методы доступа к стеку [править]

практические применения стека [править]

Мы можем видеть поведение стека с функциями повтора и отмены во многих местах, таких как редакторы, фотошоп, а также функция перемотки вперед и назад в веб-браузерах.

Учебное задание на питоне [править]

Используя структуру данных списка Python, реализуйте 3 функции стека, push, pop и isEmpty. Мы предполагаем, что знаем имя стека.

 myStack = []

def push (элемент):

    # делай что-нибудь здесь

    возвращаться

def pop (элемент):

    # делай что-нибудь здесь

    возвращаться

def isEmpty (stackName):

    # эта функция должна возвращать логическое значение True или False
    возвращаться
 

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

Стандарты

[править]

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

См. Также [редактировать]

Источники [править]

Определение технического стека

| Mixpanel

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

Определение

Стек технологий, также называемый стеком решений, технологической инфраструктурой или экосистемой данных, представляет собой список всех технологических сервисов, используемых для создания и запуска одного приложения. Социальный сайт Facebook, например, состоит из комбинации фреймворков и языков программирования, включая JavaScript, HTML, CSS, PHP и ReactJS.Это «технологический стек» Facebook.

Разработчики говорят о технических стеках, потому что они упрощают передачу большого количества информации о том, как создается приложение. Этот термин иногда применяется к маркетинговым услугам (пакеты martech) или услугам продаж (пакеты продаж), но он возник в сообществе разработчиков программного обеспечения. Технический стек быстро обобщает языки программирования, фреймворки и инструменты, которые потребуются разработчику для взаимодействия с приложением. Поскольку большинство языков программирования имеют хорошо известные характеристики и ограничения производительности, технический стек намекает на сильные и слабые стороны приложения в целом.Если программист знает, что программный сервис построен, например, на PHP, он знает, что его кодовая база, вероятно, велика и ее трудно отлаживать. PHP — общеизвестно неэффективный язык программирования, но он используется в большинстве популярных веб-приложений. Если программист знает, что приложение было создано с использованием Ruby on Rails, он знает, что ему придется изучить язык программирования Ruby, чтобы вносить какие-либо изменения. Технические стеки особенно полезны для найма разработчиков. «Если кандидаты не знакомы с фреймворками и языками технологического стека или не желают познакомиться с ними, они могут не подходить», — сказал Джон Дебс, программист полного цикла в платформе обмена сообщениями Lua.Компании, пытающиеся нанять разработчиков, часто включают свой технический стек в должностные инструкции.

Как создать свой технический стек

Разным компаниям требуются разные технологические стеки, и нет двух одинаковых. Команды решают, какие технологии они хотят использовать, а затем опираются на базовый язык программирования, добавляя дополнительные инструменты и службы по мере продвижения. «Когда вы имеете в виду продукт, вы обычно начинаете с внешнего интерфейса, части, которая стоит перед заказчиком, а затем решаете, какие внутренние инструменты необходимы для его поддержки», — сказала Лира Скендери, аналитик данных и инженер хостинг-провайдера. Цифровой океан.Результирующий пакет услуг называется «стеком», потому что каждая дополнительная служба строится на основе тех, что находятся под ним, что позволяет разработчикам настраивать приложение. Разработчики, разрабатывающие приложение, к которому будут обращаться миллионы людей каждый день, могут выбрать языки программирования, которые лучше всего подходят для так называемых операций с высокой степенью чтения, то есть к ним могут обращаться одновременно многие пользователи. Если приложение предназначено для сканирования Интернета и сбора информации, разработчики могут выбрать языки с высокой степенью написания.Все технологические стеки разделены между серверной частью и клиентской частью, также известной как серверная и клиентская. Если бы технологический стек был портативным компьютером, серверной частью было бы внутреннее оборудование, которое заставляет его работать. Интерфейс внешнего интерфейса будет состоять из экрана, корпуса и клавиатуры, которые позволяют пользователю взаимодействовать с ноутбуком. Когда в заявлении о приеме на работу требуется инженер с опытом работы в бэкэнд, фронтенд и полный стек, это относится к той части технологического стека, на которой кандидат будет в идеале специализироваться.

Серверные технологии включают веб-фреймворки, языки программирования, серверы и операционные системы. Один из популярных технологических стеков веб-разработки известен под аббревиатурой LAMP, сокращенно от операционной системы Linux, HTTP-сервера Apache, системы управления реляционными базами данных MySQL и языка программирования PHP. Внешние технологии — это визуальный интерфейс, например веб-сайты и приложения. Это визуальные элементы, которыми славится большинство приложений, и предлагающие пользователям инструменты, необходимые для выполнения работы.Языки интерфейса пользователя обычно намного проще, чем языки внутреннего интерфейса. Большинство интерфейсов веб-приложений построены с использованием языка программирования Javascript и фреймворков Angular JS, Backbone.js и ReactJS. Внешние технологии для приложений для смартфонов включают Objective-C / SWIFT для приложений iOS и Java для приложений Android.

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

План на будущее

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

Положитесь на сообщество разработчиков ПО с открытым исходным кодом

Разработчики со всего мира вносят свой вклад в создание инструментов с открытым исходным кодом, которые бесплатны для использования и доступны всем, у кого есть подключение к Интернету. Размах сообщества открытого исходного кода и предлагаемые им полезности ошеломляют. «Программное обеспечение с открытым исходным кодом, вероятно, является причиной последних 10-20 лет технологического возрождения», — сказал Дебс.«Любой может встать на плечи гигантов и создавать продукты с невероятно сложной базовой технологией, которые они никогда не смогли бы создать сами. Вы говорите о совокупности миллиардов часов рабочего времени людей и вкладе экспертов в каждой области ». По оценкам Дебса, на написание программного обеспечения, которое он использует каждый день, у других людей уходили миллионы часов. Любым инженерным командам, рассматривающим возможность создания технологического стека, будет проще полагаться, по крайней мере частично, на программное обеспечение с открытым кодом.

Рассмотрите цель приложения

Разработчики, как правило, отдают предпочтение языкам, которые они уже знают, но для создания лучшего технологического стека стоит сделать шаг назад и позволить цели приложения определять его технологию. Например, будет ли приложение существовать на мобильном устройстве или на компьютере? Если на мобильном телефоне, какие приложения? Если настольный, то какие браузеры? Это медиа-сайт, который будет получать миллионы посетителей ежедневно, или приложение для мобильного банкинга, которое должно быть защищено? Для каждой из этих целей подходят разные языки программирования, инструменты и технологические стеки.Как и некоторые разработчики с соответствующими навыками.

Использовать аналитику

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

Рассмотреть содержание

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

Стек

и его основные операции

Стек и его основные операции

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

Во-первых, давайте посмотрим на свойства структур данных, которые мы уже знаем, и доработаем наши концепции до стека.

  • Массив: Это контейнер с произвольным доступом , что означает, что к любому элементу этого контейнера можно получить мгновенный доступ. доступ только последовательно

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

Стек — это структура данных, соответствующая принципу LIFO (Last In, First Out).

Если у вас проблемы с визуализацией стопок, представьте себе стопку книг.

  • В стопке книг вы можете видеть только верхнюю книгу
  • Если вы хотите получить доступ к любой другой книге, вам сначала нужно удалить книги наверху
  • Самая нижняя книга в стопке была ставится первым и может быть удален только после того, как все книги на нем будут удалены.

PUSH Операция

Операция Push — это вставка элемента в стек. Поскольку есть только одна позиция, в которую можно вставить новый элемент — Верх стека, новый элемент вставляется наверху стека.

POP Операция

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

PEEK Операция

Операция просмотра позволяет пользователю видеть элемент на вершине стека. В этой операции стек никаким образом не изменяется.

isEmpty : Проверить, пуст ли стек или нет.

Чтобы предотвратить выполнение операций с пустым стеком, программист должен внутренне поддерживать размер стека, который будет обновляться во время операций push и pop соответственно.isEmpty () обычно возвращает логическое значение: True, если размер равен 0, иначе False.

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

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

Вы должны помнить одну очень важную вещь →

Все операции в стеке должны иметь временную сложность O (1)

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

1. Реализация массива

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

  int stack [10]
int top = -1  

Здесь 10 — предопределенная емкость стека. Мы можем выдать ошибку переполнения стека, если пользователь попытается превысить эту емкость.

★ Значение по умолчанию для top равно -1, что означает, что стек пуст.

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

Давайте обернем эту группу элементов данных в class

  class Stack {
    int arr []
    int емкость
    int top
}  

Давайте также создадим конструктор, который инициализирует емкость и верхнюю

  Стек (int cap)
{
    емкость = крышка
    верх = -1
}  

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

→ Теперь нам нужно реализовать операции, которые мы обычно выполняем со стеками.

PUSH Operation

Какие изменения вносятся в стек при нажатии нового элемента?

  • Новый элемент вставлен сверху
  • Значение top увеличивается на 1

▹ Что делать, если стопка заполнена до отказа?

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

Теперь давайте просто реализуем это

  void push (int item)
{
    если (верх == вместимость - 1)
        print («Переполнение стека!»)
    еще
    {
        arr [top + 1] = элемент
        верх = верх + 1
    }
}  

Операция POP

Давайте попробуем еще раз: Pop ().

Какие изменения вносятся в стек внутри для операции pop?

  • Верхний элемент удален
  • Значение top уменьшено на 1

▹ Можете ли вы придумать исключение в этом случае, например, когда стек переполнен? Ответ: стек может быть пустым, если операция pop называется

. Давайте попробуем реализовать ее сейчас.

  void pop ()
{
    если (isEmpty () == Истина)
        print («Стопка пуста!»)
    еще
        top = top - 1
}  

★ Является ли уменьшение значения top тем же, что и удаление верхнего элемента? ( Think! )

Peek and isEmpty Operation

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

  int peek ()
{
    если (isEmpty () == Истина)
    {
        print («Стопка пуста!»)
        возврат -1
    }
    еще
        возврат arr [вверху]
}  
  bool isEmpty ()
{
    если (вверху == -1)
        вернуть True
    еще
        вернуть ложь
}  
2. Реализация связанного списка

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

Как вы думаете, какой конец должен представлять вершину стопки? ( Think! )

Верх стека должен быть представлен заголовком , потому что в противном случае мы не смогли бы реализовать операции стека с временной сложностью O (1).

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

  class ListNode {
    int val
    ListNode следующий
}  

Как должен выглядеть пустой стек, если он реализован со связным списком? Ответ: Его голова будет указывать на NULL

  ListNode head = NULL  

Есть ли какие-либо преимущества в реализации стека в виде связанного списка по сравнению с массивами? Ответ: Нам не нужно заранее указывать размер стопки.

→ Хотя, если вы хотите реализовать ограничение для предотвращения чрезмерного использования, вам может потребоваться инкапсулировать класс ListNode внутри некоторого другого класса вместе с элементом данных емкостью .

  класс Стек {
    int емкость
    class ListNode {
        int val
        ListNode следующий
    }
}  

Мы будем использовать только класс ListNode ниже для простоты.

→ Давайте перейдем к операциям стека

Операция PUSH

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

  void push (int item)
{
    ListNode temp = ListNode (элемент)
    темп.next = голова
    head = temp
}  

Операция POP

Свойства связанного списка освободили нас от проверки, заполнен ли стек при операции push. Предоставляют ли они какие-либо послабления для исключений в поп-деятельности? Нам еще нужно проверить, пуста ли стопка.

Так как в этой реализации верхняя часть представлена ​​головкой . Как удалить первый элемент связного списка?

Просто, второй элемент делаем как голову.

  пустота поп ()
{
    если (голова == NULL)
        print («Стопка пуста!»)
    еще
        head = head.next
}  

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

Peek and isEmpty Operation

Реализация этих двух операций довольно проста и понятна в связанном списке.

  int peek ()
{
    если (голова == NULL)
    {
        print («Стопка пуста!»)
        возврат -1
    }
    еще
        вернуть голову.вал
}  
  bool isEmpty ()
{
    если (голова == NULL)
        вернуть True
    еще
        вернуть ложь
}  
Дополнения в стеке

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

  • isFull (): сообщает вам, если стек заполнен до его емкости
  • Операция pop может вернуть удаляемый элемент

★ Довольно интересное дополнение, которое было запрошено в Во многих интервью вас просят реализовать MinStack , который хранит все свойства обычного стека, но также возвращает минимальное значение в стеке.Поскольку ожидается, что все операции со стеком будут выполняться за постоянное время, вам необходимо вернуть минимальный элемент в стеке с временной сложностью O (1).

Приложения структуры данных стека

  • Механизм отмены в текстовых редакторах
  • Функция прямого и обратного отката в веб-браузерах
  • Проверка сбалансированных скобок в выражении
  • Оценка выражений и синтаксический анализ
  • Отслеживание с возвратом . Это процесс, когда вам нужно получить доступ к самому последнему элементу данных в серии элементов.Представьте себе лабиринт — как найти путь от входа к выходу? Как только вы зайдете в тупик, вам придется отступить. Но куда вернуться? к предыдущему пункту выбора. Следовательно, в каждой точке выбора вы сохраняете в стеке все возможные варианты. Тогда переход с возвратом просто означает выталкивание следующего варианта из стека.
  • Мы используем стек для итеративной реализации нескольких рекурсивных программ, таких как обход дерева, обход DFS в графе и т. Д.
  • Для решения нескольких проблем в алгоритмах мы используем стек как основную структуру данных, с помощью которой они организуют свою информацию .
  • Управление памятью: Любая современная компьютерная среда использует стек в качестве основной модели управления памятью для выполняющейся программы.
Предлагаемые проблемы для решения

Удачного кодирования! Наслаждайтесь алгоритмами!

Онлайн-курс по структуре данных и алгоритмам AfterAcademy — Прием открыт

Brilliant Math & Science Wiki

Для реализации структуры данных стека нам обычно требуется:

  • область памяти для хранения элементов данных
  • указатель на вершину стека
  • набор четко определенных операций: push , pop , peek и size

В этой реализации верх стека находится справа от массива.

Примечание. Стеки уже реализованы в Python, как вы можете видеть ниже. Это повторная реализация.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21 год
22
23
24
25 
  класс Стек:
    self.array = []
    self.size = 0

    def __init __ (self, array = None):
        если массив! = Нет:
            self.array = массив
            self.size = len (массив)
        еще:
            self.array = []
            себя.size = 0

    def push (self, item):
        self.array.append (элемент)

    def pop (сам):
        удалено = self.array [-1]
        self.array = self.array [0: -1]
        возврат удален

    def peek (сам):
        вернуть self.array [-1]

    размер по умолчанию (сам):
        вернуть self.size
  

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

Напишите метод, обращающий содержимое стека

Решение

Если метод не является методом экземпляра ADT стека, мы можем записать обратный как

  def reverse (стек):
  new_stack = Стек ()
  пока стек.size ()! = 0:
      new_stack.push (stack.pop ())
   вернуть new_stack
  

.