Навигация
RSS
Опрос
Стеки. Часть 1
В современной литературе, посвященной обучению программированию, обсуждение вопросов, касающихся структур данных, стало встречаться крайне редко. И часто случается, что человек, прочитавший не одну книгу по какой-нибудь Delphi, довольно отдаленно представляет себе, что такое стеки и очереди, односвязные или двусвязные списки и т.п.
В этом цикле статей мы рассмотрим стеки. Сначала дадим общее определение, потом попробуем реализовать собственный класс стека. В конце напишем классическое приложение для демонстрации работы стека – проверка правильности расстановки скобок в выражении. Так же немного коснемся класса TStack, уже реализованного в Delphi.
Стек
Стек – это структура данных, доступ к которым осуществляется лишь с одного конца, называемого вершиной стека. То есть получить элемент можно только, тот, который лежит на вершине стека, а что бы взять следующий, первый нужно вытолкнуть.
Добавление (проталкивание) элемента возможно только на вершину стека, при этом добавляемый элемент сам становиться верхним. Удаление (выталкивание), так же возможно только с вершины. В общем, доступ в стеке есть лишь к верхнему элементу.
Реализация стека
Вообще, конечно, самому писать класс стека это изобретение велосипеда. В Delphi уже есть стеки на все случаи жизни, но это полезно в образовательных целях.
Для начала нужно выбрать структуру, на которой будет строиться стек. Как правило, это либо односвязные списки, либо массивы. Поскольку в Delphi есть динамические массивы, и с ними работать довольно удобно, то их и можно использовать как основу стека.
Так же необходимо решить какого типа данных будет элементы в стеке. Хотелось, что бы он был универсальным и подходил для любого типа. Эту проблему могут решить введенные в последних версиях Delphi шаблоны (generetic), но их рассмотрение выходит за рамки статьи. Без них остается всего лишь вариант: в качестве элементов стека использовать указатели, что позволит работать с любым типом, будь это хоть integer, хоть какой-нибудь TLabel. Но работа с указателями довольно опасна, и чревата как минимум утечками памяти.
Другим решением может являться, то, что стек будет лишь для хранения объектов, тогда тип элементов будет TObject и мы сможем гарантировать уничтожение элементов при уничтожении стека. Правда, тогда невозможно будет использовать стек для простых типов данных, таких как числа или символы. Но все, же мы остановимся именно на этом варианте, так как он несколько проще.
Создадим новый unit, к примеру, StStack и подключим необходимые библиотеки. Сам класс стека назовем TStStack (так как, TStack уже есть в Delphi).
Поскольку стек строится на основе динамического массива, то сам этот массив сделаем private полем класса. Добавим методы:
- Push– проталкивание элемента в стек.
- Pop– выталкивание элемента из стека.
- Peek– получение элемента с вершины стека (так же как Pop, но без удаления)
- Clear – очистка стека.
Кроме того добавим доступнее только для чтения, свойство Count для получения количества элементов.
- unit StStack;
- interface
- uses
- Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
- Dialogs, StdCtrls;
- type
- TStStack = class
- private
- FItems: array of TObject;
- public
- procedure Push( newObject: TObject );
- function Pop(): TObject;
- function Peek(): TObject;
- procedure Clear();
- function GetCount(): integer;
- property Count: integer read GetCount;
- destructor Destroy;
- end;
- implementation
- end.
Прежде чем перейти к реализации методов, нужно решить с какой стороны массива будем работать, то есть что будет являться вершиной: первый или последний элемент? Ответ, в общем-то, очевидный, так, как вставка и удаление элементов в начале массива довольно ресурсоемкая операция, выполнимая за время O(n), где n – количество элементов (так как требуется освободить место в начале, копированием всех элементов на единицу вправо). В то же время вставка и удаление в конце выполнится за время O(1). Следовательно, лучше что бы вершиной стека был последний элемент массива.
Метод GetCount
Метод при чтении свойства Count. Используя функцию Length, возвращает количество элементов в массиве.
- function TStStack.GetCount(): integer;
- begin
- Result := Length( FItems );
- end;
Метод Push
Принимает в качестве параметра новый элемент стека и добавляет его в конец массива.
- procedure TStStack.Push( newObject: TObject );
- var
- newCount: integer;
- begin
- newCount := Count + 1;
- // Увеличиваем количество элементов в массиве
- SetLength( FItems, newCount );
- // Добавляем новый элемент
- FItems[ newCount - 1 ] := newObject;
- end;
Метод Pop
Возвращает последний элемент массива, при этом, удаляя его, собственно, из массива.
- function TStStack.Pop(): TObject;
- begin
- if Count = 0 then
- raise Exception.Create('Стек пуст');
- // Возвращаем элемент с верхушки
- Result := FItems[ Count - 1 ];
- // Убираем его из массива
- SetLength( FItems, Count - 1 );
- end;
Метод Peek
Просто возвращает последний элемент массива.
- function TStStack.Peek(): TObject;
- begin
- if Count = 0 then
- raise Exception.Create('Стек пуст');
- Result := FItems[ Count - 1 ]
- end;
Метод Clear
Сначала для всех элементов вызывается деструктор, потом уже обнуляется сам массив.
- procedure TStStack.Clear();
- var
- i: integer;
- begin
- for i := 0 to Count - 1 do
- FItems[ i ].Free;
- SetLength( FItems, 0 );
- end;
Мы получили вполне рабочий стек для хранения объектов. Вообще говоря, все страшно неоптимизированно. К примеру, каждый раз для получения количества элементов вызывается функция Length. Так же при добавлении нового элемента каждый раз выделяется память. При малом добавляемом количестве элементов это допустимо, но вот если сразу нужно добавить достаточно много элементов, то выделение памяти каждый раз сильно ударит по производительности.
Эти и многие другие недостатки исправлены в реализации стеках Delphi, поэтому все же использовать их :)
На этом первая часть цикла статей закончена. Далее мы рассмотрим пример использования стека, а так же классы стеков, которые уже есть в Delphi.
delphi, структуры данных
Комментарии (0)
Добавить комментарий