Черга (queue). Характеристика та приклад черги

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

Применение очередей

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

Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.

/*** Класс "Очередь"** Слава Антонов (с) 2004** http://slava.users.otts.ru*/ #ifndef QUEUE_H#define QUEUE_H #include <iostream.h>#include <malloc.h> // Тип элемента очередиtypedef int datatype; // Элемент односвязного спискаstruct listitem{ datatype data; listitem* next;}; class equeue{ private: char* msg; // сообщение об ошибке public: equeue(const char* errmsg) { msg = strdup(errmsg); } ~equeue() { free(msg); } const char* getmsg() { return msg; }}; #define EQUEUE_EMPTY "Queue is empty" class cqueue{ private: listitem* head; // голова односвязного списка listitem* tail; // хвост односвязного списка unsigned cnt; // длина очереди (кол-во элементов в ней) public: cqueue(); // конструктор по-умолчанию cqueue(const cqueue&); // конструктор копирования // этот конструктор вызывается в следующей ситуации: // cqueue Q2 = Q1 ~cqueue() { clear(); } // деструктор cqueue& clear(); // удалить все элементы очереди unsigned getCnt() const { return cnt; } cqueue& del(); // удалить один элемент из начала очереди bool empty() const { return head == NULL; } // признак пустой очереди cqueue& push(const datatype&); // добавить элемент в конец очереди datatype pop(); // извлеч элемент из начала очереди const datatype& get() const; // посмотреть элемент в начале очереди cqueue& set(const datatype&); // заменить элемент в начале очереди bool operator == (const cqueue&) const; // оператор сравнения bool operator!= (const cqueue& q) const { return!(*this == q); } cqueue& operator = (const cqueue&); // оператор присваивания friend ostream& operator << (ostream&, const cqueue&); // оператор вывода}; cqueue::cqueue(){ head = tail = NULL;} cqueue::cqueue(const cqueue& q){ head = tail = NULL; *this = q;} cqueue& cqueue::clear(){ while(!empty()) del(); return *this;} cqueue& cqueue::del(){// если стек пуст - генерируем исключение if(empty()) throw(equeue(EQUEUE_EMPTY)); listitem* tmp = head->next; // запоминаем указатель на // следующий элемент очереди delete head; // удаляем элемент...//...и переводим указатель на следующий элемент if(!tmp) head = tail = NULL; else head = tmp; cnt--; return *this;} cqueue& cqueue::push(const datatype& data){ listitem* item = new listitem; item->data = data; item->next = NULL; if(!head) { head = item; tail = head; } else { tail->next = item; tail = item; } cnt++; return *this;} datatype cqueue::pop(){ if(empty()) throw(equeue(EQUEUE_EMPTY)); datatype data = head->data; del(); return data;} const datatype& cqueue::get() const{ if(empty()) throw(equeue(EQUEUE_EMPTY)); return head->data;} cqueue& cqueue::set(const datatype& data){ if(empty()) throw(equeue(EQUEUE_EMPTY)); head->data = data; return *this;} bool cqueue::operator == (const cqueue& q) const{ if(this == &q) return true; if(getCnt()!= q.getCnt()) return false; listitem* h1 = head; listitem* h2 = q.head; while(h1) { if(h1->data!= h2->data) return false; h1 = h1->next; h2 = h2->next; } return false;} cqueue& cqueue::operator = (const cqueue& q){ if(*this == q) return *this; clear(); listitem* item = q.head; while(item) { push(item->data); item = item->next; } return *this;} ostream& operator << (ostream& s, const cqueue& q){ listitem* item = q.head; while(item) { s << item->data << endl; item = item->next; } return s;} #endif

23. Асоціативні контейнери. Загальна характеристика.

Ассоциативные контейнеры
set	Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.
multiset	То же что и set, но позволяет хранить повторяющиеся элементы.
map	Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.
multimap	То же что и map, но позволяет хранить несколько одинаковых ключей.