Очереди. Пользовательская реализация очереди

   
На этом шаге мы рассмотрим другую реализацию очереди.

   
Стандартный класс queue<> ставит на первое место не удобство и безопасность, а скорость работы. Поэтому вашему вниманию предлагается
нестандартная реализация очереди. Она обладает двумя преимуществами:

  • функция рор() возвращает следующий элемент;
  • при пустой очереди функции рор() и front() генерируют исключения.

   
Кроме того, из реализации исключены операции, лишние для рядового пользователя очередей (например, операции сравнения и функция back()).
Полученный класс очереди приведен ниже.

//Queue.hpp
// ************************************************************
// *  Queue.hpp
// *   - более удобный и безопасный класс очереди
// ************************************************************
#ifndef QUEUE_HPP
#define QUEUE_HPP

#include <deque>
#include <exception>

template <class T>
class Queue {
  protected:
    std::deque<T> c;        // Контейнер для хранения элементов

  public:
    // Класс исключения, генерируемого функциями pop() и front()
    // при пустой очереди

    class ReadEmptyQueue : public std::exception {
      public:
        virtual const char* what() const throw() {
            return "read empty queue";
        }
    };
  
    // Количество элементов
    typename std::deque<T>::size_type size() const {
        return c.size();
    }

    // Проверка пустой очереди
    bool empty() const {
        return c.empty();
    }

    // Занесение элемента в очередь
    void push (const T& elem) {
        c.push_back(elem);
    }

    // Извлечение элемента из очереди с возвращением его значения
    T pop () {
        if (c.empty()) {
            throw ReadEmptyQueue();
        }
        T elem(c.front());
        c.pop_front();
        return elem;
    }

    // Получение значения следующего элемента
    T& front () {
        if (c.empty()) {
            throw ReadEmptyQueue();
        }
        return c.front();
    }
};

#endif // QUEUE_HPP 

   
При использовании этой очереди пример из 336 шага можно записать в следующем виде:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream>
#include <string>
#include "Queue.hpp"      // Использование нестандартного класса очереди

#include <conio.h>   //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{

 try {    
    Queue<string> q;

    // Вставка трех элементов в очередь
    q.push(ToRus("Это "));
    q.push(ToRus("я. "));
    q.push(ToRus("Здравствуйте"));

    // Вывод и удаление двух элементов из очереди
    cout << ToRus("Извлечение и вывод двух элементов из очереди: \n");
    cout << q.pop();
    cout << q.pop();
    cout << endl;

    // Вставка двух новых элементов
    q.push(ToRus("Привет "));
    q.push(ToRus("всем!"));

    // Удаление одного элемента
    q.pop();

    // Вывод и удаление двух элементов из очереди
    cout << ToRus("Вывод и удаление двух элементов: \n");
    cout << q.pop();
    cout << q.pop() << endl;

    // Вывод количества оставшихся элементов
    cout << ToRus("Количество элементов в очереди: ") << q.size()
         << endl;
    // Вывод и удаление одного элемента
    cout << q.pop() << endl;
   }
   catch (const exception& e) {
      cerr << "EXCEPTION: " << e.what() << endl;
   }


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

   
При последнем вызове рор() намеренно допущена ошибка. В отличие от стандартного класса очереди с неопределенным поведением наш
класс генерирует исключение. Результат выполнения программы выглядит так:


Рис.1. Результат работы приложения

   
Со следующего шага мы начнем рассмотривать приоритетные очереди.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий