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

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

Теория

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

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

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

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

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

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

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

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

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

Практика

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

Код на C++

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

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

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

Функции

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

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

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

Функцию я назову s_push, перейдем к коду.

Код на C++

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

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

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

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

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

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

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

Код на C++

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

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

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

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

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

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

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

Код на C++

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

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

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

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

Код на C++

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

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

Заключение

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

Код на C++

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

Результат выполнения

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

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

Теги: Добавить метки

Теория

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

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

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

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

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

Практика

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

Код на C++

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

Функции

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

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

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

Функцию я назову s_push, перейдем к коду.

Код на C++

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

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

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

Код на C++

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

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

Код на C++

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

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

Код на C++

Заключение

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

Код на C++

Результат выполнения

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

Память, которую используют программы, состоит из нескольких частей — сегментов :

сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Сегмент кода обычно доступен только для чтения;

сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и , инициализированные нулем;

сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные;

к уча (heap), откуда выделяются динамические переменные;

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

В этом уроке мы рассмотрим только кучу и стек, поскольку всё самое интересное происходит именно там.

Куча

Сегмент кучи (или просто «куча ») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче в .

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

int *ptr = new int; // ptr выделяется 4 байта из кучи int *array = new int; // array выделяется 40 байтов из кучи

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

int *ptr1 = new int; int *ptr2 = new int; // ptr1 и ptr2 могут не иметь последовательных адресов

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

Куча имеет свои преимущества и недостатки:

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

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

Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.

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

Стек вызовов

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

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

Структура данных «Стек»

Структура данных - это механизм в программировании для организации данных, чтобы они могли эффективно использоваться. Вы уже видели несколько типов структур данных, таких как массивы и структуры. Они обеспечивают механизмы для эффективного хранения данных и доступа к ним. Существует еще много дополнительных структур данных, которые обычно используются в программировании, некоторые из которых реализованы в стандартной библиотеке C++, и «Стек» является одним из таких.

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

Посмотреть на поверхность верхней тарелки.

Взять верхнюю тарелку из стопки (открывая таким образом следующую, которая находится снизу – если она вообще есть).

Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку — если она была).

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

Посмотреть на верхний элемент в стеке (используется функция top () или peek () ).

Вытянуть верхний элемент стека (используется функция pop () ).

Добавить новый элемент на вершину стека (используется функция push () ).

Стек – это структура типа LIFO (Last In, First Out – последним пришёл, первым ушёл). Последний элемент, помещенный на вершину стека, будет первым, который и выйдет из стека. Если вы положите новую тарелку поверх стопки других тарелок, то она будет первой, которую вы потом возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются со стека – стек уменьшается.

Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:

Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

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

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

Сегмент стека вызовов

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

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

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

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

Стек вызовов на практике

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

Программа сталкивается с вызовом функции.

Фрейм стека создается и помещается в стек, он состоит из:

Адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес »). Так процессор запоминает, куда возвращаться после выполнения функции.

Аргументов функции.

Памяти для локальных переменных.

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

Процессор переходит к точке начала выполнения функции.

Инструкции внутри функции начинают выполняться.

После завершения функции, выполняются следующие шаги :

Регистры восстанавливаются из стека вызовов.

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

Обрабатывается возвращаемое значение.

ЦП возобновляет выполнение кода (исходя из обратного адреса).

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

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

Пример стека вызовов

Рассмотрим следующий фрагмент кода:

Стек вызовов этой программы выглядит следующим образом:

boo() (включая параметр b)
main()

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

Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В Windows размер стека по умолчанию составляет 1 МБ. На некоторых других Unix-системах этот размер может достигать и 8 МБ. Если программа пытается поместить слишком много информации в стек, то это приведет к переполнению стека. Переполнение стека (stack overflow) происходит при запросе на память, в то время, когда вся память стека уже выделена — в этом случае все запросы на выделения начнут переливаться (переполняться) в другие разделы памяти.

Переполнение стека является результатом добавления слишком большого числа переменных в стек и/или создания слишком большого количества вложенных вызовов функций (например, где функция A вызывает функцию B, которая в свою очередь вызывает функцию C, а та вызывает функцию D и т.д. и т.п.). Переполнение стека обычно приводит к сбою в программе.

Например:

int main() { int stack; return 0; }

int main ()

int stack [ 100000000 ] ;

return 0 ;

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

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

void boo() { boo(); } int main() { boo(); return 0; }

Стек

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

Стек можно представить в виде трубки с подпружиненым дном, расположеной вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать элементы. Общепринятые английские термины в этом плане очень красочны, операция добавления элемента в стек обозначается push, в переводе "затолкнуть, запихнуть". Новый добавляемый элемент проталкивает элементы, помещеные в стек ранее, на одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются вверх, по-английски pop ("выстреливают").

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

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

Почему именно стек используется для сохранения состояния прерванного задания? Предположим, что компьютер выполняет задачу A. В процессе ее выполнения возникает необходимость выполнить задачу B. Состояние задачи A запоминается, и компьютер переходит к выполнению задачи B. Но ведь и при выполнении задачи B компьютер может переключиться на другую задачу C, и нужно будет сохранить состояние задачи B, прежде чем перейти к C. Позже, по окончании C будет сперва восстановлено состояние задачи B, затем, по окончании B, - состояние задачи A. Таким образом, восстановление происходит в порядке, обратном сохранению, что соответствует дисциплине работы стека.

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

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

Кроме локальных переменных, в аппаратном стеке сохраняются адреса возврата при вызовах подпрограмм. Пусть в некоторой точке программы A вызывается подпрограмма B . Перед вызовом подпрограммы B адрес инструкции, следующей за инструкцией вызова B, сохраняется в стеке. Это так называемый адрес возврата в программу A. По окончании работы подпрограмма B извлекает из стека адрес возврата в программу A и возвращает управление по этому адресу. Таким образом, компьютер продолжает выполнение программы A, начиная с инструкции, следующей за инструкцией вызова. В большинстве процессоров имеются специальные команды, поддерживающие вызов подпрограммы с предварительным помещением адреса возврата в стек и возврат из подпрограммы по адресу, извлекаемому из стека. Обычно команда вызова назывется call, команда возврата - return.

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

В Фортране-4, одном из самых старых и самых удачных языков программирования, аргументы передаются через специальную область памяти, которая может располагаться не в стеке, поскольку до конца 70-х годов XX века еще существовали компьютеры вроде IBM 360 или ЕС ЭВМ без аппаратной реализации стека. Адреса возврата также сохранялись не в стеке, а в фиксированных для каждой подпрограммы ячейках памяти. Программисты называют такую память статической в том смысле, что статические переменные занимают всегда одно и то же место в памяти в любой момент работы программы. При использовании только статической памяти рекурсия невозможна, поскольку при новом вызове предыдущие значения локальных переменных разрушаются. В эталонном Фортране-4 использовались только статические переменные, а рекурсия была запрещена. До сих пор язык Фортран широко используется в научных и инженерных расчетах, однако, современный стандарт Фортрана-90 уже вводит стековую память, устраняя недостатки ранних версий языка.

last in - first out , «последним пришёл - первым вышел»).

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

В некоторых языках (например, Lisp , Python ) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами . И т. д.

Энциклопедичный YouTube

1 / 3

Информатика. Структуры данных: Стек. Центр онлайн-обучения «Фоксфорд»

#9. Стек / 1. Ассемблер и процедуры / Программирование с нуля

Основы сетей передачи данных. Модель OSI и стек протоколов TCP IP. Основы Ethernet.

Субтитры

Программный стек

Организация в памяти

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

Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека (Stack Pointer , - SP ) обычно является регистром процессора и указывает на адрес головы стека.

Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек, SP сначала уменьшается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее увеличение содержимого SP на 1.

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

Пример реализации стека на языке С:

struct stack { char * data ; struct stack * next ; };

Операции со стеком

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push ), удаление элемента (pop ) и чтение головного элемента (peek ) .

При проталкивании (push ) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

При удалении элемента (pop ) убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент). При этом значение убранного элемента возвращается.

void push ( STACK * ps , int x ) // Добавление в стек нового элемента { if ( ps -> size == STACKSIZE ) // Не переполнен ли стек? { fputs ( "Error: stack overflow \n " , stderr ); abort (); } else { ps -> items [ ps -> size ++ ] = x ; } } int pop ( STACK * ps ) // Удаление из стека { if ( ps -> size == 0 ) // Не опустел ли стек? { fputs ( "Error: stack underflow \n " , stderr ); abort (); } else { return ps -> items [ -- ps -> size ]; } }

Область применения

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

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

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причем под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ , естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищенном режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек .