Вредоносное ПО (malware) - это назойливые или опасные программы,...
Стек - это феномен программирования и естественное решение. Стек сразу пришел в компьютерное дело и стал таким «родным», как будто именно с него все начиналось.
Без стека не работает процессор, нет рекурсии и эффективные вызовы функций организовать невозможно. Любой алгоритм может обойтись без очереди, списка, коллекции, массива или системы организованных объектов, но без памяти и стека не работает ничего, в том числе все перечисленное.
На заре начала: процессор, память и стек
Идеальная память обеспечивает адресацию прямо к значению - это уровни машины и языка высокой степени. В первом случае процессор последовательно перебирает адреса памяти и выполняет команды. Во втором случае программист манипулирует массивами. В обоих эпизодах есть:
- адрес = значение;
- индекс = значение.
Адрес может быть абсолютным и относительным, индекс может быть цифровым и ассоциативным. По адресу и индексу может находиться другой адрес, а не значение, но это детали косвенной адресации. Без памяти процессор работать не может, а без стека команд и данных - он, как лодка без весел.
Стопка тарелок - традиционная новелла о сути стека: понятие stack и перевод в общебытовом сознании. Нельзя взять тарелку снизу, можно брать только сверху, и тогда все тарелки будут целы.
Все, что последним приходит в стек, уходит первым. Идеальное решение. По сути, stack, как перевод одного действия в другое, трансформирует представления об алгоритме как последовательности операций.
Суть и понятие стека
Процессор и память - основные конструктивные элементы компьютера. Процессор исполняет команды, манипулирует адресами памяти, извлекает и изменяет значения по этим адресам. На языке программирования все это трансформируется в переменные и их значения. Суть стека и понятие last in first out (LIFO) остается неизменным.
Аббревиатура LIFO уже не используется так часто, как раньше. Вероятно потому, что списки трансформировались в объекты, а очереди first in first out (FIFO) применяются по мере необходимости. Динамика типов данных потеряла свою актуальность в контексте описания переменных, но приобрела свою значимость на момент исполнения выражений: тип данного определяется в момент его использования, а до этого момента можно описывать что угодно и как угодно.
Так, стек - что это такое? Теперь вы знаете, что это вопрос неуместный. Ведь без стека нет современного программирования. Любой вызов функции - это передача параметров и адреса возврата. Функция может вызвать другую функцию - это опять передача параметров и адреса возврата. Наладить механизм вызова значений без стека - это лишняя работа, хотя достижимое решение, безусловно, возможное.
Многие спрашивают: "Стек - что это такое?". В контексте вызова функции он состоит из трех действий:
- сохранения адреса возврата;
- сохранения всех передаваемых переменных или адреса на них;
- вызова функции.
Как только вызванная функция исполнит свою миссию, она просто вернет управление по адресу возврата. Функция может вызывать любое количество других функций, так как ограничение накладывается только размером стека.
Свойства стека
Стек - это не абстрактный тип данных, а реальный механизм. На уровне процессора - это «движок», который уточняет и дополняет работу основного цикла процессора. Как битовая арифметика, стек фиксирует простые и очевидные правила работы. Это надежно и безопасно.
Характерные свойства стека - это его размер и длина элементов. На уровне процессора все определяется разрядностью, адресацией памяти и физикой доступа к ней. Интересная особенность и традиция: стек растет вниз, то есть в сторону уменьшения адресов памяти, а память программ и данных - вверх. Это обычно, но не обязательно. Здесь важен смысл - пришел последним, а ушел первым. Это удивительно простое правило позволяет строить интересные алгоритмы работы прежде всего на языках высокого уровня. Теперь вы не будете спрашивать, стек - что это такое.
Безукоризненная работа аппаратного обеспечения уже очень давно является нормой, но на передовом крае информационных технологий идея стека обретает новые и перспективные применения.
По сути не важно, что такое стек на уровне процессора. Это естественная составляющая архитектуры компьютера. Но в программировании стек зависит от конкретного применения и способностей программиста.
Массивы, коллекции, списки, очереди... Стек!
Часто люди задают вопрос: "Стек - что это такое?". "Программирование" и "систематизация" - интересные понятия: они не синонимы, но так тесно связаны. Программирование прошло очень быстро такой длительный путь, что достигнутые вершины кажутся идеальными. Скорее всего, это не так. Но очевидно другое.
Идея стека стала привычной не только на уровне различных языков программирования, но и на уровне их конструкций и возможностей по созданию типов данных. Любой массив имеет push и pop, а понятия "первый и последний элементы массива" стали традиционными. Раньше были просто элементы массива, а сегодня есть:
- элементы массива;
- первый элемент массива;
- последний элемент массива.
Операция помещения элемента в массив сдвигает указатель, а извлечение элемента с начала массива или с его конца имеет значение. По сути это тот же стек, но в применении к другим типам данных.
Особенно примечательно, что популярные языки программирования не имеют конструкции stack. Но они предоставляют его идею разработчику в полном объеме.
При освоении программирования, рано или поздно, возникает вопрос: "Что такое стек?
".
Наиболее наглядным способом объяснения я считаю программу на языке ассемблера (не пугайтесь), которая просто добавляет данные в стек.
Стек - это структура данных присущая всей программируемой технике. Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Часто стек называют магазином - по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).
Зачем все это нужно?
Вы вряд ли сможете написать программу, которая не будет использовать функции (подпрограммы). При вызове функции в стек копируется адрес для возврата после окончания выполнения данной подпрограммы. По окончании её выполнения адрес возвращается из стека в счетчик команд и программа продолжает выполняться с места после функции.
Также в стек необходимо помещать регистры, которые используются в данной подпрограмме (в языках высокого уровня этим занимается компилятор).
Все вышесказанное характерно для так называемого аппаратного стека. Надеюсь вы догадываетесь, что такая структура данных (LIFO - last in, first out) полезна далеко не только при работе на низком уровне. Часто возникает необходимость хранить данные в таком порядке (например известный алгоритм разбора арифметических выражений основан на работе со стеком), тогда программисты реализуют программный стек.
Как это работает?
Давайте разберем работу со стеком
на примере контроллеров семейства MSP430. Я выбрал их только из-за того что у меня оказалась установленной среда для работы с ними.
В MSP430 стек основан на предекрементной схеме. Т.е. перед тем как вы записываете данные в стек он уменьшает адрес вершины стека (верхней тарелки). Бывает также постдекрементный/постинкрементный (вычитание/добавление вершины стека происходит после записи данных) и прединкрементный (перед записью адрес вершины увеличивается).
Если стек увеличивает свой адрес при записи данных, говорят о стеке растущем вверх, если же уменьшает - вниз.
За хранения адреса вершины стека отвечает регистр SP.
Как видите адрес вершины по умолчанию у нас 0x0A00.
Рассмотрим вот такую программу:
PUSH #0123h ; Помещение числа 0123h на вершину стека (TOS) ; копируем данные из памяти MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; пишем еще два числа PUSH #9250h PUSH #0000h ; выводим данные из стека POP R8 POP R9 POP R10
Что делает эта программа?
Командой PUSH мы помещаем данные 0123h в стек. Казалось бы этой командой мы запишем 0123h в память по адресу 0x0A00, но мы ведь помним, что стек у нас предекрементный. Поэтому сначала адрес уменьшается на 2 (0x0A00 - 2 = 0x09FE) и в ячейку с полученным адресом записываются данные.
Вот так выглядела память изначально:
После выполнения команды PUSH (красным выделены изменения):
Итак данные записались.
Проверим так ли это выполнив две команды пересылки (mov). Сначала получим данные из ячейки 0x0A00 и запишем их в регистр R5, а затем запишем в регистр R6 данные из ячейки 0x09FE.
После этого в регистрах будет данные:
При выполнении команд POP вершина стека будет увеличиваться на 2 при каждой команде, а в регистры R8-10 попадут данные: 0x0000, 0x9250 и 0x0123 соответственно.
При добавлении других данные память (которая все еще содержит данные, выведенные из стека) будет заполнена новыми значениями.
Проиллюстрировать работу со стеком можно так (слева на право):
Изначально адресом стека был 0x0A00, в нем хранились 0000. При выполнении PUSH верхушкой стека стала ячека ниже (с адресом 0x09FE) и в неё записались данные. С каждой следующей командой верхушка находиться ниже в памяти.
При выполнении команды POP картина обратная.
Жду ваши вопросы в комментариях.
Стек
Стек - самая популярная и, пожалуй, самая важная структура данных в программировании. Стек представляет собой запоминающее устройство, из которого элементы извлекаются в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой первым обслуживают того, кто встал в нее последним. В программистской литературе общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди и стека. Дисциплина работы очереди обозначается 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 уже вводит стековую память, устраняя недостатки ранних версий языка.
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Стек (англ. stack - стопка; читается стэк) - абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in - first out, «последним пришёл - первым вышел»).
Достаточно полное определение, но возможно для новичков оно будет немного трудным для понимания.
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга - это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере - это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Код на C++
struct comp { //Структура с названием comp(от слова component) int Data; //Какие-то данные(могут быть любыми, к примеру можно написать int key; char Data; так-же можно добавить еще какие-либо данные) comp *next;//Указатель типа comp на следующий элемент };
Новичкам возможно будет не понятно, зачем наш указатель - типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
- Стек пуст, и нужно создать его
- Стек уже есть и нужно лишь добавить в него новый элемент
Код на C++
void s_push(comp **top, int D) { //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q типа структуры comp. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем необходимое число в Data элемента if (top == NULL) { //Если вершины нет, то есть стек пустой *top = q; //вершиной стека будет новый элемент } else //если стек не пустой { q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Обозначаем, что вершиной теперь является новый элемент } }
Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top
и о том, что же означает ->
.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент - вершина, для этого пишется: *top = q; .
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
- Ячейка, которую нам нужно удалить является вершиной стека
- Ячейка, которую нам нужно удалить находится в конце, либо между двумя ячейками
Код на C++
void s_delete_key(comp **top, int N) {//функция которая принимает вершину 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
Результат выполнения
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.
Теги: Добавить метки
Теги: Стек, стек на си, реализация стека, стек на массиве, динамически растущий стек, стек на односвязном сиске
Стек
С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел.
Стек позволяет хранить элементы и поддерживает, обычно, две базовые операции:
- PUSH – кладёт элемент на вершину стека
- POP – снимает элемент с вершины стека, перемещая вершину к следующему элементу
Также часто встречается операция PEEK, которая получает элемент на вершине стека, но не снимает его оттуда.
Стек является одной из базовых структур данных и используется не только в программировании, но и в схемотехнике, и просто в производстве, для реализации технологических процессов и т.д.; стек используется в качестве вспомогательной структуры данных во многих алгоритмах и в других более сложных структурах.
Пусть, например, у нас есть стек чисел. Выполним несколько команд. Изначально стек пуст. Вершина стека – указатель на первый элемент, никуда не указывает. В случае си она может быть равна NULL.
Теперь стек состоит из одного элемента, числа 3. Вершина стека указывает на число 3.
Стек состоит из двух элементов, 5 и 3, при этом вершина стека указывает на 5.
Стек состоит из трёх элементов, вершина стека указывает на 7.
Вернёт значение 7, в стеке останется 5 и 3. Вершина будет указывать на следующий элемент – 5.
Вернёт 5, в стеке останется всего один элемент, 3, на который будет указывать вершина стека.
Вернёт 3, стек станет пуст.
Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.
Когда мы будем работать со стеком, возможны две основные и часто встречающиеся ошибки:
- 1. Stack Underflow: Попытка снять элемент с пустого стека
- 2. Stack Overflow: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)
Программная реализация
Р ассмотрим три простые реализации стека:
Стек фиксированного размера, построенный на массиве
О тличительная особенность – простота реализации и максимальная скорость выполнения. Такой стек может применяться в том, случае, когда его максимальный размер известен заранее или известно, что он мал.
Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:
#define STACK_MAX_SIZE 20 typedef int T;
Теперь сама структура
Typedef struct Stack_tag { T data; size_t size; } Stack_t;
Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.
Кладём новый элемент на стек.
Void push(Stack_t *stack, const T value) { stack->data = value; stack->size++; }
Единственная проблема – можно выйти за пределы массива. Поэтому всегда надо проверять, чтобы не было ошибки Stack overflow:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) { if (stack->size >= STACK_MAX_SIZE) { exit(STACK_OVERFLOW); } stack->data = value; stack->size++; }
Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему
T pop(Stack_t *stack) { if (stack->size == 0) { exit(STACK_UNDERFLOW); } stack->size--; return stack->data; }
И функция peek, возвращающая текущий элемент с вершины
T peek(const Stack_t *stack) { if (stack->size <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }
Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение size
Вспомогательные функции для печати элементов стека
Void printStackValue(const T value) { printf("%d", value); } void printStack(const Stack_t *stack, void (*printStackValue)(const T)) { int i; int len = stack->size - 1; printf("stack %d > ", stack->size); for (i = 0; i < len; i++) { printStackValue(stack->data[i]); printf(" | "); } if (stack->size != 0) { printStackValue(stack->data[i]); } printf("\n"); }
Заметьте, что в функции печати мы использует int, а не size_t, потому что значение len может стать отрицательным. Функция печатает сначала размер стека, а потом его содержимое, разделяя элементы символом |
Проверка
Stack_t stack; stack.size = 0; push(&stack, 3); printStack(&stack, printStackValue); push(&stack, 5); printStack(&stack, printStackValue); push(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();
Рассмотрим также ситуации, когда есть ошибки использования. Underflow
Void main() { Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); }
Void main() { Stack_t stack; size_t i; stack.size = 0; for (i = 0; i < 100; i++) { push(&stack, i); } _getch(); }
Динамически растущий стек на массиве
Д инамически растущий стек используется в том случае, когда число элементов может быть значительным и не известно на момент решения задачи. Максимальный размер стека может быть ограничен каким-то числом, либо размером оперативной памяти.
Стек будет состоять из указателя на данные, размера массива (максимального), и числа элементов в массиве. Это число также будет и указывать на вершину.
Typedef struct Stack_tag { T *data; size_t size; size_t top; } Stack_t;
Для начала понадобится некоторый начальный размер массива, пусть он будет равен 10
#define INIT_SIZE 10
Алгоритм работы такой: мы проверяем, не превысило ли значение top значение size. Если значение превышено, то увеличиваем размер массива. Здесь возможно несколько вариантов того, как увеличивать массив. Можно прибавлять число, можно умножать на какое-то значение. Какой из вариантов лучше, зависит от специфики задачи. В нашем случае будем умножать размер на число MULTIPLIER
#define MULTIPLIER 2
Максимального размера задавать не будем. Программа будет выпадать при stack overflow или stack underflow. Будем реализовывать тот же интерфейс (pop, push, peek). Кроме того, так как массив динамический, сделаем некоторые вспомогательные функции, чтобы создавать стек, удалять его и чистить.
Во-первых, функции для создания и удаления стека и несколько ошибок
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() { Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) { exit(OUT_OF_MEMORY); } out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) { free(out); exit(OUT_OF_MEMORY); } out->top = 0; return out; } void deleteStack(Stack_t **stack) { free((*stack)->data); free(*stack); *stack = NULL; }
Всё крайне просто и понятно, нет никаких подвохов. Создаём стек с начальной длиной и обнуляем значения.
Теперь напишем вспомогательную функцию изменения размера.
Void resize(Stack_t *stack) { stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) { exit(STACK_OVERFLOW); } }
Здесь, заметим, в случае, если не удалось выделить достаточно памяти, будет произведён выход с STACK_OVERFLOW.
Функция push проверяет, вышли ли мы за пределы массива. Если да, то увеличиваем его размер
Void push(Stack_t *stack, T value) { if (stack->top >= stack->size) { resize(stack); } stack->data = value; stack->top++; }
Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера
T pop(Stack_t *stack) { if (stack->top == 0) { exit(STACK_UNDERFLOW); } stack->top--; return stack->data; } T peek(const Stack_t *stack) { if (stack->top <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }
Проверим
Void main() { int i; Stack_t *s = createStack(); for (i = 0; i < 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }
Напишем ещё одну функцию, implode, которая уменьшает массив до размера, равного числу элементов в массиве. Она может быть использована тогда, когда уже известно, что больше элементов вставлено не будет, и память может быть частично освобождена.
Void implode(Stack_t *stack) { stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); }
Можем использовать в нашем случае
For (i = 0; i < 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
Эта однопоточная реализация стека использует мало обращений к памяти, достаточно проста и универсальна, работает быстро и может быть реализована, при необходимости, за несколько минут. Она используется всегда в дальнейшем, если не указано иное.
У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 2 раза (в нашем случае) требуется мало обращений к памяти, но при этом каждое последующее увеличение может привести к ошибке, особенно при маленьком количестве памяти в системе. Если же использовать более щадящий способ выделения памяти (например, каждый раз прибавлять по 10), то число обращений увеличится и скорость упадёт. На сегодня, проблем с размером памяти обычно нет, а менеджеры памяти и сборщики мусора (которых нет в си) работают быстро, так что агрессивное изменение преобладает (на примере, скажем, реализации всей стандартной библиотеки языка Java).
Реализация стека на односвязном списке
Ч то такое односвязный список, . Коротко: односвязный список состоит из узлов, каждый из которых содержит полезную информацию и ссылку на следующий узел. Последний узел ссылается на NULL.
Никакого максимального и минимального размеров у нас не будет (хотя в общем случае может быть). Каждый новый элемент создаётся заново. Для начала определим структуру узел
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag { T value; struct Node_tag *next; } Node_t;
Функция вставки первого элемента проста: создаём новый узел. Указатель next кидаем на старый узел. Далее указатель на вершину стека перекидываем на вновь созданный узел. Теперь вершина стека указывает на новый узел.
Void push(Node_t **head, T value) { Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) { exit(STACK_OVERFLOW); } tmp->next = *head; tmp->value = value; *head = tmp; }
Функция pop берёт первый элемент (тот, на который указывает вершина), перекидывает указатель на следующий элемент и возвращает первый. Здесь есть два варианта – можно вернуть узел или значение. Если вернём значение, то придётся удалять узел внутри функции
Node_t* pop1(Node_t **head) { Node_t *out; if ((*head) == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; return out; }
T pop2(Node_t **head) { Node_t *out; T value; if (*head == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; value = out->value; free(out); return value; }
Теперь вместо проверки на длину массива везде используется проверка на равенство NULL вершины стека.
Простая функция peek
T peek(const Node_t* head) { if (head == NULL) { exit(STACK_UNDERFLOW); } return head->value; }
Итерирование достаточно интересное. Просто переходим от одного узла к другому, пока не дойдём до конца
Void printStack(const Node_t* head) { printf("stack >"); while (head) { printf("%d ", head->value); head = head->next; } }
И ещё одна проблема – теперь нельзя просто посмотреть размер стека. Нужно пройти от начала до конца и посчитать все элементы. Например, так
Size_t getSize(const Node_t *head) { size_t size = 0; while (head) { size++; head = head->next; } return size; }
Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.
