Реализация очереди на C

[Груша Вильямс]

Можно ли написать очередь без использования структур, указателей и списков? То есть исключительно манипулируя функциями, массивами и переменными.

@темы: C++, Алгоритм

Comments

[CD_Eater]

типичная реализация очереди - это массив и две переменные (хранящие индексы головы и хвоста очереди)

[Груша Вильямс]

CD_Eater, можете показать как это делается?

[CD_Eater]

ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D1%8C%...
forum.vingrad.ru/forum/topic-344036.html

[Kot Dymok]

Груша Вильямс, Набросал прямо здесь, потому могут быть ошибки:

При помощи std::vector:

std::vector<int> queue = {}; //Очередь
// Добавление:
queue.push_back(value); //Добавляем в хвост очереди
// Удаление из очереди:
if(!queue.empty()){
  output = queue.at(0);
  queue.erase(queue.begin());
}

При помощи стандартного массива:

int N = 100; // Стандартный размер пула
uint queueBegin = 0; // Голова очереди
uint qeueEnd = 0; // Хвост очереди
int* queue = malloc(N * sizeof(int)); // Сама очередь
uint endMemory = N; // Размер выделенного пула
// Добавление:
// Проверка на окончание выделенной памяти
if(queueEnd == endMemory){
  if(queueBegin!=0){ //Или сдвигаем используемую часть массива в начало массива
    uint p = 0 
    for(uint i = queueBegin; i<queueEnd; i++){
      queue[p++] = queue[i];
    }
    queueEnd=p;
  }else{ //Или выделяем еще помяти
    endMemory+=N;
    int* queueTmp = malloc(endMemory*sizeof(int));
    for(uint i = queueBegin; i<queueEnd; i++){
      queueTmp[i] = queue[i];
    }
    free(queue);
    queue = queueTmp;
  }
}
//Само добавление  
queue[queueEnd++] = value;

// Удаление:
if(queueBegin!=queueEnd)
  output=queue[queueBegin++];

[Груша Вильямс]

CD_Eater, спасибо, но этот код для ЮАРТа слишком крут для меня пока что)

Kot Dymok, через вектор мне не очень подходит, поэтому и написал на С (как понимаю он в С++ только), не подходит потому, что вектор динамический массив. Через функцию маллок ближе уже, но тоже не то, так как имеется динамическое выделение памяти. Хотелось бы на обычном статичном массиве. Скажем я заведомо знаю, что данных у меня на 10 элементов в исходном массиве (инициализирую его сам с клавиатуры 0,1,2,...,9), затем у меня есть второй пустой массив также на 10 элементов (инициализирую его нулями 0,0,0,...,0) и данные поступают следующим образом:
- в нулевой элемент пустого массива отправляется нулевой элемент данных, то есть 0, в первый элемент - 1, во второй - 2, ..., в девятый 9;
- отправка осуществляется поэлементно, на каждой итерации ровно один элемент;
- после того как все элементы отправлены происходит циклический сдвиг всех элементов на 1 позицию вправо, но голова уходит в хвост;
- такой циклический сдвиг происходит, например, N раз, где N я ввожу с клавиатуры.
Это же будет очередью?
Решение интересует исключительно в образовательных целях, чтоб получше представлять структуру.