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

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

Класс Stack<T> представляет коллекцию, которая использует алгоритм LIFO («последний вошел — первый вышел»). При такой организации каждый следующий добавленный элемент помещается поверх предыдущего. Извлечение из коллекции происходит в обратном порядке — извлекается тот элемент, который находится выше всех в стеке.

Стек — довольно часто встречаемая структура данных в реальной жизни. Банальные примеры стеков — стопка книг или тарелок, где каждую новую книгу или тарелку помещают поверх предыдущей. А извлекают из этой стопки книги/тарелки в обратном порядке — сначала самую верхнюю и так далее. Другой пример — одежда: допустим, человек выходит на улицу в зимнюю погоду и для этого сначала одевает майку, потом рубашку, затем свитер, и в конце куртку. Когда человек снимает с себя одежду — он делает это в обратном порядке: сначала снимает куртку, потом свитер и так далее.

Создание стека

Для создания стека можно использовать один из трех конструкторов. Прежде всего можно создать пустой стек:

При создании пустого стека можно указать емкость стека:

Также можно инициализировать стек элементами из другой коллекции или массивом:

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

Для получения количества элементов стека применяется свойство Count .

Методы Stack

В классе Stack можно выделить следующие методы:

Clear : очищает стек

Contains : проверяет наличие в стеке элемента и возвращает true при его наличии

Push : добавляет элемент в стек в верхушку стека

Pop : извлекает и возвращает первый элемент из стека

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

Посмотрим на примере:

Работу стека можно представить следующей иллюстрацией:

Стоит отметить, что если с помощью методов Peek или Pop мы попытаемся получить первый элемент стека, который пуст, то программа выдаст исключение. Соответственно перед получением элемента мы можем проверять количество элементов в стеке:

Либо можно использовать пару методов:

bool TryPop(out T result) : удаляет из стека первый элемент и передает его в переменную result, возвращает true , если очередь не пуста и элемент успешно получен.

bool TryPeek(out T result) : передает в переменную result первый элемент стека без его извлечения, возвращает true , если элемент успешно получен.

How can I clear a stack in c++ efficiently?

I have a c++ stack named pages. As I have no clear() function to clear a stack, I wrote the following code:

Now my question: is there a better efficient way to clear the stack?

5 Answers 5

In general you can’t clear copying containers in O(1) because you need to destroy the copies. It’s conceivable that a templated copying container could have a partial specialization that cleared in O(1) time that was triggered by a trait indicating the type of contained objects had a trivial destructor.

If you want to avoid loop.

I don’t think there is a more efficient way. A stack is a well defined data type, specifically designed to operate in a LIFO context, and not meant to be emptied at once. For this you could use vector or deque (or list ), which are basically the underlying containers; a stack is in fact a container adaptor. Please see this C++ Reference for more information.

If you don’t have a choice, and you have to use stack, then there is nothing wrong with the way you do it. Either way, the elements have to be destroyed if they were constructed, whether you assign a new empty stack or pop all elements out or whatever.

I suggest to use a vector instead; it has the operations you need indeed:

• size (or resize)
• empty
• push_back
• pop_back
• back
• clear

It is just more convenient, so you can use the clear method. Not sure if using vector is really more performant; the stack operations are basically the same.

Стек: классы Stack и Stack<T>

— это контейнер, работающий по принципу «последний вошел, первый вышел» (last in, first out — LIFO). На рисунке показано представление стека, где метод Push() добавляет элемент, а метод Pop() — получает элемент, добавленный последним:

Класс коллекции, поддерживающий стек, носит название Stack. В нем реализуются интерфейсы ICollection, IEnumerable и ICloneable. Этот класс создает динамическую коллекцию, которая расширяется по мере потребности хранить в ней вводимые элементы. Всякий раз, когда требуется расширить такую коллекцию, ее емкость увеличивается вдвое.

В классе Stack определяются следующие конструкторы:

В первой форме конструктора создается пустой стек, во второй форме — пустой стек, первоначальный размер которого определяет первоначальная емкость, задаваемая параметром initialCapacity, и в третьей форме — стек, содержащий элементы указываемой коллекции col. Его первоначальная емкость равна количеству указанных элементов.

В классе Stack определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто используемых методов этого класса приведены ниже. Эти методы обычно применяются следующим образом. Для того чтобы поместить объект на вершине стека, вызывается метод Push(). А для того чтобы извлечь и удалить объект из вершины стека, вызывается метод Pop(). Если же объект требуется только извлечь, но не удалить из вершины стека, то вызывается метод Peek(). А если вызвать метод Pop() или Peek(), когда вызывающий стек пуст, то сгенерируется исключение InvalidOperationException.

Класс Stack<T> является обобщенным эквивалентом класса необобщенной коллекции Stack. В нем поддерживается стек в виде списка, действующего по принципу «первым пришел — последним обслужен». В этом классе реализуются интерфейсы Collection, IEnumerable и IEnumerable<T>. Кроме того, в классе Stack<T> непосредственно реализуются методы Clear(), Contains() и СоруТо(), определенные в интерфейсе ICollection<T>. А методы Add() и Remove() в этом классе не поддерживаются, как, впрочем, и свойство IsReadOnly. Коллекция класса Stack<T> имеет динамический характер, расширяясь по мере необходимости, чтобы вместить все элементы, которые должны в ней храниться.

Count

Свойство Count возвращает количество элементов в стеке.

Push()

Метод Push() добавляет элемент в вершину стека.

Pop()

Метод Pop() удаляет и возвращает элемент из вершины стека. Если стек пуст, генерируется исключение типа InvalidOperationException.

Peek()

Метод Peek() возвращает элемент из вершины стека, не удаляя его при этом.

Contains()

Метод Contains() проверяет наличие элемента в стеке и возвращает true в случае нахождения его там.

Урок 39. Коллекция Стек (Stack) C#

На 39 уроке учебника C# для начинающих рассматривается класс Stack. Эта коллекция включает в себя функциональные возможности, требуемые в структуре стекирования «Last In, First Out» (LIFO, последним пришёл — первым ушёл). Стеки позволяют хранить предметы для последующего извлечения и обработки.

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

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

В операционных системах и языках разработки высокого уровня часто используются стеки. Одним из ключевых применений является сохранение точек возврата для вызовов программы. Каждый раз, когда вызывается подпрограмма, адрес вызывающей функции добавляется или перемещается в стек. Когда подпрограмма завершается, последний адрес может быть извлечен или выскочил из стека, и нормальный поток программы может продолжаться из предыдущего местоположения. Более ранняя статья по обработке исключений C# содержит пример использования стека при чтении свойства StackTrace.

Коллекция Stack

Платформа .NET framework включает класс Stack. Он обеспечивает все функциональные возможности, необходимые для работы стеков LIFO без дополнительного кода. Класс Stack предоставляет простую коллекцию, которая может содержать любой тип объекта, включая дубликаты и значения null.

Реализованные интерфейсы

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

Конструкторы

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

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

Третий конструктор позволяет создать предварительно заполненный стек, содержащий объекты из любого класса, реализующего ICollection .

Стеки позволяют добавлять новые элементы в верхнюю часть стека, а затем извлекать их в обратном порядке. Чтобы добавить новый элемент в верхнюю часть стека, используйте метод Push. Этот метод принимает один параметр, являющийся объектом для добавления в стек.

Для извлечения элементов из стека вызывается метод Pop. Pop возвращает элемент из верхней части стека и удаляет его из коллекции. Элемент возвращается как объект, который может быть приведен к правильному типу. В следующем примере метод ToString используется для выполнения преобразования, когда три элемента добавляются и затем извлекаются из стека. Нельзя сказать, что порядок извлечения является обратным порядку, в котором элементы были помещены в стопку.

Иногда необходимо получить следующий элемент в стеке, не удаляя его из коллекции. Метод Peek используется таким же образом, как и Pop, но когда получается значение верхнего элемента, то он также остается в положении.

Другие методы работы со стеком

В дополнение к методам LIFO, класс Stack предоставляет другие функциональные возможности для изменения и чтения коллекции. Это увеличивает коллекцию с поведением, похожим на те, которые встречаются в некоторых других подобных типов.

Метод Clear используется для очистки содержимого стека. Метод не требует никаких параметров.

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

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

Создание потокобезопасной обертки стека

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

Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, стек, уроки по си шарп, си шарп, коллекции