Реализация: круговая модель.
Наша реализация очереди вводит круговую модель. Вместо сдвига элементов влево, когда один элемент удаляется, элементы очереди организованы логически в окружность. Переменная front всегда является местоположением первого элемента очереди, и она продвигается вправо по кругу по мере выполнения удалений. Переменная rear является местоположением, где происходит следующая вставка. После вставки rear перемещается по кругу вправо. Переменная count поддерживает запись количества элементов в очереди, и, если счетчик count равен значению size очередь заполнена.
Реализуем круговое движение, используя операцию остатка от деления:
- Перемещение конца очереди вперед: rear = (rear+1)%MaxQSize;
- Перемещение начала вперед: front = (front+1)%MaxQSize;
Листинг 13. Очередь
Очередь
#pragma once
#include <iostream>
#include <cstdlib>
// максимальный размер списка очереди
template<class DType>
class Queue
{
private:
// Массив и параметры очереди
int front, rear, count;
DType *qlist;
//Размер массива
int size;
public:
// конструктор
Queue(int size);
~Queue();
// операции модификации очереди
void qInsert(const DType &item);
DType qDelete(void);
void qClear(void);
// операции доступа
DType qFront(void) const;
// методы тестирования очереди
int qLength(void) const { return count; }
int isEmpty(void) const {return !count; }
int isFull(void) const {return count==size;}
};
// инициализация данных-членов: front, rear, count, size
template<class DType>
Queue<DType>::Queue (int s) : front(0), rear(0), count(0), size(s)
{
qlist = new DType[s];
}
template<class DType>
Queue<DType>::~Queue()
{
delete [] qlist;
}
// вставить item в очередь
template<class DType>
void Queue<DType>::qInsert (const DType &item)
{
// закончить программу, если очередь заполнена
if (isFull())
{
std::cerr << "Переполнение очереди!" << std::endl;
exit(1);
}
// увеличить count, присвоить значение item элементу массива
// изменить значение rear
count++;
qlist[rear] = item;
rear = (rear+1) % size;
}
// удалить элемент из начала очереди
// и возвратить его значение
template<class DType>
DType Queue<DType>::qDelete()
{
DType temp;
// если очередь пуста, закончить программу)
if(isEmpty())
{
std::cerr << "Удаление из пустой очереди!" << std::endl;
exit(1);
}
// записать значение в начало очереди
temp = qlist[front];
// уменьшить count на единицу
// продвинуть начало очередии возвратить прежнее значение
//из начала
count--;
front = (front+1) % size;
return temp;
}
template<class DType>
DType Queue<DType>::qFront() const
{
if(isEmpty())
{
std::cerr << "Удаление из пустой очереди!" << std::endl;
exit(1);
}
return qlist[front];
}
template<class DType>
void Queue<DType>::qClear()
{
front = 0;
rear = 0;
count = 0;
}
Main:
#include <iostream>
#include "queue.h"
using namespace std;
int main(int argc, char *argv[])
{
system("chcp 65001");
const int amount = 10;
Queue<int> test(amount);
cout << " Пуст? " << boolalpha << (bool) test.isEmpty() << endl;
cout << " Кол-во: " << test.qLength() << endl;
for (int i=0; i<amount; i++)
test.qInsert(i+1);
cout << " Полон? " << boolalpha << (bool) test.isFull() << endl;
cout << " Кол-во: " << test.qLength() << endl;
cout << " 1-ый эл-нт: " << test.qFront() << endl;
cout << " Проверка очереди:\n";
for (int i=0; i<amount; i++)
cout << test.qDelete() << endl;
return 0;
}
Результат:
Пуст? true
Кол-во: 0
Полон? true
Кол-во: 10
1-ый эл-нт: 1
Проверка очереди:
Литература
1. Шилдт, Герберт. Полный справочник по C++, 4-е издание — М. : Издательский дом “Вильямс”, 2006.
2. Павловская Т.А. C/C++. Программирование на языке высокого уровня — СПб.:Питер, 2003.
3. Павловская Т. А., Щупак Ю. А. C/C++. Структурное и объектно-ориентированное программирование: Практикум. — СПб.: Питер, 2011.
4. Уильям Топп, Уильям Форд. Структуры данных в C++: Пер. с англ. — М.: ЗАО «Издательство БИНОМ», 1999.