Как очистить stack c

О стеке простыми словами — для студентов и просто начинающих

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

Теория

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

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

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

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

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

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

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

Практика

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

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

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

Функции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

как я могу эффективно очистить стек в c ++?

У меня есть стек C ++ с именем pages. Поскольку у меня нет функции clear () для очистки стека, я написал следующий код:

Теперь мой вопрос: есть ли более эффективный способ очистить стек? Заранее спасибо.

3 ответа

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

Если вы хотите избежать loop.

Как насчет создания подкласса std :: stack и реализации простого метода clear (), подобного этому, для доступа к базовому контейнеру c?

Я не думаю, что есть более эффективный способ. Стек — это четко определенный тип данных, специально разработанный для работы в контексте LIFO и не предназначенный для немедленной очистки. Для этого вы можете использовать vector или deque (или list ), которые в основном являются базовыми контейнерами; stack на самом деле является адаптером контейнера. Дополнительные сведения см. В этом Справочнике по C ++.

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

Я предлагаю вместо этого использовать vector ; в нем есть необходимые вам операции:

размер (или изменение размера)
опорожнить
отталкивать
pop_back
назад
Ясно

Это просто удобнее, поэтому вы можете использовать метод clear . Не уверен, что использование vector действительно более производительно; стековые операции в основном такие же.

Stack<T>.Clear Метод

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

Удаляет все объекты из Stack<T>.

Примеры

В следующем примере кода демонстрируется несколько методов универсального Stack<T> класса, включая Clear метод.

В примере кода создается стек строк с емкостью по умолчанию и используется Push метод для отправки пяти строк в стек. Перечисляются элементы стека, которые не изменяют состояние стека. Метод Pop используется для получения первой строки из стека. Метод Peek используется для просмотра следующего элемента в стеке, а затем Pop метод используется для его выключения.

Метод ToArray используется для создания массива и копирования элементов стека в него, затем массив передается Stack<T> конструктору, который принимает IEnumerable<T>, создавая копию стека с порядком элементов, обратным. Отображаются элементы копии.

Создается массив в два раза больше размера стека, а CopyTo метод используется для копирования элементов массива, начиная с середины массива. Stack<T> Конструктор снова используется для создания копии стека с обратным порядком элементов. Таким образом, три пустых элемента находятся в конце.

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