Реализация: круговая модель. — КиберПедия 

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...

История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...

Реализация: круговая модель.

2017-07-01 172
Реализация: круговая модель. 0.00 из 5.00 0 оценок
Заказать работу

Наша реализация очереди вводит круговую модель. Вместо сдвига элементов влево, когда один элемент удаляется, элементы очереди организованы логически в окружность. Переменная 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.

 


Поделиться с друзьями:

Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...

Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...

Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...

Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.021 с.