Очередь


 

Очередью называется упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец.

Очередь организована, в отличие от стека, согласно дисциплине обслуживания 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
#define QMAX 100
struct queue {
  int qu[QMAX];
  int rear, frnt;
};

Инициализация очереди

1
2
3
4
5
void init(struct queue *q) {
  q->frnt = 1;
  q->rear = 0;
  return;
}

Добавление элемента в очередь

1
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;
}

Проверка, пуста ли очередь

1
2
3
4
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; h<= q->rear; 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 <= q->rear) {
    a = remove(q);
    printf("\nУдален элемент %d\n", a);
    print(q);
  }
  getchar(); getchar();
  return 0;
}

Результат выполнения
Очередь: пример

Реализация очереди на базе односвязного линейного списка

1
2
3
4
5
6
7
struct list {
  int field;
  struct list *ptr;
};
struct queue {
  struct list *frnt, *rear;
};

Инициализация очереди

Очередь пуста если q->front = q->rear = 0.

1
2
3
4
void init(struct queue *q) {
  q->frnt = 0;
  q->rear = 0;
}

Проверка, пуста ли очередь

1
2
3
4
5
6
int isempty(struct queue *q) {
  if(q->frnt==0)
    return 1;
  else
    return 0;
}

Добавление элемента в очередь

1
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);
}

Вывод элементов очереди

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;
}

Получение первого элемента в очереди без его удаления

1
2
3
4
5
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;
}

Результат выполнения
Результат выполнения: очередь

Реализация очереди на базе класса ООП

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
#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;
}

Результат выполнения
Очередь: программа


Назад: Структуры данных

Комментариев к записи: 8

  • Николай
    Реализация очереди на базе односвязного линейного списка Добавление элемента в очередь
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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); 
    }
    Вот ошибки: 1.Ошибка: значение типа "void" нельзя присвоить сущности типа "list *" 2.Ошибка: аргумент типа "int" несовместим с параметром типа "queue *" 3.Ошибка C2664: "int init(queue *)": невозможно преобразовать аргумент 1 из "int" в "queue *"

    • Елена Вставская
      Я не знаю всех подробностей реализации, но вижу, что Вы пытаетесь присвоить возвращаемое значение функции init() в q->rear. А сама функция - типа void, то есть не возвращает никакого значения. Об этом Вам компилятор и сообщает.

      • Николай
        Но это просто скопированный код из статьи, я ничего не менял... Я скопировал весь код по реализации односвязным списком и код из примера и вот такие ошибки проявились.



Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *