webdonsk.ruКак сделать стек в c
Добавил пользователь Дмитрий К. Обновлено: 10.09.2024
Настоящая статья — первая из цикла, состоящего из четырёх статей, посвящённых разработке стека — достаточно известной и простой структуры данных. Несмотря на её простоту, можно придумать немалое количество разнообразных функций, предназначенных для обработки стека, а некоторые из них могут быть реализованы различными способами. Разработка этих функций — отличный способ попрактиковаться в программировании.
Цикл статей может оказаться полезным тем, кто уже достаточно неплохо разбирается в языке C99 и кого не пугают такие понятия, как указатель, адрес переменной и динамическое распределение памяти. К слову сказать, указателей в нашем коде будет предостаточно, так что возможность поупражняться в построении не самых простых программных конструкций у нас будет.
Стеком называется контейнер, предназначенный для хранения элементов произвольного типа. Особенностью стека является то, что элементы добавляются в него последовательно, а извлекаются в порядке, обратном тому, в котором были добавлены.
Отличной иллюстрацией стека является стопка тарелок, символизирующих элементы стека. В любой момент времени нам доступна только одна тарелка — та, которая поставлена на стопку последней, т. е. верхняя. Для того, чтобы получить доступ к произвольной тарелке внутри стопки, необходимо сначала последовательно снять все тарелки, находящиеся над ней.
По аналогии со стопкой тарелок применительно к стеку говорят о верхнем элементе (том, который добавлен последним) и нижнем элементе (добавленном первым). Отметим ещё, что принцип работы стека кратко описывается аббревиатурой LIFO — last in - first out (первым вошёл - последним вышел, англ.).
Для хранения стеков в памяти компьютера наиболее часто используются массивы и односвязные списки. Преимущество первых перед последними заключается в том, что операции помещения элемента на вершину стека (т. н. проталкивание) и получения верхнего элемента одновременно с его удалением (выталкивание) в случае массивов выполняются быстрее, чем в случае с односвязными списками, т. к. не требуют динамического выделения и освобождения памяти. Эти же операции, реализованные для односвязных списков, как правило, основаны на динамическом распределении памяти.
С другой стороны, при использовании массивов необходимо знать заранее, хотя бы приблизительно, количество элементов, которые будут храниться в стеке, поскольку размер массива всегда фиксирован. В отсутствии такой информации, размер массива приходится выбирать "с запасом", что может привести к неиспользованию существенного объёма зарезервированной памяти. Односвязные списки в этом отношении являются более гибкими: в ходе операций проталкивания и выталкивания они динамически меняют свой размер. Наш стек будет построен на основе односвязного списка.
Непустой односвязный список представляет собой упорядоченный набор узлов — переменных определённого типа, хранящихся в памяти компьютера. Каждый узел, кроме последнего, содержит указатель на следующий за ним узел. Последний же узел в качестве указателя на последующий содержит ноль. Помимо этого, каждый из узлов является контейнером для хранения некоторой информации. Заметим, что односвязный список может быть пустым, т. е. может не содержать ни одного узла.
Наш стек будет универсальным, т. е. он будет поддерживать данные любых типов. Поэтому его элементами будут являться адреса переменных произвольного типа, для хранения которых будут использованы нетипизированные указатели (т. е. указатели типа void * ).
Каждый узел списка будет являться контейнером для указателя, содержащего элемент стека, а также для указателя на следующий узел. В первом узле списка будет храниться верхний элемент стека, во втором - второй сверху и т. д. Наконец, в последнем узле будет содержаться нижний элемент стека. Для представления узлов создадим следующую структуру:
Таким образом, каждый узел списка будет являться переменной типа node .
Что касается самого стека, то отдельный тип данных для его представления мы создавать не будем. Для того, чтобы получить доступ к стеку, достаточно иметь указатель на первый узел списка, т. е. тот, в котором содержится верхний элемент стека. Такой указатель будем в дальнейшем называть, для определённости, стековой переменной. Для создания пустого стека достаточно объявить стековую переменную, например, под именем stack , и присвоить ей нулевое значение:
Теперь мы можем наполнять созданный стек элементами с помощью функции push() . Стоп! Но ведь эту функцию мы ещё не создали! Ну так давайте создадим!
Функция push()
Но перед созданием функции push() напишем вспомогательную функцию pmalloc() , которая будет вызываться из push() .
Проталкивание элемента в стек влечёт за собой необходимость создания нового узла списка, в котором будет храниться этот элемент. Память для данного узла будет выделяться динамически с помощью функции malloc() из стандартной библиотеки . Эта функция возвращает адрес выделенного участка памяти, если выделение прошло удачно или нулевой адрес в противном случае. Таким образом, перед использованием этого адреса необходимо убедиться в том, что он отличен от нуля.
Ниже размещён код функции pmalloc() (префикс p в названии функции происходит от слова "protected"):
Ну а теперь можно перейти к созданию функции p u s h ( ) .
Функция push() будет принимать в качестве аргументов значение стековой переменной ( stack ) и элемент, который требуется протолкнуть в стек ( element ). В результате выполнения функции будет динамически выделяться память для нового узла списка, в него будут помещаться новый элемент стека и адрес следующего узла. Последний будет браться из формального параметра stack , который теперь уже будет указывать не на первый узел списка, а на второй. Функция возвращает новое значение стековой переменной, которым теперь будет являться адрес только что созданного узла. Вот код функции:
Поместить новый элемент в стек можно, например, следующим образом:
Следующая функция будет выталкивать из стека верхний элемент.
Функция pop()
Функция pop() возвращает верхний элемент стека и удаляет узел списка, содержащий этот элемент. Разумеется, стековая переменная, связанная с обрабатываемым стеком, должна после выполнения функции указывать на узел, следующий за удалённым. Однако функция возвратить новое значение стековой переменной уже не может. Поэтому мы предоставим функции возможность самой изменить значение стековой переменной, передав в функцию её адрес. Если к моменту вызова стек уже пустой, то функция возвращает ноль. Ниже приведён код функции pop() .
Получить вытолкнутый элемент стека можно, например, так:
Заметим, что функции push() и pop() "берут на себя" динамическое выделение памяти для узлов списка и её освобождение. Что касается переменных, адреса которых содержатся в стеке, то "забота" о памяти, в которой хранятся эти переменные, полностью ложится на плечи пользователя стека. Впрочем, заботиться о своевременной очистке памяти нужно лишь в случае её динамического распределения. Если же память выделяется автоматически, то, разумеется, думать о её "ручном" освобождении не приходится.
Мы реализовали функции, осуществляющие основные операции со стеком: проталкивание и выталкивание элементов. Однако, к основным операциям часто относят также просмотр верхнего элемента без его удаления из стека. Давайте реализуем соответствующую функцию.
Функция peek()
Функция peek() принимает в качестве аргумента значение стековой переменной и возвращает верхний элемент стека, не удаляя его. Если стек пуст, то возвращается ноль. Реализация весьма проста:
Не менее прост и пример использования функции:
На этом с основными функциями мы закончили. Во второй части будут реализованы некоторые дополнительные функции для работы со стеком. Там же будет размещена ссылка на скачивание исходного кода, опубликованного в обеих статьях.
Доброго времени суток! Сегодня мы посмотрим на реализацию совсем простой вещи — собственного стека на базе массива и на базе линейного списка. Код был мной написан на втором курсе, достаточно давно, перед написанием статьи я сдул с него пыль и немного подкорректировал страшные названия переменных, навел марафет. Теперь его можно показывать, хоть и осторожно.
Кратко о том, что такое стек. Это такой тип данных, в котором они организованны по принципу LIFO(last in — first out). По русски говоря, последним пришел, первым вышел. Отличный пример для визуализации это книжная стопка, верхняя книга последняя пришла и, если вы не собираетесь пугать кошку грохотом, первая ушла.
Реализация простейших структур данных — это отличный способ их изучить. Можно прочитать сотню книг про стек, но пока вы его не напишите самостоятельно, вы не подружитесь. Я писал реализацию на языке программирования С++, используя классы. Два стека — два класса и при большом желании можно запаковать их в отдельный файл и подключать к другим проектам.
Функции работы со стеком
push — положить элемент на вершину стека;
pop — убрать элемент с вершины;
top — вернуть элемент на вершине, не убирая его оттуда;
size — вернуть размер стека.
Реализация стека на базе массива
Смысл в том, что данные хранятся в обычном массиве, но доступ к ним строго регулируется нами с помощью функций. Огромный недостаток в том, что размер стека ограничен. Она решается с помощью расширяемых массивов. Когда место в массиве кончается, просто выделяется новый участок памяти большего размера и все копируется туда. Насколько мне известно, в библиотеке STL стек реализован именно на расширяемых массивах.
Исходный код на C++
Реализация стека на базе линейного списка
Линейный список это очень популярная структура данных, даже не смотря на то, что не очень быстрая. Очень часто встречается в реализации системных функций. Скорость работы компенсируется гибкостью. Список используем односвязный, реализуем минимальный набор функций, о которых я говорил ранее. Неоспоримое преимущество перед массивом — максимальный размер стека не ограничен.
Исходный код на C++
Тестирование производительности
Реализовали два стека, грех с ними не побаловаться. Давайте посмотрим, какой из них работает быстрее. И сравним скорость их работы со стеком из STL , а вдруг нам удалось реализовать быстрее?
Функция тестирования
Результат
Заключение
Такой размер стека был выбран экспериментально, при большем размере моя система просто падала, весь системный ресурс уходил в тест(подозреваю, что это косяк убунты). Что мы видим? Наш стек на базе массива всех уделал, и это не удивительно, ведь STL-стек расширяемый, и бог знает, сколько ресурсов он потратил на расширения в этом тесте. Наш стек на массиве оказался самым быстрым, но совершенно не гибким. В принципе, если размер входных данных заранее известен и неизменяем, можно воспользоваться и этой реализацией.
Тема избита и стара, как мир, но я внес свою лепту. Не пропадать же коду, верно? Надеюсь, что кому нибудь пригодится мой опыт, спасибо за внимание!
Здравствуйте!
Есть вопросик.
Задача создать стек (без использования массива) и реализовать функции работы с ним (просмотр содержимого стека, удаление элемента и т.д.).
Сделал я так:
Создал структуру, которая будет являться ячейкой стека (в ней будет содержаться число и указатель на следующую ячейку).
Далее я задумал написать void-функцию "add", создающую стек и добавляющую элемент в него, и тут у меня возник вопрос.
А как передать вершину в функцию add и как в функции обозначить параметр ?
Логика мне подсказывает, что если я передам функции указатель на вершину, стек бы изменялся только внутри функции add, а в main вершина так бы и осталась нулевой(NULL).
Знакомый подсказал копать в сторону ссылок и дал мне такой пример
Связаться с ним возможности не будет несколько дней.
Помогите понять его пример.
Как я понял тут передаётся в функцию add ссылка на адрес вершины, но тогда почему параметром в функции является указатель на указатель ?
Реализовать стек и 3 оператора для работы с ним
Доброго времени суток! Помогите, есть такая задача: Реализовать стек и 3 оператора для работы.
Массив: С помощью одномерного массива организовать стек и реализовать набор команд для работы с ним.
С помощью одномерного массива организовать стек и сделать следующие действия с ним: Элементами.
Организовать стек из однородного массива и реализовать действия с ним
Здравствуйте, я только что зарагестрировался на форуме и не знаю всех правил, так что прошу.
И снова здравствуйте. Решил забросить идею создания стека пока хоть мало мальски не разберусь в этом.
Вроде много литературы по стеку прочёл, а на практике что-то не получается.
Суть задания создать стек (без использования массива) и реализовать функции работы с ним (см. код).
Вот, что я написал:
P.s. Работоспособность остальных функций помимо вывода стека, добавления и удаления элемента не проверял, но думаю там есть косяки. Да и ещё пока не написал проверку переполнения стека.
Если можно, пожалуйста, покажите на мои косяки в коде.
Теперь если элемент один в стеке, то он нормально удаляется и стек считается пустым, также если в стеке более одного элемента и пользователь хочет удалить элемент,являющейся вершиной, то всё прекрасно удаляется.
Например: стек 5432 => после удаления 432.
Всё ещё осталась проблема,как удалить элемент, являющийся не вершиной стека ? Т.е. хочется удалить из стека 5432, например 3. Не понимаю как это сделать и возможно ли вообще ?
Структуры данных, которые мы рассмотрим на этом уроке, объединены тем, что создаются на основе массивов для эффективного решения определенного круга задач. В язык C++ структуры данных стек, очередь и куча можно реализовать на основе классов контейнеров vector и deque . С вектором мы познакомились ранее, настало время познакомиться с деком.
Дек, двусвязная очередь (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов массива. Это позволяет многие задачи решать непосредственно с помощью дека, абстрагируясь до нужной структуры данных.
Контейнер deque очень похож на vector . deque также является последовательным контейнером произвольного доступа, следовательно, поддерживается индексация ( [] , at() ), методы front() и back() , а также большинство других методов класса vector . Дек имеет аналогичные итераторы, в том числе, реверсивные. Но, в отличие от vector , расширение deque происходит более эффективно, т. к. перераспределение памяти не происходит (элементы не переносятся в новую область, в случае переполнения текущей). Дек более сложная структура данных, его элементы не всегда находятся в одной области памяти. Если вектор можно сравнить с С-массивом, то дек можно представить как комплект нескольких С-массивов (один или более), используемых как единый объект.
Главное отличие deque от (как vector ) в том, что он открыт с обоих концов. Вставка элементов в начало и в конец deque осуществляется очень быстро. Но обход дека с помощью итераторов, будет осуществляться медленнее, чем обход вектора. При каждой вставке и удалении не в начало или не в конец дека приведет к недействительности итераторов как начала, так и конца (в том числе, указателей и ссылок на остальные элементы). Если вставка производится в начале или в конце массива, то недействительными окажутся только итераторы, ссылки же и указатели останутся в силе.
Для контейнера deque не определены методы работы с объемом capacity() и reserve() , но метод shrink_to_fit() использовать можно. Связано это с тем, что при уменьшении размера дека, объем его не уменьшается. Этот метод необязательно выполняет операцию уменьшения capacity() до size() .
| Метод | Описание |
|---|---|
| clear | Очищает контейнер (объем не будет изменен) |
| insert | Вставляет элементы |
| emplace | Создает элементы на месте. Не использует копирование или перемещение. |
| emplace_back | Создает элементы на месте в конце массива |
| emplace_front | Создает элементы на месте в начале массива |
| erase | Удаляет элементы |
| push_back | Добавляет элемент в конце |
| pop_back | Удаляет последний элемент |
| push_front | Добавляет элемент в начале |
| pop_front | Удаляет первый элемент |
| resize | Изменяет размер массива |
| assign | Заменяет содержимое на новое |
Решим с помощью дека следующую задачу.
Задача 1. Дан массив ar и числа m и n , определяющие позиции элементов в массиве ar ( m ). Определить на этом отрезке минимальный элемент. Задачу эту решить с помощью дека.
Структура данных stack (стек)
| Метод | Описание |
|---|---|
| empty | Возвращает true , если stack пуст |
| size | Количество элементов в стеке |
| top | Доступ по ссылке к верхнему элементу |
| push | Вставляет элемент в вершину |
| emplace | Создание элемента на месте с добавлением в вершину |
| pop | Удаляет элемент с вершины |
| swap | Обменивает содержимое |
Помимо этих методов, поддерживаются все операции сравнения и операция присваивания.
Рассмотрим одну из задач, которую легко можно решить с помощью стека.
Задача 2. В постфиксной записи арифметического выражения операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B + . Запись B C + D * обозначает (B + C) * D , а запись A B C + D * + означает A + (B + C) * D . Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операций для своего чтения.
Дано выражение в постфиксной записи, содержащее числа, операции + , – , * . Вычислите значение выражения, записанного в постфиксной форме (называемой также обратной польской записью). Числа и символы должны разделяться одним пробелом.
Структура данных queue (очередь)
| Метод | Описание |
|---|---|
| empty | Возвращает true , если очередь пуста |
| size | Количество элементов в очереди |
| front | Доступ по ссылке к первому элементу |
| back | Доступ по сылке к последнему элементу |
| push | Вставляет элемент в конце очереди |
| emplace | Создание элемента на месте в конце очереди |
| pop | Удаляет первый элемент |
| swap | Обменивает содержимое |
Помимо этих методов, поддерживаются все операции сравнения и операция присваивания.
Очередь нашла свое применение в алгоритмах так называемого обхода дерева (или графа) в ширину (англ. breadth-first search, BFS ). Не вдаваясь глубоко в теорию графов, рассмотрим пример такой задачи на основе задачи ЕГЭ.
Задача 3. Вася, решая задачи формата ЕГЭ, дошел до задачи об исполнителе:
«У исполнителя Калькулятор две команды:
Структура данных heap (куча). Очередь с приоритетом (priority queue)
Куча (другие названия: двоичная куча, пирамида, сортирующее дерево) — это структура данных представленная в виде дерева. В классической куче нет ограничений на число потомков, но на практике их всегда два. Поэтому такую кучу называют двоичной кучей. Она удовлетворяет свойству кучи: если B является узлом-потомком узла A , то ключ A >= ключ B . Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (максимальными кучами).
Для двоичного дерева кучи должны выполняться три условия:
Для реализации кучи можно взять любой последовательный контейнер или C-массив. Корневой элемент — A[0] , а потомки элемента A[i] — A[2*i+1] и A[2*i+2] .
Тогда индексы, в виде дерева, можно представить следующим образом:
Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом ( priority queue ). Очередь с приоритетом применяется в программах, которые включают в себя поиск максимального (или минимального) элемента в некотором массиве данных (например, самые активные пользователи социальной сети). Но это не единственное её применение. С помощью очереди с приоритетом можно организовать планировщик задач, поиск оптимальных путей, прогнозирование событий и многие др. задачи.
priority_queue
priority_queue (наряду с очередью и стеком) является адаптером контейнеров. В основе очереди с приоритетом находится, по умолчанию, контейнер vector (это может быть изменено, как и для других адаптеров). priority_queue предупреждает случайное аннулирование кучи. Элементы очереди сортируются автоматически по убыванию (max-куча). Направление сортировки можно изменить с помощью компаратора.
Для priority_queue (заголовок - queue ) определены следующие методы:
| Метод | Описание |
|---|---|
| empty | Проверяет пуст ли базовый контейнер |
| size | Количество элементов в очереди |
| top | Доступ по ссылке к вершине |
| push | Вставляет элемент и сортирует базовый контейнер |
| emplace | Создаёт элемент на месте и сортирует базовый контейнер |
| pop | Удаляет элемент в вершине |
| swap | Обменивает содержимое |
С помощью кучи можно осуществить пирамидальную сортировку. Она выполняется путем вставки всех элементов последовательности в кучу и, затем, извлечением всех элементов кучи от наибольшего значения по порядку. Рассмотрим два варианта. Первый вариант основан на использовании priority_queue . Минус варианта - это вывод (или иная операция) с удалением элементов.
В priority_queue C++ реализована max-куча. В ней, как уже было сказано, элементы упорядочены от большего к меньшему. Чтобы изменить направление сортировки, в шаблонном параметре конструктора передаётся, помимо типа элементов, еще два необязательных элемента: тип базового контейнера и компаратор, изменяющий направление сортировки на обратное (см. стр. 18 в программе 9.6.4; в качестве компаратора выступает встроенная функция сравнения или функтор - greater ).
Этот способ также накладывает ограничение на использование контейнеров. Так, например, в этой программе нельзя заменить вектор на array , поскольку последний не поддерживает операцию insert .
Второй вариант основан на использовании библиотеки обобщенных алгоритмов.
После выполнения сортировки, массив утрачивает свойство кучи.
Решим следующую задачу.
Задача 4. В игре участвуют N игроков ( N >= 3 ). В каждом раунде пользователи по очереди бросают кость. Результаты суммируются по каждому раунду, количество которых не ограничено. По итогам игры выявляются три участника с максимальным результатом. Абсолютным победителем является игрок, первым набравший более 20 очков.
Читайте также: