Понятие стека. Класс «Стек из символов»

Рассмотрим один из распространенных примеров объектно-ориентированного программирования – класс, который реализует хранение данных в стеке во время работы программы.

Модель стека:

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

Хранение данных стека обеспечивается на основе закрытого (private) массива. Операции помещения данных в стек и извлечения из него доступны через public-методы.

// Класс Stack для хранения символов:

Class Stack

{

char [ ] mas; //Закрытый массив символов

Int tos; //Индекс вершины стека

// Конструктор класса с параметром size:

Public Stack(int size)

{

mas = new char[size];//Выделим память массиву

tos = 0;

}

// Метод помещения символа в Stack:

public void Push(char simb)

{

if (tos == mas.Length)

{

Console.WriteLine("Стек полон!");

return;

}

mas[tos] = simb;

tos++;

}

// Метод извлечения символа из Stack'a:

Public char Pop()

{

if (tos == 0)

{

Console.WriteLine("Стек пуст!");

return (char)0;

}

tos--;

return mas[tos];

}

// Дополнительные методы, предоставляющие информацию о стеке:

// Метод, возвращающий true, если стек полон:

public bool Full() { return tos == mas.Length; }

// Метод, возвращающий true, если стек пуст:

public bool Empty() { return tos == 0; }

// Метод, возвращающий объём стека:

public int Capacity() { return mas.Length; }

// Метод, возвращающий текущее количество элементов в стеке:

public int Get_num() { return tos; }

}

Протестируем класс Stack.

//В Main():

Stack Stk1 = new Stack(10);

int i = 0;

char simb;

Console.WriteLine("Помещаем первые 10 символов английского алфавита!");

for (i = 0;!Stk1.Full(); i++)

Stk1.Push((char)('A' + i));

If (Stk1.Full())

Console.WriteLine("Стек Stk1 полон!");

else Console.WriteLine("Стек Stk1 ещё не полон!");

//Выполнить!

Console.WriteLine("Объём стека Stk1=" + Stk1.Capacity());

//Выполнить!

//Выведем Stk1 на экран:

Console.WriteLine("Содержимое стека Stk1:");

while (!Stk1.Empty())

{

simb = Stk1.Pop();

Console.WriteLine(simb);

}

Console.WriteLine();

If (Stk1.Empty())

Console.WriteLine("Стек Stk1 пуст!");

Else

Console.WriteLine("Стек Stk1 не пуст!");

//Выполнить!

Стек Stk1 будет пуст.

Допустим нужно создать ещё один стек, хранящий буквы от ‘A’ до ‘J’, на базе первого стек. Для этого нужно снова заполнить стек Stk1, а затем переместить все элементы в Stk2:

//В Main():

Stack Stk2 = new Stack(10);

Console.WriteLine("Снова помещаем первые 10 букв в Stk1!");

for (i = 0;!Stk1.Full(); i++)

Stk1.Push((char) ('A' + i));

while (!Stk1.Empty())

{

simb = Stk1.Pop();

Stk2.Push(simb);

}

If (Stk1.Empty())

Console.WriteLine("Стек Stk1 пуст!");

Else

Console.WriteLine("Стек Stk1 не пуст!");

//Выполнить!

Стек Stk1 снова станет пустым. В Stk2 символы будут расположены в обратном порядке.

Чтобы вывести содержимое стека Stk2 на экран, желательно разработать метод Show(), который не будет использовать метод Pop()– извлечение элемента из стека. Метод Pop() при работе в цикле опустошает стек.

//В классе Stack:

Public void Show()

{

for (int i = mas.Length - 1; i >= 0; i--)

Console.WriteLine(mas[i]);

Console.WriteLine();

}

Этот метод будет выводить на экран текущий объект-стек, т.е. тот объект, который вызвал метод. Можно разработать более универсальный, перегруженный метод Show(), который выводит любой стек на экран, а не только текущий. Для этого метод Show() должен иметь параметр Stack Ob.

public void Show(Stack Ob)

{

for (int i = mas.Length - 1; i >= 0; i--)

Console.WriteLine(mas[i]);

Console.WriteLine();

}

//В Main():

Console.WriteLine("Содержимое стека Stk2:");

Stk2.Show();

// ИЛИ Stk1.Show(Stk2);

//Выполнить!

Примечание: Массив, хранящий данные стека, после выполнения метода Show() останется в памяти заполненным, ненулевым!

Усилим класс Stack, добавим в него конструктор копирования или конструктор-копировщик. Такой конструктор позволяет создать один стек на основе другого.

//В классе Stack:

public Stack(Stack Ob)

{

mas=new char [Ob.Capacity()]; //Массиву выделена память

//Копируем элементы из объекта-параметра в создаваемый объект:

for (int i=0; i<Ob.tos; i++)

mas[i]=Ob.mas[i];

tos=Ob.tos; // tos - вершина

}

//В Main():

Создадим стек Stk3 на базе стека Stk2:

Stack Stk3 = new Stack(Stk2);

Console.WriteLine("Содержимое стека Stk3:");

Stk3.Show();

//Выполнить!

Стеки Stk2 и Stk3 – это отдельные объекты, хотя и идентичны по своему содержанию.