Очередью называется упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец.
Очередь организована, в отличие от стека, согласно дисциплине обслуживания FIFO:
- FIRST - первый
- INPUT - вошел
- FIRST - первый
- OUTPUT - вышел
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в 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<frnt.
Число элементов в очереди можно определить как
n = rear-frnt+1
Для реализации на базе массива используется структура
1
2
3
4
5
2
3
4
5
#define QMAX 100
struct queue {
int qu[QMAX];
int rear, frnt;
};
struct queue {
int qu[QMAX];
int rear, frnt;
};
Инициализация очереди
1
2
3
4
5
2
3
4
5
void init(struct queue *q) {
q->frnt = 1;
q->rear = 0;
return;
}
q->frnt = 1;
q->rear = 0;
return;
}
Добавление элемента в очередь
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
void insert(struct queue *q, int x) {
if(q->rear < QMAX-1) {
q->rear++;
q->qu[q->rear]=x;
}
else
printf("Очередь полна!\n");
return;
}
if(q->rear < QMAX-1) {
q->rear++;
q->qu[q->rear]=x;
}
else
printf("Очередь полна!\n");
return;
}
Проверка, пуста ли очередь
1
2
3
4
2
3
4
int isempty(struct queue *q) {
if(q->rear < q->frnt) return 1;
else return 0;
}
if(q->rear < q->frnt) return 1;
else return 0;
}
Вывод элементов очереди
1
2
3
4
5
6
7
8
9
10
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; h<= q->rear; h++)
printf("%d ",q->qu[h]);
return;
}
int h;
if(isempty(q)==1) {
printf("Очередь пуста!\n");
return;
}
for(h = q->frnt; h<= q->rear; h++)
printf("%d ",q->qu[h]);
return;
}
Удаление элемента из очереди
1
2
3
4
5
6
7
8
9
10
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;
}
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
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;
}
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
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 <= q->rear) {
a = remove(q);
printf("\nУдален элемент %d\n", a);
print(q);
}
getchar(); getchar();
return 0;
}
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 <= q->rear) {
a = remove(q);
printf("\nУдален элемент %d\n", a);
print(q);
}
getchar(); getchar();
return 0;
}
Результат выполнения
Реализация очереди на базе односвязного линейного списка
1
2
3
4
5
6
7
2
3
4
5
6
7
struct list {
int field;
struct list *ptr;
};
struct queue {
struct list *frnt, *rear;
};
int field;
struct list *ptr;
};
struct queue {
struct list *frnt, *rear;
};
Инициализация очереди
Очередь пуста если q->front = q->rear = 0.
1
2
3
4
2
3
4
void init(struct queue *q) {
q->frnt = 0;
q->rear = 0;
}
q->frnt = 0;
q->rear = 0;
}
Проверка, пуста ли очередь
1
2
3
4
5
6
2
3
4
5
6
int isempty(struct queue *q) {
if(q->frnt==0)
return 1;
else
return 0;
}
if(q->frnt==0)
return 1;
else
return 0;
}
Добавление элемента в очередь
1
2
3
4
5
6
7
2
3
4
5
6
7
void insert(struct queue *q, int x) {
if((q->rear==0) && (q->frnt==0)) {
q->rear = init(x);
q->frnt = q->rear;
} else
q->rear = addelem(q->rear, x);
}
if((q->rear==0) && (q->frnt==0)) {
q->rear = init(x);
q->frnt = q->rear;
} else
q->rear = addelem(q->rear, x);
}
Вывод элементов очереди
1
2
3
4
5
6
7
8
9
10
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;
}
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
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;
}
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;
}
Получение первого элемента в очереди без его удаления
1
2
3
4
5
2
3
4
5
int test(struct queue *q) {
int x;
x = q->frnt->field;
return x;
}
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
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;
}
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;
}
Результат выполнения
Реализация очереди на базе класса ООП
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
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<rear+1;i++)
cout<<" "<<queue[i];
}
//Помещение элемента в очередь
void Queue::push ( int num ) {
if ( rear+1 == frnt || ( rear + 1 ==SIZE && !frnt )) {
cout << "очередь полна" <<endl ;
return ;
}
rear++;
if ( rear==SIZE ) rear = 0 ;
queue [ rear ] = num;
}
// Извлечение элемента из очереди
void Queue::pop() {
if ( frnt == rear ) {
cout << "очередь пуста" <<endl ;
return;
}
frnt++;
if ( frnt==SIZE ) frnt = 0 ;}
//Определение размера очереди
int Queue::size() {
int s=0;
for(int i=frnt; i<rear; 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 <= 5 ; i++ )
queue1.push ( i ) ;
cout<<"Изначальная очередь ";
queue1.out();
cout<<endl;
cout<<"введите еще элемент: ";
cin>>i;
queue1.push(i);
cout<<"теперь очередь имеет следующий вид"<<endl;
queue1.out();
cout<<endl<<"Размер очереди:"<<endl;
cout<<queue1.size();
cout<<endl <<"последний элемент:"<< endl;
cout<<queue1.back();
cout<<endl<<"первый элемент"<<endl;
cout<<queue1.front();
cout<<endl <<"удаление элемента";
queue1.pop();
cout<<endl <<"текущие данные";
queue1.out();
cout<<endl <<"еще одно добавление элемента";
queue1.push(i);
queue1.out();
cout<<endl;
cin.get(); cin.get();
return 0;
}
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<rear+1;i++)
cout<<" "<<queue[i];
}
//Помещение элемента в очередь
void Queue::push ( int num ) {
if ( rear+1 == frnt || ( rear + 1 ==SIZE && !frnt )) {
cout << "очередь полна" <<endl ;
return ;
}
rear++;
if ( rear==SIZE ) rear = 0 ;
queue [ rear ] = num;
}
// Извлечение элемента из очереди
void Queue::pop() {
if ( frnt == rear ) {
cout << "очередь пуста" <<endl ;
return;
}
frnt++;
if ( frnt==SIZE ) frnt = 0 ;}
//Определение размера очереди
int Queue::size() {
int s=0;
for(int i=frnt; i<rear; 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 <= 5 ; i++ )
queue1.push ( i ) ;
cout<<"Изначальная очередь ";
queue1.out();
cout<<endl;
cout<<"введите еще элемент: ";
cin>>i;
queue1.push(i);
cout<<"теперь очередь имеет следующий вид"<<endl;
queue1.out();
cout<<endl<<"Размер очереди:"<<endl;
cout<<queue1.size();
cout<<endl <<"последний элемент:"<< endl;
cout<<queue1.back();
cout<<endl<<"первый элемент"<<endl;
cout<<queue1.front();
cout<<endl <<"удаление элемента";
queue1.pop();
cout<<endl <<"текущие данные";
queue1.out();
cout<<endl <<"еще одно добавление элемента";
queue1.push(i);
queue1.out();
cout<<endl;
cin.get(); cin.get();
return 0;
}
Результат выполнения
