Реализация стека на основе ранее рассмотренного кольцевого списка

Программирование

ПОИСК

Главная / Алгоритмы / Структуры данных и хэширование / Введение в абстрактные структуры / Cтек /

8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга

Реализация стека на основе ранее рассмотренного кольцевого списка - Программирование от RIN.RU

Реализация стека на основе ранее рассмотренного кольцевого списка

Реализация опирается на класс кольцевого списка. Шаблон класса Stack содержит собственный элемент данных s, который указывает на объект List, представляющий собой стек. Список упорядочен с верха стека до его низа, в частности верхний элемент стека находится в первой позиции списка, а нижний элемент - в последней позиции списка.

template class Stack {
private :
List *s;
public :
Stack (void);
~Stack (void);
void push (T v);
Т pop (void);
bool empty (void);
int size (void);
Т top (void);
Т nextToTop (void);
Т bottom (void);
};

Реализация компонентных функций очевидна. Конструктор Stack создает объект List и приписывает его элементу данных s:

template Stack::Stack (void) :
s (new List)
{
}

Деструктор ~Stack удаляет объект List, на который указывает элемент данных s:

template Stack::-Stack (void) :
{
delete s;
}

Компонентная функция push проталкивает элемент v в текущий стек, а компонентная функция pop выбирает из текущего стека самый верхний элемент и возвращает его:

template void Stack::push(T v)
{
s->prepend(v);
}

template T Stack::pop(void)
{
s->first();
return s->remove();
}

Компонентная функция empty возвращает значение TRUE (истина) в том случае, когда текущий стек пустой, а компонентная функция size возвращает число элементов в текущем стеке:

template bool Stack::empty(void)
{
return (s->length() == 0);
}

template int Stack::size (void)
{
return s->length();
}

Функция top возвращает самый верхний элемент в стеке, функция nextTolop возвращает элемент, лежащий непосредственно под самым верхним, а функция bottom возвращает самый нижний элемент. Ни одна из этих функций вызова не изменяет состояния стека (ничто не заносится и не выбирается).

template T Stack::top (void)
{
return s->first();
}

template T Stack::nextToTop (void)
{
s->first();
return s->next();
}

template T Stack::bottom (void)
{
return s->last();
}

На простейшем примере использования стека покажем, как с помощью следующей функции можно изменить порядок следования строк в массиве а:

void reverse (char *a[] , int n)
{
Stack s;
for (int i = 0; i < n; i++)
s.push(a[i]);
for (i = 0; i < n; i++)
a[i] = s.pop();
}

Заметим, что мы реализовали АТД стека в терминах АТД списка. Такая реализация гораздо проще, чем реализация, основанная непосредственно на таких программных блоках низкого уровня, как связанные списки или массивы. Опасность реализации АТД в терминах другого АТД заключается том, что первый АТД наследует характеристики второго, реализация которого может быть неэффективной. Но в данном случае, применяя свою собственную реализацию АТД списка, мы хорошо представляем ее свойства и поэтому можем легко показать, что каждая из операций, поддерживаемая классом Stack, выполняется за постоянное время.

8 Комментарии к статье 8 8 Обсудить в чате