Устаревшие материалы - примеры использования очереди

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

Задача 1.

Вводятся натуральные числа, конец ввода - 0
Вывести: количество четных, количество нечетных, все четные в прямом порядке, все нечетные — в обратном.

Например, введены числа:

1  2  5  7  4  6  9  0

Должно быть выведено следующее:

3 // количество четных
4 // количество нечетных
2  4  6 // все четные в прямом порядке
3  7  5 // все нечетные в обратном порядке

Решение:
Эта задача имеет несколько решений, но, очевидно, самым удобным является использование изученных нами АТД — стека и очереди.
Очередь организована по принципу FIFO, а значит подходит для вывода чисел в прямом порядке, в то время как для обратного вывода надо воспользоваться стеком, организованным по принципу LIFO.

uses Collections;

var
  /// для хранения четных чисел
  q: Queue<integer>;  
  /// для хранения нечетных чисел
  s: Stack<integer>;
  
  /// количество четных чисел
  cEven: integer;
  /// количество нечетных чисел
  cOdd: integer;
  
begin
  q := new Queue<integer>;
  cEven := 0;
  s := new Stack<integer>;
  cOdd := 0;
  
  while True do
  begin
    var x: integer;
    read(x);
    
    if x = 0 then
      break;
    Assert(x > 0);  // по условию задачи должны вводиться натуральные числа
    
    if Odd(x) then
    begin
      cOdd += 1;
      s.Push(x);
    end
    else  // if x is even
    begin
      cEven += 1;
      q.Enqueue(x);
    end;
  end;
  
  writeln('Количество четных = ', cEven);
  writeln('Количество нечетных = ', cOdd);

  write('Четные в прямом порядке: ');
  while not q.IsEmpty do
    write(q.Dequeue, '  ');
  writeln();
  
  write('Нечетные в обратном порядке: ');
  while not s.IsEmpty do
    write(s.Pop, '  ');
end.


Задача 2. Обслуживание клиентов в очереди (категория использование АТД при моделировании).
Спецификация задачи: Имеется очередь клиентов.
Первоначально она пуста.
В течение рабочего дня (7*60 минут) происходят следующие случайные события:

  • приход клиента;
  • обслуживание клиента в очереди;

Время перед приходом нового клиента TimeBeforeNewClient и время обслуживания текущего клиента ServeTime генерируются случайно.
Будем считать, что функция RandomClient возвращает нового клиента.

Решение:

uses Collections;

type
  /// Клиент
  Client = class
    /// Имя клиента
    name: string;
    /// Сумма денег
    money: integer;
    
    constructor (pName: string; pMoney: integer);
    begin
      name := pName;
      money := pMoney;
    end;
    
    procedure Println;
    begin
      write('Имя: ', name);
      writeln('  Наличные: ', money);
    end;
  end;

/// Возвращает случайного клиента  
function RandomClient: Client;
begin
  case Random(3) of
    0 : result := new Client('Иванов', Random(100, 1000));
    1 : result := new Client('Петрова', Random(1, 1000000));
    2 : result := new Client('Сидоров', Random(1000, 10000));
  end;
end;
  
const
  /// Количество часов рабочего дня
  WORKING_DAY = 7;
  /// Количество минут в часе
  MIN_IN_HOUR = 60;
  
  /// Минимальное время до прихода нового клиента
  MIN_BEFORE_NEW = 1;
  /// Максимальное время до прихода нового клиента
  MAX_BEFORE_NEW = 10;
  /// Минимальное время обслуживания клиента
  MIN_SERVE = 4;
  /// Максимальное время обслуживания клиента
  MAX_SERVE = 9;
 
/// Выводит время в часах и минутах  
procedure PrintTime(cMinutes : integer);
begin
  var hours := cMinutes div MIN_IN_HOUR;
  var minutes := cMinutes mod MIN_IN_HOUR;
  
  write(hours:2, ' : ', minutes:2);
end;

var 
  /// Очередь клиентов
  ClientQueue := new Queue<Client>;
  
  /// Время до обслуживания нового клиента
  TimeBeforeNewClient: integer;
  /// Врямя, требующееся на обслуживание клиента
  ServeTime: integer;
  
  
begin
  TimeBeforeNewClient := 0;
  ServeTime := 0;

  for var t := 1 to WORKING_DAY * MIN_IN_HOUR do
  begin
    if TimeBeforeNewClient = 0 then   // пришел новый клиент
    begin
      var rCl := RandomClient;
      ClientQueue.Enqueue(rCl);
      TimeBeforeNewClient := Random(MIN_BEFORE_NEW, MAX_BEFORE_NEW);
      
      PrintTime(t); write(' Пришел: ');
      rCl.Println;
    end;
    
    if (ServeTime = 0) and not ClientQueue.IsEmpty then  // подошло время обслуживать клиента
    begin
      var rCl := ClientQueue.Dequeue;
      ServeTime := Random(MIN_SERVE, MAX_SERVE);
      
      PrintTime(t); write(' Обслужен: ');
      rCl.Println;
    end;
    
    if TimeBeforeNewClient > 0 then
      TimeBeforeNewClient -= 1;
    if ServeTime > 0 then 
      ServeTime -= 1;
  end;
end.