// ННГУ, ВМК, Курс "Методы программирования-2", С++, ООП
//
// Copyright (c) Гергель В.П. 05.08.2000
//
// Динамические структуры данных - тестирование системы N стеков (списки)

#include <dos.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include "datlist.cpp"

#define N  15
#define NS 10 // количество стеков

void main() {
  TListStack mst[NS];
  int i, k, val[N];
  clrscr();
  cout << "Алгоритм поразрядной сортировки - пример на использование стеков" << endl;

  // генерация данных
  cout << endl;
  for ( i=0; i < N; i++ ) val[i] = random(100);
  cout << "Данные до сортировки" << endl;
  for ( i=0; i < N; i++ ) cout << val[i] << " ";
  cout << endl;

  // раскладка по стекам (номер стека - младшая цифра)
  cout << endl;
  for ( i=0; i < N; i++ ) mst[val[i]%10].Put(val[i]);

  // сборка значений из стеков (от старшего стека)
  for ( i=NS-1, k=0; i>-1; i-- )
    while ( ! mst[i].IsEmpty() ) val[k++] = mst[i].Get();
  cout << "Данные после первой раскладки" << endl;
  for ( i=0; i < N; i++ ) cout << val[i] << " ";
  cout << endl;

  // раскладка по стекам (номер стека - старшая цифра)
  cout << endl;
  for ( i=0; i < N; i++ ) mst[val[i]/10].Put(val[i]);

  // сборка значений из стеков (от младшего стека)
  for ( i=0, k=0; i < NS; i++ )
    while ( ! mst[i].IsEmpty() ) val[k++] = mst[i].Get();
  cout << "Данные после второй раскладки (итог)" << endl;
  for ( i=0; i < N; i++ ) cout << val[i] << " ";
  cout << endl;

  getch();
}