Очередью называется упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец.
Очередь организована, в отличие от стека, согласно дисциплине обслуживания 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;
}
Результат выполнения
а где вы взялии malloc?
#include <malloc.h>
Зачем индексируется с единицы??? Теряем же один элемент данных плюс сводим с ума коллег индексацией..
Добрый вечер,такой вопрос:как вывести элементы очереди в обратном порядке?
Очередь сама по себе не предназначена для этого. Поэтому через промежуточный стек.
Или воспользоваться деком (двусторонняя очередь)
Добрый день, я сравниваю 2 очереди на основе ОЛС, но почему-то сравниваются только последние элементы. Пожалуйста подскажите как это исправить.
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
89
90
91
92
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
struct list {
int field;
struct list * next;
};
struct queue {
struct list* head;
struct list* tail;
};
struct list * init(int a) // а- значение первого узла
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->next = NULL; // это последний узел списка
return(lst);
}
int main(void) {
setlocale(LC_ALL, ("RUS"));
struct queue q = { NULL, NULL };
int l, m, a;
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
struct queue* Qe = (struct queue*)malloc(sizeof(struct queue));
struct list* p = (struct list*)malloc(sizeof(struct list));
struct list* p1 = (struct list*)malloc(sizeof(struct list));
printf(" Введите размер первого списка: ");
scanf_s("%d", &l);
printf(" Введите размер второго списка: ");
scanf_s("%d", &m);
for (int i = 0; i < l; i++) {
printf("Введите элемент очереди1: ");
scanf("%d", &a);
Q->tail = init(a);
Q->head = Q->tail;
}
for (int i = 0; i < m; i++) {
printf("Введите элемент очереди2: ");
scanf("%d", &a);
Qe->tail = init(a);
Qe->head = Qe->tail;
}
printf("\n\n\nСравнение очередей : ");
p = Q->head;
p1 = Qe->head;
if (p->field != p1->field)
{
printf("не одинаковые\n");
}
else
{
printf("одинаковые\n");
}
system("pause");
exit(1);
}
Q->head = Q->tail; двигает начало списка, теряя указатели на уже введённые элементы. В результате мы можем работать только с последними элементами списков. Для добавления всех элементов, кроме первого, нужно использовать функцию, которая не будет смещать корень списка
Подскажите, как можно сделать чтобы из очереди все время удалялся не первый элемент, а второй?
2
3
q->qu[h] = q->qu[h+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
#define SIZE 4 // Размер массива ( очереди ). Может быть задан другой
#define size SIZE
int n = 0; // Сохраняемое в массиве число
int arr[ size ] = { 0 }; // Массив
int num = 0; // Количество элементов в очереди
int h = 0; Начальная позиция головы очереди
int t = 0; Начальная позиция хвоста очереди
int main( void )
{
while( TRUE )
{
printf( "Сделайте выбор: 1 — внести число, 0 — извлечь, 2 — выйти из программы: " );
scanf( "%d", &n );
if( n == 0 )
{
if( num == 0 )
{
printf( "Очередь пуста! \n" );
}
else
{
printf( " Из позиции очереди %d извлечено значение: %d \n", h, arr[ h ]);
printf( "Число занятых позиций очереди: %d \n\n", num );
num—;
h++;
}
if( h == size )
{
h = ( h — size );
}
}
else if( n == 1 )
{
if( num < size )
{
printf( "Ввести число: " );
scanf( "%d", &arr[ t ] );
printf( "В элемент очереди %d внесено число %d \n", ( t ), arr[ t ] );
t++;
if( t == size )
{
t = t — size;
}
num++;
printf( "Новое значение хвоста очереди: %d \n", t );
printf( "Значение головы очереди: %d \n", h );
printf( "Число занятых позиций очереди: %d \n\n", num );
}
else if( num == size )
{
printf( "Очередь заполнена \n\n" );
}
}
else if( n == 2 )
{
break ;
}
// getchar();
}
return 0;
}
Проблем не вижу
Спасибо. Но не современно как-то, не стильно. Ни структур, ни указателей… Так можно? И еще, код оказался после копипаста с дефектами. Правильный, точно работающий —
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
#define FALSE 0
#define TRUE !FALSE
#define SIZE 4 // Размер очереди
#define size SIZE
int n = 0; // Сохраняемое в массиве число
int arr[ size ] = { 0 }; // Массив
int num = 0; // Количество элементов в очереди
int h = 0; // Начальная позиция головы очереди
int t = 0; // Начальная позиция хвоста очереди
int main( void )
{
while( TRUE )
{
printf( "Сделайте выбор: 1 — внести число, 0 — извлечь, 2 — выйти из программы: " );
scanf( "%d", &n );
if( n == 0 )
{
if( num == 0 )
{
printf( "Очередь пуста! \n" );
}
else
{
printf( " Из позиции очереди %d извлечено значение: %d \n", h, arr[ h ]);
num—;
printf( "Число занятых позиций очереди: %d \n\n",( num ) );
h++;
}
if( h == size )
{
h = ( h — size );
}
}
else if( n == 1 )
{
if( num < size )
{
printf( "Ввести число: " );
scanf( "%d", &arr[ t ] );
printf( "В элемент очереди %d внесено число %d \n",t ,arr[ t ] );
t++;
if( t == size )
{
t = t — size;
}
num++;
printf( "Новое значение хвоста очереди: %d \n", t );
printf( "Значение головы очереди: %d \n", h );
printf( "Число занятых позиций очереди: %d \n\n", num );
}
else if( num == size )
{
printf( "Очередь заполнена \n\n" );
}
}
else if( n == 2 )
{
break ;
}
// getchar();
}
return 0;
}
Вы уж или удалите полностью мое "творение", или вставьте, пожалуйста, правильный код. А то стыдно мне, вдруг — кому-то придет в голову скопировать и проверить (
Доброго дня!
Тема кольцевого буфера увлекла. Прикольный эффект обнаружил, если вас, вдруг, устроил бы размер буфера в 256 значений. Тогда, если объявить размер массива const unsigned char … может быть очень интересно 😉
Реализация очереди на базе односвязного линейного списка
Добавление элемента в очередь
2
3
4
5
6
7
8
9
10
{
if ((q->rear == 0) && (q->frnt == 0))
{
q->rear = init(x); // На эту строку ругается компилятор, подскажите пожалуйста, из-за чего?
q->frnt = q->rear;
}
else
q->rear = addelem(q->rear, x);
}
Вот ошибки:
1.Ошибка: значение типа "void" нельзя присвоить сущности типа "list *"
2.Ошибка: аргумент типа "int" несовместим с параметром типа "queue *"
3.Ошибка C2664: "int init(queue *)": невозможно преобразовать аргумент 1 из "int" в "queue *"
Я не знаю всех подробностей реализации, но вижу, что Вы пытаетесь присвоить возвращаемое значение функции init() в q->rear. А сама функция — типа void, то есть не возвращает никакого значения. Об этом Вам компилятор и сообщает.
Но это просто скопированный код из статьи, я ничего не менял… Я скопировал весь код по реализации односвязным списком и код из примера и вот такие ошибки проявились.
Дополните проект функциями init() и addelem() для односвязного линейного списка
Переименуйте перед копированием init(int a) во что-нибудь другое — язык С в классическом варианте не поддерживает полиморфизм функций.
2
q->rear = addelem(q->rear, x);
Откуда здесь addelem?
addelem() — это функция добавления элемента односвязного линейного списка
Спасибо, эти информации были полезны