Стек си: Реализация стека на си

Структура приложения на си

Теги: Си структура приложения, ro-data, rw-data, bss сегмент, куча, стек, сегмент кода

Сегментация приложения на си

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

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

• Сегмент данных (Data, bss-сегмент и куча)
• Стек
• Сегмент кода

Структура программы на си.

Data cостоит из статических и глобальных переменных, которые явно инициализируются значениями. Этот сегмент может быть далее разбит на ro-data (read only data) – сегмент данных только для чтения, и rw-data (read write data) – сегмент данных для чтения и записи.
Например, глобальные переменные

s[] = "hello world" 
int debug=1

Будут храниться в rw-области. Для выражения типа

const char* string = "hello world"

указатель будет храниться в rw-области, а строкой литерал «hello world» в ro-области.

static int i = 10
int i = 10

оба будут расположены в сегменте данных.

BSS-сегмент (block started by symbol) содержит неинициализированные глобальные переменные, или статические переменные без явной инициализации.
Этот сегмент начинается непосредственно за data-сегментом. Обычно загрузчик программ инициализирует bss область при загрузке приложения нулями.
Дело в том, что в data области переменные инициализированы – то есть затирают своими значениями выделенную область памяти. Так как переменные в bss
области не инициализированы явно, то они теоретически могли бы иметь значение, которое ранее хранилось в этой области, а это уязвимость, которая
предоставляет доступ до, возможно, приватных данных. Поэтому загрузчик вынужден обнулять все значения. За счёт этого и неинициализированные глобальные
переменные, и статические переменные по умолчанию равны нулю.

Куча – начинается за BSS сегментом и начиная оттуда растёт, соответственно с увеличением адреса. Этот участок используется для выделения на нём памяти с использованием
функции malloc (и прочих) и для очисти с помощью функции free.

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

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

ru-Cyrl
18-
tutorial

Sypachev S.S.
1989-04-14
[email protected]
Stepan
Sypachev

students

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Путешествие по Стеку. Часть 1 / Блог компании Smart-Soft / Хабр

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

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

Итак, начнем. Как только мы вызываем функцию, в стеке для нее создается стековый кадр. Стековый кадр содержит локальные переменные, а также аргументы, которые были переданы вызывающей функцией. Помимо этого кадр содержит служебную информацию, которая используется вызванной функцией, чтобы в нужный момент возвратить управление вызвавшей функции. Точное содержание стека и схема его размещения в памяти могут быть разными в зависимости от процессорной архитектуры и используемой конвенции вызова. В данной статье мы рассматриваем стек на архитектуре x86 с конвенцией вызова, принятой в языке C (cdecl). На рисунке вверху изображен стековый кадр, разместившийся у верхушки стека.

Сразу бросаются в глаза три процессорных регистра. Указатель стека, esp, предназначается для того, чтобы указывать на верхушку стека. Вплотную к верхуше всегда находится объект, который был добавлен в стек, но еще оттуда не снят. Точно также в реальной жизни обстоят дела со стопкой тарелок или пачкой 100-долларовых банкнот.

Хранимый в регистре esp адрес изменяется по мере того, как объекты добавляются и снимаются со стека, однако он всегда указывает на последний добавленный и еще не снятый со стека объект. Многие процессорные инструкции изменяют значение регистра esp как побочный результат своего выполнения. Реализовать работу со стеком без регистра esp было бы проблематично.

В случае с процессорами Intel, ровно как и со многими другими архитетурами, стек растет в направлении меньших адресов памяти. Поэтому верхушка, в данном случае, соответствует наименьшему адресу в стеке, по которому хранятся валидные используемые данные: в нашем случае это переменная local_buffer. Думаю, должно быть понятно, что означает стрелка от esp к local_buffer. Здесь все, как говорится, по делу – стрелка указывает точно на первый байт, занимаемый local_buffer, и это соответствует тому адресу, который хранится в регистре esp.

Далее на очереди еще один регистр, используемый для отслеживания позиций в стеке – регистр ebp – базовый указатель или указатель базы стекового кадра. Данный регистр предназначен для того, чтобы указывать на позицию в стековом кадре. Благодаря регистру ebp текущая функция всегда имеет своего рода точку отсчёта для доступа к аргументам и локальным переменным. Хранимый в регистре адрес изменяется, когда функция начинает или прекращает выполнение. Мы можем довольно просто адресовать любой объект в стековом кадре как смещение относительно ebp, что и показано на рисунке.

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

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

Теперь давайте разберем данные, содержащиеся в стековом кадре. Рисунок показывает точное побайтовое содержимое кадра, c направлением роста адресов слево-направо – это то, что мы обычно видим в отладчике. А вот и сам рисунок:

Локальная переменная local_buffer – это массив байт, представляющий собой нуль-терминированную ASCII-строку; такие строки — неизменный атрибут всех программ на C. Размер строки — 7 байт, и, скорее всего, она была получена в результате клавиатурного ввода или чтения из файла. В нашем массиве может храниться 8 байт и, следовательно, один байт остается неиспользуемым. Значение этого байта неизвестно. Дело в том, что, данные то и дело добавлются и снимаются со стека, и в этом «бесконечном танце операции добавления и снятия» никогда нельзя знать заранее, что содержит память, пока не осуществишь в нее запись. Компилятор языка C не обременяет себя тем, чтобы иницилизировать стековый кадр нулями. Поэтому содержащиеся там данные заранее неизвестны и являются в некоторой степени случайными. Уж сколько крови попило такое поведение компилятора у программистов!

Идем далее. local1 – 4-байтовое целое число, и на рисунке видно содержимое каждого байта. Кажется, что это большое число – только взгляните на все эти нули после восьмерки, однако здесь наша интуиция сослужила нам дурную службу.

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

Неплохо знать о том, что вся эта «остроконечная / тупоконечная» терминология восходит к произведению Джонатана Свифта «Путешествия Гулливера». Подобно тому, как жители Лилипутии чистили яйцо с острого конца, процессоры Intel тоже обрабатывают числа начиная с младшего байта.

Таким образом, переменная local1 в действительности хранит число 8 (да-да, прям как количество щупалец у осьминога). Что касается param1, то там во втором от начала октете изображена двойка, поэтому в результате получаем число 2 * 256 = 512 (мы умножаем на 256, потому что каждый октет – это диапазон от 0 до 255). param2 хранит число 1 * 256 * 256 = 65536.

Служебная информация стекового кадра включает в себя два компонента: адрес стекового кадра вызвавшей функции (на рисунке — saved ebp) и адрес инструкции, куда необходимо передать управление по завершении данной функции (на рисунке – return address). Эта информация делает возможным возвращение управления, и следовательно, дальнейшее выполнение программы как будто никакого вызова и не было.

Теперь давайте рассмотрим процесс «рождения» стекового кадра. Стек растет не в том направлении, которое обычно ожидают увидеть, и сначала это может сбивать с толку. Например, чтобы увеличить стек на 8 байт, программист вычитает 8 из значения, хранимого в регистре esp. Вычитание – странный способ что-либо увеличить. Забавно, не правда ли!

Возьмем для примера простенькую программу на C:

Предположим, программу запустили без параметров в командной строке. При выполнении «сишной» программы в Linux, первым делом управление получает код, содержащийся в стандартной библиотеке C. Этот код вызовет функцию main() нашей программы, и, в данном случае, переменная argc будет равна 0 (на самом деле, переменная будет равна «1», что соответствует параметру — названию, под которым запущена программа, но давайте для простоты это момент сейчас опустим). При вызове функции main() происходит следующее:

Шаг 2 и 3, а также 4 (описан ниже) соответствуют последовательности инструкций, которая называется «прологом» и встречается практически в любой функции: текущее значение регистра ebp помещается в стек, затем значение регистра esp копируется в регистр ebp, что фактически приводит к созданию нового стекового кадра. Пролог функции main() такой же, как и других функций, с той лишь разницей, что при начале выполнения программы регистр ebp содержит нули.

Если взглянуть на то, что располагается в стеке под argc, то будут видны еще некоторые данные – указатель на строку-название, под которым программа была запущена, указатели на строки-параметры, переданные через командную строку (традиционный C-массив argv), а также указатели на переменные среды и непосредствено сами эти переменные. Однако, на данном этапе нам это не особо важно, так что продолжаем двигаться по направлению к вызову функции add():

Функция main() сначала вычетает 12 из текущего значения в регистре esp для выделения нужного ей места и затем присваивает значения переменным a и b. Значения, хранимые в памяти, изображены на рисунке в шестнадцатеричной форме и с прямым порядком байтов – как и в любом отладчике. После присвоения значений, функция main() вызывает функцию add(), и та начинает выполняться:

Чем дальше, тем интересней! Перед нами еще один пролог, однако теперь уже четко видно как последовательность стековых кадров в стеке оказывается организованной в связный список, и регистр ebp хранит ссылку на первый элемент этого списка. Вот с опорой на это и реализованы трассировка стека в отладчиках и Exception-объекты высокоуровневых языков. Обратим внимание на типичную для начала выполнения функции ситуацию, когда регистры ebp и esp указывают в одно и то же место. И еще раз вспомним, что для наращивания стека осуществляется вычитание из значения, хранящегося в регистре esp.

Важно заметить следующее — при копировании данных из регистра ebp в память происходит непонятное на первый взгляд изменение порядка хранения байтов. Дело в том, что для регистров такого понятия как «порядок байтов» не существует. Иными словами, рассматривая регистр, мы не можем говорить о том, что в нем есть «старшие или младшие адреса». Поэтому отладчики показывают значения, хранимые в регистрах, в наиболее удобном для человеческого восприятия виде: от более значимых к менее значимым цифрам. Таким образом, имея стандартную нотацию «слева-направо» и «little-endian» машину, создается обманчивое впечатление, что в результате операции копирования из регистра в память байты поменяли порядок на обратный. Я хотел, чтобы картина, показанная на рисунках была максимально приближена к реальности – отсюда и такие рисунки.

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

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

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

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

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

Материал подготовлен сотрудниками компании Smart-Soft
smart-soft.ru

Как и зачем делать очередь на двух стеках / Хабр

Привет, Хабр!

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

Для начала вспомним основы:

Стек

Стек реализует принцип LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

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

• push — положить элемент на стек
• pop — достать элемент из стека

Стек обычно реализуется на массиве (еще можно на связном списке). Подробнее про стек и его реализацию можно прочитать здесь

Очередь

Очередь — это структура данных с доступом к элементам FIFO (англ. First In, First Out – «первым пришёл — первым ушёл»)

Очередь имеет два основных метода в своем интерфейсе:

• push — положить элемент в конец очереди
• pop — достать элемент из начала очереди

Подробнее про обычную очередь можно прочитать здесь.

Обычно рассматривают два базовых подхода к реализации очереди:

1. На массиве
2. На связном списке

Почему стек круче, чем очередь

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

• Поддержка минимума (min)
• Поддержка максимума (max)
• Поддержка gcd (англ. greatest common divisor — наибольший общий делитель)
• Поддержка lcm (англ. least common multiple — наименьшее общее кратное)

Все перечисленные операции ассоциативны (образуют полугруппу), но ни одна из них не имеет обратного элемента (не образует группу).

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

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

Ниже пример реализации стека с поддержкой минимума на Python:

class Stack:
    def __init__(self):
        self.stack = []

    def __bool__(self):
        return bool(self.stack)

    def push(self, elem):
        if self.stack:
            self.stack.append((elem, min(elem, self.stack[-1][1])))
        else:
            self.stack.append((elem, elem))

    def pop(self):
        return self.stack.pop()[0]

    def get_min(self):
        if not self.stack:
            return math.inf
        return self.stack[-1][1]

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

Очередь на двух стеках

Главное условие, которое должно быть выполнено — все операции должны выполняться за амортизированное O(1).

Возьмем два стека: s1 и s2.

Операцию push будем всегда делать в стек s1.

Операция pop будет устроена так: если стек s2 пустой, перекладываем все элементы из s1 в s2 последовательными вызовами pop и push. Теперь в стеке s2 лежат элементы в обратном порядке (самый верхний элемент — это самый первый положенный элемент в нашу очередь).

Если s2 не пуст, тупо достаем элементы из него. Как только s2 окажется снова пустым повторяем ту же операцию.

Код на Python:

class Queue:
    def __init__(self):
        self.s1 = Stack()
        self.s2 = Stack()

    def push(self, elem):
        self.s1.push(elem)

    def pop(self):
        if not self.s2:
            while self.s1:
                self.s2.push(self.s1.pop())
        return self.s2.pop()

    def get_min(self):
        return min(self.s1.get_min(), self.s2.get_min())

Время работы

Операция push: Мы тупо кладем элемент в стек s1. Время работы O(1).

Операция pop: Для каждого элемента мы делаем не более одного перекладывания из стека в стек, следовательно амортизированное время работы составит O(1).

Операция get_min: Для стеков s1 и s2 известны минимумы, поэтому мы просто берем минимум из минимумов. Время работы O(1).

Бонусная задачка

Дана последовательность N чисел. Задано число M Идея решения 1

Сделай очередь с поддержкой минимума и максимума.

Идея решения 2aamonster подсказал, что есть другой способ решения (читай здесь).

Заключение

Спасибо, что дочитали до конца!

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

Пишите в комментариях какие задачи на двух стеках вам приходилось решать на интервью или контестах.

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

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

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

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

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

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

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

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

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

Стек вызовов

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

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

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

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

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

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

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

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

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

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

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

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

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

Стек данных

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

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

Что дальше

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

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

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

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

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

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

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

Мой новый стек веб-технологий для 2020 года / Блог компании RUVDS.com / Хабр

Помните те времена, когда стеки веб-технологий были простыми? Когда уровни этих стеков можно было обозначить в виде четырёхбуквенного сокращения вроде LAMP, LEMP или LEPP? Когда всё, что было нужно для создания и поддержки сайтов, сводилось к вполне обычному железу, к какому-нибудь опенсорсному софту, да к упорству в достижении цели?

Мой первый успешный сайт, теперь уже старинный проект 1999 года, был создан с использованием технологий, которые можно пересчитать по пальцам одной руки: HTML4, CSS2, JavaScript3 и Apache 1.1. Всё это крутилось на сервере с Linux 2.0. Сайт включал в себя 38000 страниц. И сегодня, через 20 лет, он всё ещё их выдаёт.

С тех пор всё изменилось. Это касается и стеков веб-технологий. Теперь они совсем не те, что прежде.

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

Стек веб-технологий 2020 года

2020 год — это начало нового десятилетия. Это — время, когда стоит поговорить о новом стеке веб-технологий.

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

Меня особенно интересуют маленькие веб-сайты. Те, которые хорошо чувствуют себя на виртуальном сервере. Таким сайтам не нужны балансировщики нагрузки или постоянные хранилища данных. Это — ниша CMS, которую уже давно занимает WordPress. Но в основе всего этого лежит не некий минималистичный сервер. Вместо этого речь идёт о системе, которая может выдержать постоянный поток трафика без необходимости автоматического повышения её мощности в часы пик.

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

▍1. Облачный провайдер

Базой моего стека является облачный провайдер, который учитывает потребности тех, кто привык сам заниматься тонкими настройками сред, в которых выполняются их веб-проекты. Я пользовался собственными серверами до тех пор, пока стоимость их поддержки не стала слишком высокой. Аренда места в серверной стойке, выделенный IP-адрес, обеспечение нужной полосы пропускания… Всё это вносит вклад в месячную стоимость физического сервера. Но настоящий «вымогатель» — это стоимость электричества. Облачные провайдеры гораздо дешевле, чем $1.25 в день, которые я отправлял поставщику электроэнергии. Отказ от подобных трат позволил мне сэкономить сотни долларов в год.

▍2. Дистрибутив Fedora Linux с SELinux

Безопасность — это то, что очень сильно всех нас беспокоит. SELinux можно сравнить с мощной охранной системой, работающей в Linux. Если к этому добавить ещё и хорошо настроенный iptables-файрвол, получится то, что позволит владельцу сайта спокойно спать по ночам. Если вы не уверены в том, что вам всё это нужно — проведите следующий эксперимент. Разверните новый сервер у вашего любимого облачного провайдера и понаблюдайте за тем, как скоро его начнут атаковать. Я видел, как брутфорс-атаки на новые сервера с попытками входа по SSH начинались менее чем через 10 минут после их создания.

▍3. Веб-сервер Read Write Serve

Я пользуюсь веб-сервером Read Write Serve с TLS-сертификатами от LetsEncrypt. Раньше я был фанатом Apache, на настройку и запуск новых веб-сайтов у меня уходило буквально несколько минут. Но с тех пор, как я перешёл с PHP на JavaScript, об Apache пришлось забыть. Сервер Express казался мне чрезвычайно простым инструментом, но лишь до тех пор, пока я не попытался воспроизвести в нём весь тот функционал, который давал мне Apache. Речь идёт о механизме согласования содержимого, об условном кэшировании, о сжатии данных, о перезаписи URL для SEO, о CORS, о политиках защиты контента. В результате я и перешёл на сервер Read Write Serve, в котором все эти возможности присутствуют по умолчанию.

▍4. Среда выполнения приложений Node.js

За логику приложения, выполняющуюся на сервере, отвечает среда Node.js. Возникает такое ощущение, что в экосистеме NPM имеются пакеты на все случаи жизни. Поэтому простыми и понятными оказались задачи по сборке из имеющихся пакетов того, что нужно именно мне, и по запуску всего этого на Read Write Serve. Для организации работы всего того, что нужно современному веб-проекту, не требуется прилагать чрезмерных усилий. Это — отправка электронной почты, работа с платёжными сервисами, обращение к базам данных, и всё остальное, подразумевающее работу с серверными API.

▍5. База данных MariaDB

Я пользуюсь сервером баз данных MariaDB. Это — форк MySQL, подвергнутый ребрендингу и освоенный опенсорс-сообществом. Когда мне нужно хранить неструктурированные JSON-данные, я пользуюсь PostgreSQL. Дело в том, что это позволяет мне выполнять запросы непосредственно по конкретным JSON-свойствам. Это немного похоже на MongoDB, но основано на привычном SQL-синтаксисе.

▍6. HTTP/2

Для организации связи между частями приложений я полагаюсь на возможности HTTP/2 с поддержкой постоянных соединений и с мультиплексированием потоков. Эти два дополнения к достойному уважения протоколу HTTP/1.1. изменили мой подход к формированию документов. Во-первых, исчезла проблема блокировки начала очереди. В результате пропала необходимость в спрайт-листах даже в том случае, если у меня имеются десятки маленьких изображений. Во-вторых, теперь не нужно оптимизировать JavaScript- и CSS-файлы, объединяя их в бандлы. После того, как соединение клиента и сервера установлено, все эти маленькие файлы без перебоев передаются по этому соединению.

▍7. HTML-шаблонизация с помощью Blue Phrase

Blue Phrase — это система шаблонизации, позволяющая в компактном виде точно описывать HTML-структуры. Для меня закончились времена нечитаемой мешанины из HTML-кода и несоответствий между открывающими и закрывающими тегами. В шаблонах я обычно использую лишь незначительное количество переменных (заголовок, описание, ключевые слова, SEO-данные, экран загрузки, дата и так далее) и размещаю их в шаблоне в декларативном стиле.

▍8. Написание кода страниц с помощью Read Write Doc

Когда я создаю новые страницы, я сосредоточен на том, что пытаюсь выразить, а не на их оформлении. Для решения этой задачи я пользуюсь Read Write Doc. Этот инструмент помогает мне заниматься делом, ни на что не отвлекаясь. Я пользуюсь им даже тогда, когда то, над чем работаю, планируется опубликовать на Medium (а там есть отличный онлайновый WYSIWYG-редактор). Я отношу себя к ветеранам веб-разработки, поэтому привык к моноширинным шрифтам, и к тому, чтобы мои руки были бы на клавиатуре, а не метались бы между клавиатурой и мышкой. В любом случае, если мне нужно увидеть то, над чем я работаю, с применением к нему CSS, я могу, с помощью простой комбинации клавиш, переключаться между режимами просмотра и редактирования.

▍9. Стандартные веб-компоненты

В области работы с веб-компонентами я придерживаюсь стандартов W3C. Это — теневая DOM, пользовательские элементы, HTML-тег <template>, ECMAScript-модули. Это позволяет мне полностью включать всё, что мне нужно, в пакеты, которые я распространяю через NPM. Для меня самым большим преимуществом всего этого стал тот уровень изоляции, который предоставляет теневая DOM. Это позволило избавиться от проклятья CSS, от загрязнения пространств имён.

▍10. JavaScript для клиентских скриптов

Для написания клиентских скриптов я пользуюсь модульным объектно-ориентированным JavaScript-кодом. Я применяю новые возможности стандарта ECMAScript только тогда, когда их поддержка появляется в свежих релизах браузеров. То есть, включаю их в свой арсенал в тот момент, когда вижу, что на caniuse.com «зеленеют» все основные браузеры. Я избегаю полифиллов.

▍11. Стилизация с помощью CSS

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

<link href='/fonts/source-serif-pro-400-latin.woff2' rel=preload as=font crossorigin />

Дополнительное преимущество такого подхода заключается в том, что он полностью избавляет меня от проблемы, известной как FOUT — (flash of unstyled text, вспышка обычного шрифта).

▍12. Подготовка графических ресурсов с помощью GIMP и InkScape

И, наконец, для подготовки графических ресурсов я использую пару редакторов. Растровые PNG-изображения я готовлю с помощью GIMP, а векторные SVG-материалы — с помощью InkScape.

Технологии, которые потеряли былую привлекательность

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

Технологии, которые стали фаворитами

Вот обзор тех уровней моего технологического стека, которыми я особенно впечатлён:

• JavaScript-модули. Модули отлично зарекомендовали себя в серверном JavaScript-коде. И я безмерно рад тому, что наконец могу использовать их и на стороне клиента.
• Объектно-ориентированный JavaScript. Вот пять золотых правил объектно-ориентированной JavaScript-разработки:
  1. Заменяйте анонимные объекты именованными классами.
  2. Объявляйте и инициализируйте все свойства объектов в конструкторах.
  3. Защищайте объекты от изменений сразу после создания.
  4. Объявляйте методы с неизменными сигнатурами.
  5. Привязывайте this к каждому коллбэку.

• Blue Phrase. Эта система позволяет мне пользоваться декларативным подходом при создании шаблонов и при подготовке различных материалов. Она превращает написание качественного HTML-кода в сплошное удовольствие.

Итоги

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

Уважаемые читатели! А какой он — ваш стек веб-технологий 2020 года?

Дисклеймер от переводчика: Blue Phrase, Read Write Serve и Read Write Doc — технологии, разработанные автором данной статьи. Скачивание и установка — на ваш риск.

Стек

— Справочник по C ++

Шаблон класса

<стопка>

 template > class stack; 

Стек LIFO

Стеки — это тип адаптера контейнера, специально разработанный для работы в контексте LIFO (последним пришел — первым вышел), когда элементы вставляются и извлекаются только с одного конца контейнера.

стек s реализованы как адаптеры контейнера , которые представляют собой классы, которые используют инкапсулированный объект определенного класса контейнера в качестве своего базового контейнера , предоставляя определенный набор функций-членов для доступа к его элементам.Элементы выдвигаются, / выдвигаются, из «задней» конкретного контейнера, который известен как верхний стопки.

Базовый контейнер может быть любым из стандартных шаблонов контейнерных классов или каким-либо другим специально разработанным контейнерным классом. Контейнер должен поддерживать следующие операции:

• пустой
• размер
• задний
• push_back
• pop_back

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

Параметры шаблона

т

Тип элементов.
Псевдоним типа члена stack :: value_type .

Контейнер

Тип внутреннего контейнера , лежащего в основе объекта , в котором хранятся элементы.
Его value_type должно быть T .
Псевдоним типа члена stack :: container_type .

Типы элементов

Функции-члены

(конструктор)

Стек конструкции (общедоступная функция-член
)

пусто

Проверить, пуст ли контейнер (общедоступная функция-член
)

размер

Размер возврата (общедоступная функция-член
)

вверху

Доступ к следующему элементу (общедоступная функция-член
)

push

Вставить элемент (общедоступная функция-член
)

emplace

Построить и вставить элемент (общедоступная функция-член
)

pop

Удалить верхний элемент (общедоступная функция-член
)

swap

Swap содержимое (общедоступная функция-член
)

Перегрузки функций, не являющихся членами

операторы отношения

операторы отношения для стека (функция
)

своп (стек)

Обмен содержимым стеков (общедоступная функция-член
)

Специализации класса, не являющиеся членами

uses_allocator

Использует распределитель для стека (шаблон класса
)

.

C # Стек

• Подписывайтесь на нас

• Питон
• ASP.NET Core
• MVC
• IoC
• Веб-API
• C #
• TypeScript
• Node.js
• Больше

  ✕

  . Учебники .NET

  • ASP.NET Core
  • ASP.NET MVC
  • IoC
  • веб-API
  • C #
  • LINQ

  Учебники по скриптам

  • TypeScript
  • AngularJS 1
  • Узел.js
  • D3.js
  • jQuery
  • JavaScript

  Другие учебные пособия

  • Python
  • Sass
  • Https

  Тесты навыков

  • ASP.NET Core
  • ASP.NET MVC
  • LINQ
  • C #
  • веб-API
  • IoC
  • TypeScript
  • AngularJS
  • Node.js
  • jQuery
  • JavaScript

• Статьи
• Тесты
• Напишите нам

• Учебники по C #
• C # — Начало работы

• C # — История версий

• C # — Первая программа
• C # — Ключевые слова
• C # — Класс
• C # — переменная
• C # — неявно типизированная переменная
• C # — Типы данных
  • Числа
  • Струны
  • DateTime
• C # — Типы значений и ссылок
• C # — анонимный тип
• C # — динамические типы
• C # — Интерфейс
• C # — Операторы

• C # — операторы if else

• C # — Тернарный оператор?:

• C # — переключатель

• C # — цикл For

• C # — цикл пока

• C # — цикл Do-while

• C # — Структура

• C # — Enum
• C # — StringBuilder
• C # — частичный класс
• C # — статический
• C # — Массив
  • Многомерный массив

  • Зубчатый массив

• C # — Индексатор
• C # — Дженерики
  • Общие ограничения
• C # — Коллекции
  • ArrayList
  • Список
  • SortedList
  • Словарь
  • Хеш-таблица
  • Стек
  • Очередь
• C # — Кортеж
• C # — ValueTuple
• C # — встроенные исключения
  • Обработка исключений
  • бросить
  • Пользовательское исключение
• C # — Делегаты

• C # — События
• C # — анонимный метод

• C # — Типы, допускающие значение NULL

• C # — Ковариация

• C # — Func

• C # — Действие

.

std :: stack — cppreference.com

Класс std :: stack — это контейнерный адаптер, который дает программисту функциональность стека, в частности структуру данных LIFO (последний вошел, первый вышел).

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

[править] Параметры шаблона

[править] Типы элементов

[править] Функции-члены

[править] Функции, не являющиеся членами

[править] Вспомогательные классы

[править] Руководства по выводам (начиная с C ++ 17)

.Программа стека

на C ++ — Qaru

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

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

Загрузка…

2. Авторизоваться
   зарегистрироваться

3. текущее сообщество
   

.