Очередь в C++. Если хочу создать очередь на N элементов, заполняется только на N-1. Почему так?

Question

#include <iostream>
using namespace std;

class queue {
    private:
        int* arr;
        int head, tail;
        int N;
    public:
        queue () { 
            head = 0;
            tail = 0;
            N = 10;
            arr = new int[N];
        }
        queue (int N) { 
            this->N = N;
            head = 0;
            tail = 0;
            arr = new int[N];
        }
        bool checkOverflow() {
            if (head == (tail + 1) % N) return true;
            else return false;
        }
        bool checkEmpty() {
            if (head == tail) return true;
            else return false;
        }
        void insert(int element) {
            if (checkOverflow() == true) cout << endl << endl << "QUEUE IS OVERFLOWED" << endl;
            else {
                arr[tail] = element;
                tail = (tail + 1) % N;
            }
        }
        void extract() {
            if (checkEmpty() == true) cout << endl << endl << "QUEUE IS EMPTY" << endl;
            else {
                cout << arr[head];
                head = (head + 1) % N;
            }
        }

};

int main() {
    bool answer = true;
    int element, N;
    cout << "Enter the amount of queue: ";
    cin >> N;
    queue one(N);
    do {
        cout << endl << "Enter 1 if you want to add an element;" << endl << "enter 0 if you want to extract an element" << endl;
        cin >> answer;
        if (answer == true) {
            cout << endl << "Enter the element of queue: ";
            cin >> element;
            one.insert(element);
        } else {
            cout << endl << "Extracted element: ";
            one.extract();
        }
    } while (true);
    return 0;
}

Answer 1

В замкнутой очереди признак переполнения памяти с помощью двух индексов даёт неопределённое состояние. Пустая очередь имеет индексы :

head = 0 
tail = 0

, а заполненная такие-же :

head = 0 
tail = ( 0 + N ) % N = 0

и переменная tail с доступными значениями 0 .. N-1 имеет всего N состояний. А фактически этих состояний должно быть N+1 : 0 .. N.

Можно убрать переменную tail и вместо неё хранить size - количество элементов. Тогда функция insert может выглядить так :

void insert(int element) {
  if ( size == N )
    cout << endl << endl << "QUEUE IS OVERFLOWED" << endl;
  else {
    arr [ ( head + size ) % N ] = element ;
    ++ size ;
  }
}

БЛОГ НА HUSL

Очередь в C++. Если хочу создать очередь на N элементов, заполняется только на N-1. Почему так?

Ответы (1 шт):