Очередь. Особенности реализации. Способы реализации очереди. Представление очереди в виде динамического массива
Содержание
- 1. Структура данных «очередь». Особенности реализации очереди
- 2. Виды очередей
- 3. Способы реализации очереди
- 4. Кольцевая очередь
- 5. Очередь с приоритетами. Способы реализации
- 6. Пример реализации очереди в виде динамического массива
- Связанные темы
Поиск на других ресурсах:
1. Структура данных «очередь». Особенности реализации очереди
Очередь – это динамическая структура данных которая состоит из набора элементов которые размещены последовательно друг за другом. При этом добавление элементов осуществляется с одной стороны, а удаление (вытягивание) – с другой стороны.
Очередь работает по принципу FIFO (First In — First Out), то есть «первым пришел – первым вышел». На рисунке 1 отображен принцип работы очереди.
Рисунок 1. Динамическая структура данных «очередь»
Одной из особенностей очереди есть то, что в очереди часть последовательных элементов может быть занята на данный момент времени (рисунок 2).
Рисунок 2. Очередь, в которой часть элементов занята на данный момент времени
В повседневной жизни использование очереди встречается довольно часто, например:
- очередь в магазине;
- очередь документов на печать на принтере;
- последовательность операторов в алгоритме которые выполняются друг за другом;
- другие случаи.
⇑
2. Виды очередей
Различают следующие виды очередей:
- простая очередь;
- кольцевая очередь. В такой очереди элемент, который выходит с начала очереди, будет помещен в ее конец;
- очередь с приоритетами. В такой очереди элементы размещаются по их приоритетам (весовым коэффициентам). Первым из очереди выходит элемент с наивысшим приоритетом.
Любой вид очереди может иметь ограничение по размеру (количество элементов в очереди).
⇑
3. Способы реализации очереди
В программе очередь можно реализовывать в виде:
- статического массива с ограничением на размер в очереди;
- динамического массива;
- односвязного списка;
- двусвязного списка.
⇑
4. Кольцевая очередь
В кольцевой очереди элемент, который выходит (удаляется) из очереди помещается в ее конец (рисунок 3).
Рисунок 3. Кольцевая очередь
На рисунке 4 изображена работа кольцевой очереди в случае, когда часть элементов занята.
Рисунок 4. Кольцевая очередь. Случай когда часть элементов занята
Примеры кольцевой очереди:
- движение трамваев по круговому маршруту;
- очередь событий для их обработки в Windows.
⇑
5. Очередь с приоритетами. Способы реализации
В очереди с приоритетами первым выходит (удаляется) тот элемент, который имеет наивысший приоритет. В очереди с приоритетами каждому элементу ставится в соответствие приоритет (весовой коэффициент).
Очередь с приоритетами может быть реализована одним из двух способов:
- очередь с приоритетным включением. В этом случае элемент, который добавляется в очередь, сразу размещается в ней в соответствии с его приоритетом (рисунок 5). При удалении, этот элемент просто вытягивается с конца очереди;
- очередь с приоритетным исключением. В этом случае новый элемент просто добавляется в конец очереди. А вытягивание элемента из очереди осуществляется по его приоритету, то есть вытягивается элемент с наивысшим приоритетом (рисунок 6).
Рисунок 5. Очередь с приоритетным включением.
Добавление нового элемента в соответствии с его приоритетом
Рисунок 6. Очередь с приоритетным исключением.
Элемент добавляется в конец очереди, вытягивается в соответствии с приоритетом
⇑
6. Пример реализации очереди в виде динамического массива
В примере объявляется шаблонный класс Queue, реализующий очередь в виде динамического массива для некоторого обобщенного типа T.
В классе реализованы следующие поля и методы:
- целочисленная внутренняя переменная count – количество элементов в очереди;
- внутренняя переменная p – указатель на тип T. Этот указатель есть массивом данных образующих очередь. Элемент массива с индексом 0 есть началом очереди. Элемент с индексом count-1 есть конец очереди;
- конструктор по умолчанию;
- конструктор копирования Queue(const Queue&);
- оператор копирования operator=(const Queue&);
- метод push() – добавляет элемент в конец очереди;
- деструктор;
- метод pop() – вытягивает первый элемент из очереди;
- метод GetItem() – читает первый элемент из очереди не вытягивая его;
- метод clear() – очищает очередь;
- метод IsEmpty() – проверяет пустая ли очередь;
- метод Get() – возвращает количество элементов в очереди;
- метод print() – выводит очередь на экран.
Программный код класса следующий:
#include <iostream> #include <new> using namespace std; // Динамическая структура данных "очередь" template <typename T> class Queue { private: T* p; // динамический массив int count; // количество элементов в очереди public: // конструктор по умолчанию Queue() { count = 0; // очередь пустая } // конструктор копирования Queue(const Queue& obj) { // скопировать obj в текущий объект count = obj.count; try { // попытка выделить память для p p = new T[count]; // заполнить значениями for (int i = 0; i < count; i++) p[i] = obj.p[i]; } catch (bad_alloc e) { // если память не выделена, то вывести текст ошибки cout << e.what() << endl; count = 0; // создать пустую очередь } } // добавить элемент в очередь void push(T item) { T* p2; // объявить дополнительный указатель p2 = p; // перенаправить дополнительный указатель на p try { // попытка выделить новый фрагмент памяти для p, но на 1 больше p = new T[count + 1]; // скопировать данные из участка на который указывает p2 (старые данные) // в участок, на который указывает p for (int i = 0; i < count; i++) p[i] = p2[i]; // скопировать последний элемент p[count] = item; // увеличить количество элементов на 1 count++; // освободить предварительно выделенную память if (count > 1) delete[] p2; } catch (bad_alloc e) { // если память не выделена cout << e.what() << endl; // вывести сообщение об ошибке // вернуть старый указатель на p p = p2; } } // вытянуть первый элемент из очереди T pop() { if (count == 0) return 0; // заполнить элемент, который вытягивается из очереди T item; item = p[0]; // сформировать новый участок памяти, который на 1 меньше try { T* p2; // попытка выделить пам'ять p2 = new T[count - 1]; count--; // уменьшить количество элементов в очереди // p=>p2 for (int i = 0; i < count; i++) p2[i] = p[i + 1]; // копируются все кроме первого элемента // освободить участок, на который указывает p if (count > 0) delete[] p; // перенаправить p на p2 p = p2; // вернуть item return item; } catch (bad_alloc e) { // если память не выделилась, то вернуть 0 cout << e.what() << endl; return 0; } } // операторная функция operator=(), // реализует присваивание объектов типа Queue Queue& operator=(const Queue& obj) { T* p2; // указатель на дополнительную память try { // попытка выделить новый участок памяти для p2 p2 = new T[obj.count]; // если память выделена успешно, // можно освобождать предварительно выделенную память для p if (count > 0) delete[] p; // скопировать obj в текущий объект p = p2; // перенаправить p на p2 count = obj.count; // заполнить значениями for (int i = 0; i < count; i++) p[i] = obj.p[i]; } catch (bad_alloc e) { // если память не выделилась, то вывести соответствующее сообщение cout << e.what() << endl; } return *this; // вернуть текущий объект } // деструктор ~Queue() { if (count > 0) delete[] p; } // взять первый элемент из очереди не вытягивая его T GetItem() { if (count > 0) return p[0]; else return 0; } // очистка очереди void clear() { if (count > 0) { delete[] p; count = 0; } } // проверка существования элементов в очереди bool IsEmpty() { return count == 0; } // количество элементов в очереди int GetN() { return count; } // метод, выводящий очередь void print(const char* objName) { cout << "Object: " << objName << endl; for (int i = 0; i < count; i++) cout << p[i] << "\t"; cout << endl; cout << "---------------------" << endl; } }; void main() { Queue<int> Q1; Q1.print("Q1"); Q1.push(5); Q1.print("Q1"); Q1.push(8); Q1.push(11); Q1.push(17); // Q1 = {5,8,11,17} Q1.print("Q1"); int d; d = Q1.GetItem(); cout << "d = " << d << endl; Q1.print("Q1"); Queue<int> Q2 = Q1; Q2.print("Q2"); Queue<int> Q3; Q3 = Q1 = Q2; Q1.push(333); Q2.push(555); Q1.print("Q1"); Q2.print("Q2"); Q3.print("Q3"); Q2.clear(); if (Q2.IsEmpty()) cout << "OK" << endl; else cout << "NO" << endl; cout << "n = " << Q3.GetN() << endl; }
Результат выполнения программы
Object: Q1 --------------------- Object: Q1 5 --------------------- Object: Q1 5 8 11 17 --------------------- d = 5 Object: Q1 5 8 11 17 --------------------- Object: Q2 5 8 11 17 --------------------- Object: Q1 5 8 11 17 333 --------------------- Object: Q2 5 8 11 17 555 --------------------- Object: Q3 5 8 11 17 --------------------- OK n = 4
⇑
Связанные темы
⇑