fork download
copy 
  1. #include <iostream>
  2. #include <stdexcept>
  3. #include <cstddef>
  4.  
  5. template <typename T>
  6. class CircularQueue {
  7. private:
  8.     T* data;                    // Массив для хранения элементов
  9.     std::size_t capacity;       // Максимальная вместимость
  10.     std::size_t frontIndex;     // Индекс первого элемента
  11.     std::size_t rearIndex;      // Индекс следующей свободной позиции
  12.     std::size_t count;          // Текущее количество элементов
  13.  
  14. public:
  15.     // Конструктор
  16.     explicit CircularQueue(std::size_t capacity)
  17.         : data(nullptr),
  18.           capacity(capacity),
  19.           frontIndex(0),
  20.           rearIndex(0),
  21.           count(0) {
  22.  
  23.         if (capacity == 0) {
  24.             throw std::invalid_argument(
  25.                 "Capacity must be greater than 0"
  26.             );
  27.         }
  28.  
  29.         data = new T[capacity];
  30.     }
  31.  
  32.     // Деструктор
  33.     ~CircularQueue() {
  34.         delete[] data;
  35.     }
  36.  
  37.     // Запрещаем копирование, чтобы избежать двойного освобождения памяти
  38.     CircularQueue(const CircularQueue&) = delete;
  39.     CircularQueue& operator=(const CircularQueue&) = delete;
  40.  
  41.     // Проверка на пустоту
  42.     bool isEmpty() const noexcept {
  43.         return count == 0;
  44.     }
  45.  
  46.     // Проверка на заполненность
  47.     bool isFull() const noexcept {
  48.         return count == capacity;
  49.     }
  50.  
  51.     // Текущий размер очереди
  52.     std::size_t size() const noexcept {
  53.         return count;
  54.     }
  55.  
  56.     // Максимальный размер очереди
  57.     std::size_t maxSize() const noexcept {
  58.         return capacity;
  59.     }
  60.  
  61.     // Добавление элемента в конец очереди
  62.     void enqueue(const T& value) {
  63.         if (isFull()) {
  64.             throw std::overflow_error("Queue is full");
  65.         }
  66.  
  67.         data[rearIndex] = value;
  68.  
  69.         // Циклический переход к следующей позиции
  70.         rearIndex = (rearIndex + 1) % capacity;
  71.  
  72.         ++count;
  73.     }
  74.  
  75.     // Удаление элемента из начала очереди
  76.     void dequeue() {
  77.         if (isEmpty()) {
  78.             throw std::underflow_error("Queue is empty");
  79.         }
  80.  
  81.         // Просто перемещаем индекс начала.
  82.         // Сами элементы массива не сдвигаются.
  83.         frontIndex = (frontIndex + 1) % capacity;
  84.  
  85.         --count;
  86.     }
  87.  
  88.     // Получение первого элемента
  89.     T& front() {
  90.         if (isEmpty()) {
  91.             throw std::underflow_error("Queue is empty");
  92.         }
  93.  
  94.         return data[frontIndex];
  95.     }
  96.  
  97.     const T& front() const {
  98.         if (isEmpty()) {
  99.             throw std::underflow_error("Queue is empty");
  100.         }
  101.  
  102.         return data[frontIndex];
  103.     }
  104.  
  105.     // Получение последнего элемента
  106.     T& back() {
  107.         if (isEmpty()) {
  108.             throw std::underflow_error("Queue is empty");
  109.         }
  110.  
  111.         std::size_t index =
  112.             (rearIndex + capacity - 1) % capacity;
  113.  
  114.         return data[index];
  115.     }
  116.  
  117.     const T& back() const {
  118.         if (isEmpty()) {
  119.             throw std::underflow_error("Queue is empty");
  120.         }
  121.  
  122.         std::size_t index =
  123.             (rearIndex + capacity - 1) % capacity;
  124.  
  125.         return data[index];
  126.     }
  127.  
  128.     // Очистка очереди
  129.     void clear() noexcept {
  130.         frontIndex = 0;
  131.         rearIndex = 0;
  132.         count = 0;
  133.     }
  134.  
  135.     // Вывод содержимого очереди
  136.     void print() const {
  137.         if (isEmpty()) {
  138.             std::cout << "Queue: empty\n";
  139.             return;
  140.         }
  141.  
  142.         std::cout << "Queue: ";
  143.  
  144.         for (std::size_t i = 0; i < count; ++i) {
  145.             std::size_t index =
  146.                 (frontIndex + i) % capacity;
  147.  
  148.             std::cout << data[index];
  149.  
  150.             if (i + 1 < count) {
  151.                 std::cout << " ";
  152.             }
  153.         }
  154.  
  155.         std::cout << '\n';
  156.     }
  157.  
  158.     // Вывод внутреннего состояния для демонстрации
  159.     // работы циклического массива
  160.     void printState() const {
  161.         std::cout << "frontIndex = " << frontIndex
  162.                   << ", rearIndex = " << rearIndex
  163.                   << ", size = " << count
  164.                   << ", capacity = " << capacity
  165.                   << '\n';
  166.     }
  167. };
  168.  
  169.  
  170. int main() {
  171.     try {
  172.         // Создание циклической очереди вместимостью 5 элементов
  173.         CircularQueue<int> queue(5);
  174.  
  175.         std::cout << "=== 1. Initial state ===\n";
  176.         queue.print();
  177.         queue.printState();
  178.  
  179.         // ---------------------------------------------------------
  180.         // 2. Добавление элементов
  181.         // ---------------------------------------------------------
  182.         std::cout << "\n=== 2. Enqueue ===\n";
  183.  
  184.         queue.enqueue(10);
  185.         queue.enqueue(20);
  186.         queue.enqueue(30);
  187.  
  188.         queue.print();
  189.         queue.printState();
  190.  
  191.         // ---------------------------------------------------------
  192.         // 3. Просмотр первого и последнего элемента
  193.         // ---------------------------------------------------------
  194.         std::cout << "\n=== 3. Front / Back ===\n";
  195.  
  196.         std::cout << "Front: " << queue.front() << '\n';
  197.         std::cout << "Back: " << queue.back() << '\n';
  198.  
  199.         // ---------------------------------------------------------
  200.         // 4. Удаление элементов
  201.         // ---------------------------------------------------------
  202.         std::cout << "\n=== 4. Dequeue ===\n";
  203.  
  204.         queue.dequeue();
  205.  
  206.         std::cout << "After dequeue:\n";
  207.         queue.print();
  208.         queue.printState();
  209.  
  210.         // ---------------------------------------------------------
  211.         // 5. Демонстрация циклического использования массива
  212.         // ---------------------------------------------------------
  213.         std::cout << "\n=== 5. Circular array test ===\n";
  214.  
  215.         queue.enqueue(40);
  216.         queue.enqueue(50);
  217.         queue.enqueue(60);
  218.  
  219.         queue.print();
  220.         queue.printState();
  221.  
  222.         /*
  223.          * После удаления первого элемента освободилась первая
  224.          * позиция массива. Благодаря оператору %
  225.          * rearIndex продолжает движение циклически и использует
  226.          * освободившееся место, не сдвигая остальные элементы.
  227.          */
  228.  
  229.         // ---------------------------------------------------------
  230.         // 6. Заполнение очереди до максимальной вместимости
  231.         // ---------------------------------------------------------
  232.         std::cout << "\n=== 6. Full queue test ===\n";
  233.  
  234.         // Сейчас в очереди 5 элементов
  235.         queue.print();
  236.  
  237.         std::cout << "Is full: "
  238.                   << (queue.isFull() ? "yes" : "no")
  239.                   << '\n';
  240.  
  241.         // ---------------------------------------------------------
  242.         // 7. Проверка переполнения
  243.         // ---------------------------------------------------------
  244.         std::cout << "\n=== 7. Overflow test ===\n";
  245.  
  246.         try {
  247.             queue.enqueue(70);
  248.         }
  249.         catch (const std::overflow_error& error) {
  250.             std::cout << "Overflow handled correctly: "
  251.                       << error.what() << '\n';
  252.         }
  253.  
  254.         // ---------------------------------------------------------
  255.         // 8. Проверка удаления и повторного циклического добавления
  256.         // ---------------------------------------------------------
  257.         std::cout << "\n=== 8. Reuse freed position ===\n";
  258.  
  259.         queue.dequeue();
  260.         queue.dequeue();
  261.  
  262.         queue.print();
  263.         queue.printState();
  264.  
  265.         // Добавляем элементы в освободившиеся позиции
  266.         queue.enqueue(70);
  267.         queue.enqueue(80);
  268.  
  269.         queue.print();
  270.         queue.printState();
  271.  
  272.         // ---------------------------------------------------------
  273.         // 9. Проверка размера очереди
  274.         // ---------------------------------------------------------
  275.         std::cout << "\n=== 9. Size test ===\n";
  276.  
  277.         std::cout << "Current size: "
  278.                   << queue.size() << '\n';
  279.  
  280.         std::cout << "Maximum size: "
  281.                   << queue.maxSize() << '\n';
  282.  
  283.         // ---------------------------------------------------------
  284.         // 10. Очистка очереди
  285.         // ---------------------------------------------------------
  286.         std::cout << "\n=== 10. Clear ===\n";
  287.  
  288.         queue.clear();
  289.  
  290.         queue.print();
  291.         queue.printState();
  292.  
  293.         std::cout << "Is empty: "
  294.                   << (queue.isEmpty() ? "yes" : "no")
  295.                   << '\n';
  296.  
  297.         // ---------------------------------------------------------
  298.         // 11. Проверка удаления из пустой очереди
  299.         // ---------------------------------------------------------
  300.         std::cout << "\n=== 11. Underflow test ===\n";
  301.  
  302.         try {
  303.             queue.dequeue();
  304.         }
  305.         catch (const std::underflow_error& error) {
  306.             std::cout << "Underflow handled correctly: "
  307.                       << error.what() << '\n';
  308.         }
  309.  
  310.         // ---------------------------------------------------------
  311.         // 12. Проверка добавления после очистки
  312.         // ---------------------------------------------------------
  313.         std::cout << "\n=== 12. Reuse after clear ===\n";
  314.  
  315.         queue.enqueue(100);
  316.         queue.enqueue(200);
  317.  
  318.         queue.print();
  319.  
  320.         std::cout << "Front: " << queue.front() << '\n';
  321.         std::cout << "Back: " << queue.back() << '\n';
  322.  
  323.         std::cout << "\n=== All tests completed successfully ===\n";
  324.     }
  325.     catch (const std::invalid_argument& error) {
  326.         std::cerr << "Invalid argument: "
  327.                   << error.what() << '\n';
  328.  
  329.         return 1;
  330.     }
  331.     catch (const std::exception& error) {
  332.         std::cerr << "Unexpected error: "
  333.                   << error.what() << '\n';
  334.  
  335.         return 1;
  336.     }
  337.  
  338.     return 0;
  339. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== 1. Initial state ===
Queue: empty
frontIndex = 0, rearIndex = 0, size = 0, capacity = 5

=== 2. Enqueue ===
Queue: 10 20 30
frontIndex = 0, rearIndex = 3, size = 3, capacity = 5

=== 3. Front / Back ===
Front: 10
Back: 30

=== 4. Dequeue ===
After dequeue:
Queue: 20 30
frontIndex = 1, rearIndex = 3, size = 2, capacity = 5

=== 5. Circular array test ===
Queue: 20 30 40 50 60
frontIndex = 1, rearIndex = 1, size = 5, capacity = 5

=== 6. Full queue test ===
Queue: 20 30 40 50 60
Is full: yes

=== 7. Overflow test ===
Overflow handled correctly: Queue is full

=== 8. Reuse freed position ===
Queue: 40 50 60
frontIndex = 3, rearIndex = 1, size = 3, capacity = 5
Queue: 40 50 60 70 80
frontIndex = 3, rearIndex = 3, size = 5, capacity = 5

=== 9. Size test ===
Current size: 5
Maximum size: 5

=== 10. Clear ===
Queue: empty
frontIndex = 0, rearIndex = 0, size = 0, capacity = 5
Is empty: yes

=== 11. Underflow test ===
Underflow handled correctly: Queue is empty

=== 12. Reuse after clear ===
Queue: 100 200
Front: 100
Back: 200

=== All tests completed successfully ===
https://ideone.com/J4ikfm
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!