Как работает очередь с
Очередь — это линейная динамическая структура данных, для которой выполняется правило: добавление новых данных возможно только в конец этой структуры, а удаление (извлечение) — только с начала. В англоязычной литературе этот принцип называется FIFO (First Input — First Output, т.е. первый пришёл — первый ушёл).
Примером из реальной жизни может быть очередь из покупателей к кассе в магазине.
Как не трудно понять, очередь — это линейный список, для которого определены всего две основные операции: добавление в конец и извлечение с начала. Значит, удобно иметь два указателя: на начало и конец этой динамической структуры. Но списки бывают односвязные и двухсвязные. Какой использовать? Подойдёт только двухсвязный список. В этом можно будет убедиться при рассмотрении основных алгоритмов для работы с очередью.
На рисунке ниже показано графическое представление очереди. Как и в предыдущих темах, очередь будем строить из целых чисел, например: 3, 5, 1.
Для работы используем структуры Data (данные) и Queue (очередь):
Queue *prev; // указатель на предшествующий элемент
Queue *next; // указатель на последующий элемент
Затем в программе определяем два указателя:
Queue *Begin = NULL; // Начало очереди
Queue *End = NULL; // Конец очереди
После этого можно начать работать с очередью.
Основные операции с очередью
Для очереди используется две основные операции: добавление в конец и извлечение из начала очереди.
1. Добавление в конец очереди :
void Add(Queue **Begin, Queue **End, Data &x)
Queue *t = new Queue; // Память под новый элемент
t->d.a = x.a; // Заполнение полей
if(*Begin == NULL || *End == NULL)
// Если очередь была пуста
// В очереди был хотя бы один элемент
t->prev = *End; // Подключаем новый элемент к имеющимся
*End = t; // Перенастройка начала очереди
Обратиться к функции можно так:
где x — объект типа Data .
Как видим, хотя для добавления надо знать только положение конца очереди, здесь в функцию передаётся и её начало. Зачем? А чтобы правильно обработать ситуацию, когда данные добавляются в пустую очередь. Ведь в этом случае требуется настроить указатель Begin на начало очереди.
2. Извлечение данных из начала очереди :
bool Del(Queue **Begin, Queue **End, Data &x)
x.a = t->d.a; // Заполнение полей
if(*Begin == NULL) // Удаляется единственный элемент очереди
Обратиться к функции можно так:
где x — объект типа Data .
Двухсторонняя очередь
Разновидностью очередей является двухсторонняя очередь или дек . Она отличается от обычной очереди тем, что добавление и удаление данных допустимо с обоих концов очереди.
Для реализации алгоритмов работы с двухсторонней очередью можно использовать те же структуры, что и для обычной очереди ( Data (данные) и Queue (очередь)), необходимо только дополнить основные операции.
Для работы с деком необходимы следующие действия: добавление в начало и конец очереди (последнюю можно взять из примеров для обычной очереди), удаление из начала очереди (берем как для обычной очереди) и с конца очереди.
Всё это несложно реализовать самостоятельно по аналогии с обычной очередью, поэтому ни каких примеров не привожу.
Очередь с приоритетом
Это очень интересная разновидность очередей. В ней добавление новых данных производится также в конец очереди, а вот выборка — в зависимости от какого-либо правила.
Примером может служить очередь в кассу магазина, где людей с какими-нибудь удостоверениями, например, ветеранов или инвалидов, обслуживают без очереди.
Для представления данных можно использовать те же структуры, что и для обычной очереди, добавление в конец очереди будет таким же, а вот извлечение из очереди требует основательной переделки. При каждом извлечении вначале надо поискать в очереди «внеочередников» (есть такой — его и извлекаем, на этом очередной запрос исчерпан) и только потом работать с остальными в обычном режиме.
Пример . Имеется очередь с приоритетом, в которой хранятся целые числа. Пусть удаление отрицательных чисел будет более приоритетным. Так, если в очереди находятся числа 3, -4, 2, -6 , то удаляться они могут только в последовательности: -4, -6, 3, 2 .
Всё это не так сложно реализовать самостоятельно, поэтому ни каких программных примеров не приводится.
Как работает очередь с
Класс Queue представляет обычную очередь, которая работает по алгоритму FIFO («первый вошел — первый вышел»).
Создание очереди
Для создания очереди можно использовать один из трех ее конструкторов. Прежде всего можно создать пустую очередь:
Queue people = new Queue();
При создании пустой очереди можно указать емкость очереди:
Queue people = new Queue(16);
Также можно инициализировать очередь элементами из другой коллекции или массивом:
var employees = new List < "Tom", "Sam", "Bob" >; Queue people = new Queue(employees); foreach (var person in people) Console.WriteLine(person); Console.WriteLine(people.Count); // 3
Для перебора очереди можно использовать стандартный цикл foreach .
Для получения количества элементов в очереди в классе определено свойство Count .
Методы Queue
У класса Queue можно отметить следующие методы:
- void Clear() : очищает очередь
- bool Contains(T item) : возвращает true , если элемент item имеется в очереди
- T Dequeue() : извлекает и возвращает первый элемент очереди
- void Enqueue(T item) : добавляет элемент в конец очереди
- T Peek() : просто возвращает первый элемент из начала очереди без его удаления
Посмотрим применение очереди на практике:
var people = new Queue(); // добавляем элементы people.Enqueue("Tom"); // people = < Tom >people.Enqueue("Bob"); // people = < Tom, Bob >people.Enqueue("Sam"); // people = < Tom, Bob, Sam >// получаем элемент из самого начала очереди var firstPerson = people.Peek(); Console.WriteLine(firstPerson); // Tom // удаляем элементы var person1 = people.Dequeue(); // people = < Bob, Sam >Console.WriteLine(person1); // Tom var person2 = people.Dequeue(); // people = < Sam >Console.WriteLine(person2); // Bob var person3 = people.Dequeue(); // people = < >Console.WriteLine(person3); // Sam
Стоит отметить, что если с помощью методов Peek или Dequeue мы попытаемся получить первый элемент очереди, которая пуста, то программа выдаст исключение. Соответственно перед получением элемента мы можем проверять количество элементов в очереди:
if(people.Count > 0)
Либо можно использовать пару методов:
- bool TryDequeue(out T result) : передает в переменную result первый элемент очереди с его удалением из очереди, возвращает true , если очередь не пуста и элемент успешно получен.
- bool TryPeek(out T result) : передает в переменную result первый элемент очереди без его извлечения из очереди, возвращает true , если очередь не пуста и элемент успешно получен.
var people = new Queue(); // добавляем элементы people.Enqueue("Tom"); // people = < Tom >// удаляем элементы var success1 = people.TryDequeue(out var person1); // success1 = true if (success1) Console.WriteLine(person1); // Tom var success2 = people.TryPeek(out var person2); // success2 = false if (success2) Console.WriteLine(person2);
Очереди — довольно часто встречаемая стуктура в реальной жизни. Например, очередь пациентов на прием к врачу. Реализуем данную ситуацию:
var patients = new Queue(); patients.Enqueue(new Person("Tom")); patients.Enqueue(new Person("Bob")); patients.Enqueue(new Person("Sam")); var practitioner = new Doctor(); practitioner.TakePatients(patients); class Person < public string Name < get; >public Person(string name) => Name = name; > class Doctor < public void TakePatients(Queuepatients) < while(patients.Count >0) < var patient = patients.Dequeue(); Console.WriteLine($"Осмотр пациента "); > Console.WriteLine("Доктор закончил осматривать пациентов"); > >
Здесь класс врача — класс Doctor в методе TakePatients принимает очередь пациентов в виде объектов Person. И пока в очереди есть объекты извлекает по одному объекту. Консольный вывод:
Осмотр пациента Tom Осмотр пациента Bob Осмотр пациента Sam Доктор закончил осматривать пациентов
Очередь
Очередь (англ. queue) — это структура данных, добавление и удаление элементов в которой происходит путём операций [math] \mathtt [/math] и [math] \mathtt [/math] соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
- [math] \mathtt [/math] — проверка очереди на наличие в ней элементов,
- [math] \mathtt [/math] (запись в очередь) — операция вставки нового элемента,
- [math] \mathtt [/math] (снятие с очереди) — операция удаления нового элемента,
- [math] \mathtt [/math] — операция получения количества элементов в очереди.
Реализация циклической очереди на массиве
Очередь, способную вместить не более [math]\mathtt[/math] элементов, можно реализовать с помощью массива [math]\mathtt
- [math]\mathtt[/math] — голова очереди,
- [math]\mathtt[/math] — хвост очереди.
empty
boolean empty(): return head == tail
push
function push(x : T): if (size() != n) elements[tail] = x tail = (tail + 1) % n
pop
T pop(): if (empty()) return null x = elements[head] head = (head + 1) % n return x
size
int size() if head > tail return n - head + tail else return tail - head
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за [math]O(1)[/math] времени.
- проста в разработке,
- по сравнению с реализацией на списке есть незначительная экономия памяти.
- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
Реализация на списке
Для данной реализации очереди необходимо создать список [math]list[/math] и операции работы на созданном списке.
Реализация очереди на односвязном списке:
List
- ListItem(data : T, next : ListItem) — конструктор,
- [math]\mathtt[/math] — поле, в котором хранится значение элемента,
- [math]\mathtt[/math] — указатель на следующий элемент очереди.
push
function push(x : T): element = tail tail = ListItem(x, NULL) if size == 0 head = tail else element.next = tail size++
pop
T pop(): size-- element = head head = head.next return element
empty
boolean empty(): return head == tail
- каждая операция выполняется за время [math]O(1)[/math] .
- память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
Реализация на двух стеках
Очередь можно реализовать на двух стеках [math]\mathtt[/math] и [math]\mathtt[/math] . Поступим следующим образом: [math]\mathtt[/math] будем использовать для операции [math] \mathtt [/math] , [math]\mathtt[/math] для операции [math] \mathtt [/math] . При этом, если при попытке извлечения элемента из [math]\mathtt[/math] он оказался пустым, просто перенесем все элементы из [math]\mathtt[/math] в него (при этом элементы в [math]\mathtt[/math] получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а [math]\mathtt[/math] станет пустым).
- [math] \mathtt [/math] и [math] \mathtt [/math] — функции, реализующие операцию [math] \mathtt [/math] для соответствующего стека,
- [math] \mathtt [/math] и [math] \mathtt [/math] — аналогично операции [math] \mathtt [/math] .
push
function push(x : T): pushLeft(x)
pop
T pop(): if not rightStack.empty() return popRight() else while not leftStack.empty() pushRight(popLeft()) return popRight()
При выполнении операции [math] \mathtt [/math] будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию [math] \mathtt [/math] из первого стека, третью во второй стек на финальный [math] \mathtt [/math] . Тогда для операций [math] \mathtt [/math] учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции [math] \mathtt [/math] .
Таким образом, для каждой операции требуется [math]O(1)[/math] монет, а значит, амортизационная стоимость операций [math]O(1)[/math] .
- эту реализацию несложно модифицировать для получения минимума в текущей очереди за [math]O(1)[/math] .
- если [math]\mathtt[/math] не пуст, то операция [math] \mathtt [/math] может выполняться [math]O(n)[/math] времени, в отличие от других реализаций, где [math] \mathtt [/math] всегда выполняется за [math]O(1)[/math] .
Реализация на шести стеках
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.
Подробное описание в статье Персистентная очередь.
Отличия от других реализаций
- [math]O(1)[/math] реального времени на операцию,
- возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.
- дольше в среднем выполняются операции,
- больше расход памяти,
- большая сложность реализации.
См. также
Источники информации
- Википедия — Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
- Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980
Очередь
Очередью называется упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец.
Очередь организована, в отличие от стека, согласно дисциплине обслуживания FIFO:
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
Существует несколько способов реализации очереди:
- с помощью одномерного массива;
- с помощью связанного списка;
- с помощью класса объектно-ориентированного программирования.
Простейшие операции с очередью:
- init() инициализация очереди.
- insert (q, x) — помещение элемента x в конец очереди q ( q — указатель на очередь);
- x=remove (q) — удаление элемента x из очереди q ;
- isempty(q) — возвращает 1 , если очередь пуста и 0 в противном случае;
- print(q) – вывод элементов очереди q .
Рассмотрим реализацию очереди на базе массива. Используем массив и две переменные:
- frnt – позиция первого элемента в очереди;
- rear – позиция последнего элемента в очереди
Изначально frnt=1 и rear=0 .
Очередь пуста, если rear .
Число элементов в очереди можно определить как
n = rear-frnt+1
Для реализации на базе массива используется структура
#define QMAX 100
struct queue int qu[QMAX];
int rear, frnt;
>;
Инициализация очереди
void init( struct queue *q) <
q->frnt = 1;
q->rear = 0;
return ;
>
Добавление элемента в очередь
void insert( struct queue *q, int x) <
if (q->rear < QMAX-1) <
q->rear++;
q->qu[q->rear]=x;
>
else
printf( «Очередь полна!\n» );
return ;
>
Проверка, пуста ли очередь
int isempty( struct queue *q) <
if (q->rear < q->frnt) return 1;
else return 0;
>
Вывод элементов очереди
1
2
3
4
5
6
7
8
9
10
void print( struct queue *q) <
int h;
if (isempty(q)==1) <
printf( «Очередь пуста!\n» );
return ;
>
for (h = q->frnt; hrear; h++)
printf( «%d » ,q->qu[h]);
return ;
>
Удаление элемента из очереди
1
2
3
4
5
6
7
8
9
10
int remove( struct queue *q) <
int x;
if (isempty(q)==1) <
printf( «Очередь пуста!\n» );
return (0);
>
x = q->qu[q->frnt];
q->frnt++;
return x;
>
Недостатком в предложенной реализации очереди является то, что очередь смещается в сторону старших адресов массива, что может вызвать скорое переполнение.
Для устранения этого недостатка предложена другая реализация функции удаления элемента из очереди:
1
2
3
4
5
6
7
8
9
10
11
12
13
int removex( struct queue *q) <
int x, h;
if (isempty(q)==1) <
printf( «Очередь пуста!\n» );
return 0;
>
x = q->qu[q->frnt];
for (h = q->frnt; h < q->rear; h++) <
q->qu[h] = q->qu[h+1];
>
q->rear—;
return x;
>
Пример Создать очередь из 8 элементов. Вывести ее на экран. Поочередно удалить все элементы очереди.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() <
struct queue *q;
int a;
system( «chcp 1251» );
system( «cls» );
q = (queue*)malloc( sizeof (queue));
init(q);
print(q);
for ( int i=0;i <8;i++) <
printf( «Введите элемент очереди: » );
scanf( «%d» , &a);
insert(q, a);
>
printf( «\n» );
print(q);
while (q->frnt rear) <
a = remove(q);
printf( «\nУдален элемент %d\n» , a);
print(q);
>
getchar(); getchar();
return 0;
>
Результат выполнения
Реализация очереди на базе односвязного линейного списка
struct list <
int field;
struct list *ptr;
>;
struct queue <
struct list *frnt, *rear;
>;
Инициализация очереди
Очередь пуста если q->front = q->rear = 0 .
void init( struct queue *q) <
q->frnt = 0;
q->rear = 0;
>
Проверка, пуста ли очередь
int isempty( struct queue *q) <
if (q->frnt==0)
return 1;
else
return 0;
>
Добавление элемента в очередь
Вывод элементов очереди
1
2
3
4
5
6
7
8
9
10
void print( struct queue *q) <
struct list *h;
if (isempty(q)==1) <
printf( «Очередь пуста!\n» );
return ;
>
for (h = q->frnt; h!= NULL ; h=h->ptr)
printf( «%d » ,h->field);
return ;
>
Удаление элемента из очереди
1
2
3
4
5
6
7
8
9
10
11
12
13
int remove( struct queue *q) <
struct list *temp;
int x;
if (isempty(q)==1) <
printf( «Очередь пуста!\n» );
return 0;
>
x = q->frnt->field;
temp = q->frnt;
q->frnt = q->frnt->ptr;
free(temp);
return x;
>
Получение первого элемента в очереди без его удаления
int test( struct queue *q) <
int x;
x = q->frnt->field;
return x;
>
Пример Создать очередь из 8 элементов на базе ОЛС. Вывести ее на экран. Поочередно удалить все элементы очереди.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() <
struct queue *q;
int a;
system( «chcp 1251» );
system( «cls» );
q = (queue*)malloc( sizeof (queue*));
init(q);
print(q);
for ( int i=0;i <8;i++) <
printf( «Введите элемент очереди: » );
scanf( «%d» , &a);
insert(q, a);
>
printf( «\n» );
print(q);
while (q->frnt!= NULL ) <
a = remove(q);
printf( «\nУдален элемент %d\n» , a);
print(q);
>
getchar(); getchar();
return 0;
>
Результат выполнения
Реализация очереди на базе класса ООП
#include
using namespace std;
class Queue static const int SIZE=100;
int *queue;
int frnt, rear;
public :
Queue () ;
void push ( int num ) ;
void out();
int size();
void pop();
int front();
int back();
> ;
//Конструктор
Queue::Queue() queue = new int [SIZE];
frnt = rear = 0 ;
>
//Вывод элементов очереди
void Queue::out() for ( int i=frnt+1;i
//Помещение элемента в очередь
void Queue::push ( int num ) if ( rear+1 == frnt || ( rear + 1 ==SIZE && !frnt )) cout return ;
>
rear++;
if ( rear==SIZE ) rear = 0 ;
queue [ rear ] = num;
>
// Извлечение элемента из очереди
void Queue::pop() if ( frnt == rear ) cout return ;
>
frnt++;
if ( frnt==SIZE ) frnt = 0 ;>
//Определение размера очереди
int Queue::size() int s=0;
for ( int i=frnt; i s++;
return s;
>
// Последний элемент очереди
int Queue::back() return queue[rear]; >
// Первый элемент очереди
int Queue::front() return queue[frnt+1]; >
int main() Queue queue1;
int i;
system( «chcp 1251» );
system( «cls» );
for (i= 1 ; i queue1.push ( i ) ;
cout queue1.out();
cout cout cin >> i;
queue1.push(i);
cout << "теперь очередь имеет следующий вид" queue1.out();
cout << endl << "Размер очереди:" cout cout << endl << "последний элемент:" cout cout << endl << "первый элемент" cout cout queue1.pop();
cout queue1.out();
cout queue1.push(i);
queue1.out();
cout cin.get(); cin.get();
return 0;
>
Результат выполнения