Меню

Очередь

Структуры данных / Очередь

 

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

Очередь организована, в отличие от стека, согласно дисциплине обслуживания 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;
}

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


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

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

  • Денис
    Зачем индексируется с единицы??? Теряем же один элемент данных плюс сводим с ума коллег индексацией..
    Ответить ↓
  • Danya
    Добрый вечер,такой вопрос:как вывести элементы очереди в обратном порядке?
    Ответить ↓
    • Елена Вставская
      Очередь сама по себе не предназначена для этого. Поэтому через промежуточный стек. Или воспользоваться деком (двусторонняя очередь)
      Ответить ↓
  • kudriash
    Добрый день, я сравниваю 2 очереди на основе ОЛС, но почему-то сравниваются только последние элементы. Пожалуйста подскажите как это исправить.
    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
    89
    90
    91
    92
    #define _CRT_SECURE_NO_WARNINGS
    #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; двигает начало списка, теряя указатели на уже введённые элементы. В результате мы можем работать только с последними элементами списков. Для добавления всех элементов, кроме первого, нужно использовать функцию, которая не будет смещать корень списка
      Ответить ↓
  • Валерий
    Подскажите, как можно сделать чтобы из очереди все время удалялся не первый элемент, а второй?
    Ответить ↓
  • Андрей
    Сделал свою реализацию очереди с помощью кольцевого буфера на основе массива. Я совсем чайник. Реализация - работает. Я его проверял. Прокомментируйте, пожалуйста, мое решение. Хотелось бы услышать о недостатках подхода, ошибках в алгоритме, в коде. Спасибо.
    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
    #include <stdio.h>

    #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; 
    }
    Ответить ↓
    • Андрей
      Спасибо. Но не современно как-то, не стильно. Ни структур, ни указателей... Так можно? И еще, код оказался после копипаста с дефектами. Правильный, точно работающий -
      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
      #include <stdio.h>

      #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 ... может быть очень интересно ;)
        Ответить ↓
  • Николай
    Реализация очереди на базе односвязного линейного списка Добавление элемента в очередь
    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, то есть не возвращает никакого значения. Об этом Вам компилятор и сообщает.
      Ответить ↓
      • Николай
        Но это просто скопированный код из статьи, я ничего не менял... Я скопировал весь код по реализации односвязным списком и код из примера и вот такие ошибки проявились.
        Ответить ↓

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

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

Рубрики

Реклама

Свежие записи

Социальные сети

Группа Вконтакте

Все права защищены ©
Яндекс.Метрика