Коллекция Stack<T>

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

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

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

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

Stack<string> people = new Stack<string>();

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

Stack<string> people = new Stack<string>(16);

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

var employees = new List<string> { "Tom", "Sam", "Bob" };
Stack<string> people = new Stack<string>(employees);
foreach (var person in people) Console.WriteLine(person);

Console.WriteLine(people.Count); // 3

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

Bob
Sam
Tom
3

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

Методы Stack

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

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

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

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

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

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

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

var people = new Stack<string>();
people.Push("Tom");
// people = { Tom }
people.Push("Sam");
// people = { Sam, Tom }
people.Push("Bob");
// people = { Bob, Sam, Tom }

// получаем первый элемент стека без его удаления 
string headPerson = people.Peek();
Console.WriteLine(headPerson);  // Bob

string person1 = people.Pop();
// people = { Sam, Tom }
Console.WriteLine(person1);  // Bob

string person2 = people.Pop();
// people = { Tom }
Console.WriteLine(person2);  // Sam

string person3 = people.Pop();
// people = { }
Console.WriteLine(person3);  // Tom

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

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

if(people.Count > 0)
{
    var person = people.Peek();
    people.Pop();
}

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

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

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

Применение методов:

var people = new Stack<string>();
people.Push("Tom");
// people = { Tom }

// удаляем элементы
var success1 = people.TryPop(out var person1);  // success1 = true
if (success1) Console.WriteLine(person1); // Tom

var success2 = people.TryPeek(out var person2);  // success2 = false
if (success2) Console.WriteLine(person2);