10. Стек. Класс Stack<T>. Правильная скобочная последовательность.

1. Стек

Возвращаемся к структурам данных.

Еще одна очень полезная в определенном классе программ структура – стек.

Стек (англ. stack — стопка) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO («последним пришёл — первым вышел»).

Достаточно полное определение, но возможно для новичков оно будет немного трудным для понимания.

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

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

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

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

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

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

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

В классе Stack можно выделить основные методы и свойства, которые позволяют управлять элементами:

• Push: добавляет элемент в стек на первое место.
• Pop: извлекает и возвращает первый элемент из стека. Если стек пуст, генерируется исключение типа InvalidOperationException.
• Peek: просто возвращает первый элемент из стека без его удаления. Если стек пуст, генерируется исключение типа InvalidOperationException.
• Count: возвращает количество элементов в стеке.
• Contains(): проверяет наличие элемента в стеке и возвращает true в случае нахождения его там.

2. Использование стека. Пример.

Фрагмент кода программы:

var myStack = new Stack<char>();
myStack.Push('A');
myStack.Push('B');
myStack.Push('C');

Console.WriteLine("Исходный стек: ");
foreach (char s in myStack)
    Console.Write(s);
Console.WriteLine();

while (myStack.Count > 0)
{
    Console.WriteLine("Pop -> " + myStack.Pop());
}

if (myStack.Count == 0)
    Console.WriteLine("Стек пуст!");

3. Правильная скобочная последовательность.

Правильной скобочной последовательностью называется строка, состоящая только из символов "скобки" (круглых () и квадратных[]), где каждой закрывающей скобке найдётся соответствующая открывающая (причём того же типа).

Программа должна определить, является ли данная скобочная последовательность правильной.

Входные данные:

В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.

Выходные данные:

Если данная последовательность правильная, то программа должна вывести строку «yes», иначе строку «no».

Фрагмент кода программы:

Console.Write("Введите скобочную последовательность:");
string str = Console.ReadLine();

var myStack = new Stack<char>();

string answer = "yes";

for (int i = 0; i < str.Length; i++)
{
    bool isNotBracket = str[i] != '(' && str[i] != '[' && str[i] != ')' && str[i] != ']';
    if (isNotBracket)
    {
        continue;
    }

    bool isOpeningBracket = str[i] == '(' || str[i] == '[';
    if (isOpeningBracket)
    {
        myStack.Push(str[i]);
    }

    if (str[i] == ')')
    {
        if (myStack.Count == 0)
        {
            answer = "no";
            break;
        }

        if (myStack.Pop() != '(')
        {
            answer = "no";
            break;
        }
    }

    if (str[i] == ']')
    {
        if (myStack.Count == 0)
        {
            answer = "no";
            break;
        }

        if (myStack.Pop() != '[')
        {
            answer = "no";
            break;
        }
    }
}

if (myStack.Count != 0)
{
    answer = "no";
}

Console.WriteLine(answer);

Задание: Попробуйте самостоятельно изменить программу так, чтобы она работала еще и с фигурными {} скобками.

Итоги занятия.