Очередь (queue) в C++: легко и просто!

Всем привет! Для решения задач многие программисты используют структуру данных - очередь. Вы наверно когда-то слышали о ней, а возможно и применяли в своей программе.

Мы попытаемся ответить на несколько вопросов: что такое очередь, принцип работы очереди и какая у нее есть разновидность. Поехали!

Эта статья будет полезна не только новичкам, но и уже обросшим программистам :) .

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Что такое очередь

Очередь - это структура данных (как было сказано выше), которая построена по принципу FIFO (first in - first out: первым пришел - первым вышел). В C++ уже есть готовый STL контейнер - queue.

В очереди, если вы добавите элемент, который вошел первым, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым.

Чтобы понять принцип работы очереди вы можете представить себе магазинную очередь. И вы стоите посреди нее, чтобы вы оказались напротив кассы, сначала понадобится всех впереди стоящих людей обслужить. А вот для последнего человека в очереди нужно, чтобы кассир обслужил всех людей кроме него самого.

На рисунке слева находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке!

Так например чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4.

Хотя в стеке присутствует функция peek() (она позволяет обратится к элементу по индексу, подробнее вот здесь), в шаблоне очереди невозможно обратится к определенному элементу.

Но если вам нужно иметь доступ ко всем элементам очереди, то можете реализовать очередь через массив. Чуть ниже мы покажем как это сделать.

Как создать очередь в C++

Если вы хотите использовать шаблон очереди в C++, то вам сначала нужно подключить библиотеку - <queue>.

Дальше для объявления очереди нужно воспользоваться конструкцией ниже.

queue <тип данных> <имя>;

• Сначала нам нужно написать слова queue.
• Дальше в <тип данных> мы должны указать тот тип, которым будем заполнять нашу очередь.
• И в конце нам остается только указать название очереди.

Вот пример правильного объявления:

queue <int> q;

Методы очереди

Метод - это та же самая функция, но она работает только с контейнерами STL. Например, очередь и стек.

Для работы с очередью вам понадобится знать функции: push(), pop(), front(), back(), empty(). Кстати, если хотите узнать, как в C++ работают функции и как их правильно использовать в проекте, то можете узнать все это здесь.

1. Для добавления в очередь нового элемента нужно воспользоваться функцией - push(). В круглых скобках должно находится значение, которое мы хотим добавить.
2. Если нам понадобилось удалить первый элемент нужно оперировать функцией pop(). В круглых скобках уже не чего не нужно указывать, но по правилам они в обязательном порядке должны присутствовать! Эти функции тоже не нуждаются в указании аргумента: empty(), back() и front().
3. Если вам понадобилось обратиться к первому элементу очереди, то вам понадобится функция front().
4. Чтобы обратиться к последнему элементу в очереди вам поможет функция back().
5. Чтобы узнать пуста ли очередь нужно воспользоваться функцией empty().
   • Если ваша очередь пуста - возвратит true.
   • Если же в ней что-то есть - возвратит false.

Ниже мы использовали все выше перечисленные методы:

#include <iostream>
#include <queue>  // подключили библиотеку queue

using namespace std;

int main() {
  setlocale(LC_ALL,"rus");
  queue <int> q;  // создали очередь q
  
  cout << "Пользователь, пожалуйста введите 7 чисел: " << endl;

  for (int h = 0; h < 7; h++) { 
    int a; 
    
    cin >> a;
      
    q.push(a);  // добавляем в очередь элементы
  }
  
  cout << endl;
  cout << "Первый элемент в очереди: " << q.front() << endl;  // выводим первый
                                                                   // элемент очереди
  q.pop();  // удаляем элемент из очереди
    
  cout << "Новый первый элемент (после удаления): " << q.front() << endl;
    
  if (!q.empty()) cout << "Очередь не пуста!";  // проверяем пуста ли очередь (нет)
    
  system("pause");
  return 0;
}

Давайте посмотрим, как будет выглядеть консоль при запуске:

Пользователь пожалуйста введите 7 чисел:
6 4 2 1 6 3 6
Первый элемент в очереди: 6
Новый первый элемент (после удаления): 4
Очередь не пуста!
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Создание очереди с помощью массива

Как мы говорили выше, очередь можно реализовать через массив. Обычно, если кто-то создает такую очередь, то массив называют queue. Мы бы также назвали массив, но это уже зарезервированное слова в C++. Поэтому его назовем так, как назвали выше шаблон очереди - q.

Для реализации нам понадобится создать две дополнительные переменные start и ends. start будет указывать на первый элемент очереди, a ends на последний элемент.

Чтобы обратится к последнему элементу нам придется использовать эту конструкцию - queue[ends]. Обращение к первому элементу будет выглядеть аналогично queue[start].

Если понадобится удалить элемент из очереди, то придется всего лишь уменьшить переменную start на один.

“А как же проверить пуста ли очередь?” - спросите вы. Для этого мы просто проверим условие start == ends:

1. Если результатом условия будет true, то очередь пуста.
2. Если же результат условия false, значит очередь чем-то заполнена.

Ниже находится живой пример создания такой очереди:

  setlocale(LC_ALL,"rus");
  int q[7];  // создали массив q
  int start = 0, ends = 0;  // создали переменные начала и конца очереди

  cout << "Пользователь, пожалуйста введите 7 чисел: " << endl;

  for (int h = 0; h < 7; h++) { int a; cin >> a;
    int a;

    cin >> a;

    q[ends++] = a;  // добавляем элементы в очередь(массив)
  }

  cout << "Первый элемент в очереди: " << q[start] << endl;
 
  start++;  // удаляем первый элемент(увеличиваем индекс начала очереди на 1)

  cout << "Новый первый элемент (после удаления): " << q[start] << endl;

  cout << "Последний элемент в очереди: " << q[ends - 1];  // выводим последний
                                                                 // элемент очереди
  if (start != ends) cout << "Очередь заполнена!";        // проверяем пуста ли очередь

Очередь с приоритетом

Очередь с приоритетом (priority_queue) - это обычная очередь, но в ней новый элемент добавляется в то место, чтобы очередь была отсортирована по убыванию.

Так самый большой элемент в приоритетной очереди будет стоять на первом месте.

Для объявления шаблона очереди с приоритетом нужно использовать конструкцию ниже:

priority_queue <тип данных> <имя>;

• В начале нужно написать priority_queue.
• Потом в скобках указать тип данных, который будет находится в очереди.
• И конечно же в самом конце мы должны дать ей имя.

Для добавления элемента в очередь с приоритетом мы должны использовать функцию push(). Но чтобы обратится к первому элементу должны использоваться именно функция - top() (как и в стеке). А не функция - front().

Также нельзя использовать функцию back() для обращения к последнему элементу. Для приоритетной очереди она также не работает, как функция front().

Вот пример использования очереди с приоритетом в программе:

  setlocale(LC_ALL,"rus");
  
  priority_queue <int> priority_q;  // объявляем приоритетную очередь
  
  cout << "Введите 7 чисел: " << endl;
  
  for (int j = 0; j < 7; j++) { int a; cin >> a;
    
    priority_q.push(a);  // добавляем элементы в очередь
  }
                                                          // выводим первый
  cout << "Первый элемент очереди: " << priority_q.top();  // элемент

Какой вид создания очереди использовать

Сегодня мы изучили два способа реализации очереди:

• Реализация через шаблон C++.
• Реализация через массив.

Лично мы всегда используем первый способ реализации очереди. Он работает быстрее чем второй способ и реализация совсем простая.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Упражнение

Если вы хотите усвоить данный материал то:

1. Создайте очередь.
2. Предложите пользователю ввести 7 чисел.
3. Добавьте все 7 чисел в очередь.
4. Выведите одно число.
5. Удалите 1 число из очереди.
6. Проверьте пуста ли очередь.

Мы рады, если в этой статье вы узнали что-то новое!

Мы советуем вам изучить еще одну важную структуру данных STL - стек. Ее использование вы можете встретить во многих больших проектах.

Если есть вопрос, то пиши в комментарии, мы с радостью вам ответим. Удачи!

« Следующий урок

Предыдущий урок »