Главная » Языки программирования

Queue program in cpp

Содержание
  1. Реализация queue на C++
  2. Класс queue
  3. Синтаксис
  4. Параметры
  5. Комментарии
  6. Члены
  7. Конструкторы
  8. Определения типов
  9. Функции
  10. back
  11. Возвращаемое значение
  12. Комментарии
  13. Пример
  14. container_type
  15. Комментарии
  16. Пример
  17. empty
  18. Возвращаемое значение
  19. Пример
  20. front
  21. Возвращаемое значение
  22. Комментарии
  23. Пример
  24. pop
  25. Комментарии
  26. Пример
  27. push
  28. Параметры
  29. Комментарии
  30. Пример
  31. queue
  32. Параметры
  33. Комментарии
  34. Пример
  35. size
  36. Возвращаемое значение
  37. Пример
  38. size_type
  39. Комментарии
  40. Пример
  41. value_type
  42. Комментарии
  43. Пример
  44. Очередь (queue) в C++: легко и просто!
  45. Что такое очередь
  46. Как создать очередь в С++

Реализация queue на C++

queue — это линейная структура данных который служит контейнером объектов, которые вставляются и удаляются по принципу FIFO (First-In, First-Out).

Queue имеет три основные операции: enqueue , dequeue , а также peek . Мы уже рассмотрели эти операции и реализацию структуры данных queue на C с использованием массив а также связанный список. В этом посте мы рассмотрим реализацию queue на C++ с использованием класса и STL.

Следующая реализация queue на C++ охватывает следующие операции:

  • Enqueue: Вставляет новый элемент в конец queue.
  • Dequeue: Удаляет передний элемент queue и возвращает его.
  • Peek: Возвращает передний элемент, присутствующий в queue, без исключения его из queue.
  • IsEmpty: Проверяет, пуста ли queue.
  • IsFull: Проверяет, заполнена ли queue.
  • Size: Возвращает общее количество элементов, присутствующих в queue.

Реализация queue с использованием массива:

Inserting 1
Inserting 2
Inserting 3
The front element is 1
Removing 1
Inserting 4
The queue size is 3
Removing 2
Removing 3
Removing 4
The queue is empty

Временная сложность всех вышеперечисленных операций с queueю составляет O(1) .

С использованием std::queue :

STL C++ обеспечивает std::queue класс шаблона, который ограничен только операциями постановки/удаления из очереди. Он также обеспечивает std::list который имеет push_back а также pop_front операции с семантикой LIFO. Библиотека Java содержит Queue интерфейс, определяющий операции с queueю.

Читайте также:  Переменная окружения для php

Источник

Класс queue

Класс-шаблон адаптера контейнера, который предоставляет ограничение функциональности для некоторого базового типа контейнера, ограничивая доступ к его передним и задним элементам. Элементы можно добавить на задней панели или удалить с передней стороны, а элементы можно проверить на любом конце queue .

Синтаксис

Параметры

Type
Тип данных элемента для сохранения в queue .

Container
Тип базового контейнера, используемого для реализации queue .

Комментарии

Элементы класса Type , указанные в первом параметре queue шаблона объекта, являются синонимами value_type и должны соответствовать типу элемента в базовом классе Container контейнера, заданном вторым параметром шаблона. Должен Type быть назначаемым, чтобы можно было копировать объекты этого типа и присваивать значения переменным этого типа.

Подходят базовые классы контейнеров для включения и , или любого другого контейнера последовательности, поддерживающего front операции , back , push_back и pop_front . list deque queue Класс базового контейнера инкапсулирован в адаптер контейнера, который предоставляет только ограниченный набор функций-членов контейнера последовательностей в виде открытого интерфейса.

Объекты queue равны, если и только в том случае, если элементы класса Type равны, и менее сопоставимы, если и только в том случае, если элементы класса Type менее сопоставимы.

Существует три типа адаптеров контейнеров, определенных стандартной библиотекой C++: stack , queue и priority_queue . Каждый ограничивает функциональность некоторого базового класса контейнеров для обеспечения точно управляемого интерфейса к стандартной структуре данных.

  • Класс stack поддерживает структуру данных с поддержкой последнего входа и первого выхода (LIFO). Хорошим аналогом, чтобы иметь в виду будет стек плит. Элементы (тарелки) можно вставлять, проверять или удалять только из верхней части стека, которая является последним элементом в конце базового контейнера. Ограничение доступа только к верхнему элементу является причиной использования stack класса .
  • Класс queue поддерживает структуру данных fifo. Хорошим аналогом, чтобы иметь в виду, были бы люди, выстраивающиеся в кассу банка. Элементы (люди) можно добавлять в конец очереди и удалять из начала очереди. Проверять можно как начало, так и конец очереди. Ограничение доступа только front к элементам и back таким образом является причиной использования queue класса .
  • Класс priority_queue упорядочивает свои элементы таким образом, чтобы самый большой элемент всегда был в верхней позиции. Он поддерживает вставку элемента, а также проверку и удаление верхнего элемента. Хорошим аналогом, чтобы иметь в виду, будет людей, выстраив их в выстраивание там, где они расположены по возрасту, росту или каким-то другим критериям.

Члены

Конструкторы

Определения типов

Имя Описание
container_type Тип, предоставляющий базовый контейнер для изменения в queue .
size_type Целочисленный Typedef без знака, который может представлять число элементов в queue .
value_type Тип, представляющий тип объекта, который хранится в виде элемента в queue .

Функции

Имя Описание
back Возвращает ссылку на последний и наиболее недавно добавленный элемент в конец queue .
empty Проверяет, является ли queue пустым.
front Возвращает ссылку на первый элемент в начале queue .
pop Удаляет элемент из начала queue .
push Добавляет элемент в конец queue .
size Возвращает количество элементов в контейнере queue .

back

Возвращает ссылку на последний и наиболее недавно добавленный элемент в конец queue .

reference back(); const_reference back() const;

Возвращаемое значение

Последний элемент queue объекта . queue Если объект пуст, возвращаемое значение не определено.

Комментарии

Если возвращаемое значение back присваивается const_reference , queue объект нельзя изменить. Если возвращаемое значение back присваивается reference , queue объект можно изменить.

При компиляции с использованием _ITERATOR_DEBUG_LEVEL , определенного как 1 или 2, возникает ошибка среды выполнения при попытке доступа к элементу в пустом queue . Дополнительные сведения см. в разделе Проверяемые итераторы.

Пример

// queue_back.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; queue q1; q1.push( 10 ); q1.push( 11 ); int& i = q1.back( ); const int& ii = q1.front( ); cout

container_type

Тип, предоставляющий базовый контейнер для изменения.

typedef Container container_type;

Комментарии

Этот тип является синонимом для параметра шаблона Container . Два класса контейнеров последовательности стандартной библиотеки C++ — list класс и класс по умолчанию deque — соответствуют требованиям, которые будут использоваться в качестве базового контейнера для queue объекта. Также можно использовать пользовательские типы, удовлетворяющие требованиям.

Дополнительные сведения о Container см. в разделе queue Class "Примечания".

Пример

Пример объявления и использования container_type см. в этом примере queue .

empty

Возвращаемое значение

true queue Значение , если объект пуст; false значение , queue если непустый.

Пример

// queue_empty.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; // Declares queues with default deque base container queue q1, q2; q1.push( 1 ); if ( q1.empty( ) ) cout
The queue q1 is not empty. The queue q2 is empty.

front

Возвращает ссылку на первый элемент в начале queue .

reference front(); const_reference front() const;

Возвращаемое значение

Первый элемент объекта queue . queue Если объект пуст, возвращаемое значение не определено.

Комментарии

Если возвращаемое значение front присваивается const_reference , queue объект нельзя изменить. Если возвращаемое значение front присваивается reference , queue объект можно изменить.

Функция-член возвращает в reference первый элемент управляемой последовательности, который должен быть непустой.

При компиляции с использованием _ITERATOR_DEBUG_LEVEL , определенного как 1 или 2, возникает ошибка среды выполнения при попытке доступа к элементу в пустом queue . Дополнительные сведения см. в разделе Проверяемые итераторы.

Пример

// queue_front.cpp // compile with: /EHsc #include #include int main() < using namespace std; queue q1; q1.push( 10 ); q1.push( 20 ); q1.push( 30 ); queue ::size_type i; i = q1.size( ); cout

pop

Удаляет элемент из начала queue .

Комментарии

Для queue применения функции-члена объект должен быть непустим. Верхняя часть queue — это позиция, занимаемая последним добавленным элементом, а — последним элементом в конце контейнера.

Пример

// queue_pop.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; queue q1, s2; q1.push( 10 ); q1.push( 20 ); q1.push( 30 ); queue ::size_type i; i = q1.size( ); cout
The queue length is 3. The element at the front of the queue is 10. After a pop the queue length is 2. After a pop, the element at the front of the queue is 20.

push

Добавляет элемент в конец queue .

Параметры

val
Элемент, добавленный в заднюю часть queue .

Комментарии

Задняя часть queue — это позиция, занимаемая последним добавленным элементом, и является последним элементом в конце контейнера.

Пример

// queue_push.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; queue q1; q1.push( 10 ); q1.push( 20 ); q1.push( 30 ); queue ::size_type i; i = q1.size( ); cout
The queue length is 3. The element at the front of the queue is 10.

queue

Создает queue , который является пустым или копией объекта базового контейнера.

queue(); explicit queue(const container_type& right);

Параметры

right
Контейнер const , из которого создается , queue должен быть копией.

Комментарии

Базовый контейнер по умолчанию для queue — deque . Можно также указать list как базовый контейнер, но нельзя указать vector , так как в нем отсутствует необходимая pop_front функция-член.

Пример

// queue_queue.cpp // compile with: /EHsc #include #include #include #include int main( ) < using namespace std; // Declares queue with default deque base container queue q1; // Explicitly declares a queue with deque base container queue  q2; // These lines don't cause an error, even though they // declares a queue with a vector base container queue > q3; q3.push( 10 ); // but the following would cause an error because vector has // no pop_front member function // q3.pop( ); // Declares a queue with list base container queue > q4; // The second member function copies elements from a container list li1; li1.push_back( 1 ); li1.push_back( 2 ); queue > q5( li1 ); cout
The element at the front of queue q5 is 1. The element at the back of queue q5 is 2.

size

Возвращает количество элементов в контейнере queue .

Возвращаемое значение

Текущая длина queue объекта .

Пример

// queue_size.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; queue q1, q2; queue ::size_type i; q1.push( 1 ); i = q1.size( ); cout
The queue length is 1. The queue length is now 2.

size_type

Целочисленный Typedef без знака, который может представлять число элементов в queue .

typedef typename Container::size_type size_type;

Комментарии

Тип является синонимом базового size_type контейнера, адаптированного с queue помощью .

Пример

Пример объявления и использования size_type см. в этом примере queue::front .

value_type

Тип, представляющий тип объекта, который хранится в виде элемента в queue .

typedef typename Container::value_type value_type;

Комментарии

Тип является синонимом базового value_type контейнера, адаптированного с queue помощью .

Пример

// queue_value_type.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; // Declares queues with default deque base container queue::value_type AnInt; AnInt = 69; cout << "The value_type is AnInt = " << AnInt << endl; queueq1; q1.push(AnInt); cout
The value_type is AnInt = 69 The element at the front of the queue is 69.

Источник

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

очередь c++ пример

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

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

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

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

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

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

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

очередь c++ пример

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

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

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

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

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

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

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

Источник

Оцените статью
© 2024 Программирование