:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Структуры данных » Введение в абстрактные структуры »
 



По книге Laszlo
"Вычислительная геометрия и компьютерная графика на С++"

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

template<class T> class Stack {
 private :
  List<T> *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<class T> Stack<T>::Stack (void) :
  s (new List<T>)
{
}

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

template<class T>  Stack<T>::-Stack (void) :
{
  delete s;
}

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

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

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

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

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

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

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

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

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

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

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

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

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