Задачата с опашката (Горещ картоф)

[teodo...@abv.bg]

(Ще описвам по примера, който ми даде Даниел Илиев, защото ми хареса как той е описал програмата.)

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

typedef struct Queue Queue;

struct Queue
{
  int *items;
  int head;
  int tail;
  int capacity;
};

Queue *queue_create();
void queue_enqueue(Queue *queue, int element);
int queue_dequeue(Queue *queue);

int main()
{
  int n = 0, i = 0, last_tail_index_holder = -1, first_tail_index_holder = 0;
  char c;
  Queue *queue = queue_create();
  while((c = getchar()) != EOF)
  {
    if(c >= '0' && c <= '9')
    {
        queue_enqueue(queue, c - '0');
    }
    else
    {
        if(c == ',')
        {
            while((c = getchar()) < '0' || c > '9'){}
            n = c - '1';
        }
    }
  }
  first_tail_index_holder = queue->tail;

  while(i <= first_tail_index_holder - 1)
  {
    if(i == n)
    {
        last_tail_index_holder = last_tail_index_holder + i;
        queue_dequeue(queue);
    }
    else
    {
        queue_enqueue(queue, queue_dequeue(queue));
    }
    i = i + 1;
  }
  i = 0;
  while(i < first_tail_index_holder - 1)
  {
    printf("%d", queue_dequeue(queue));
    i = i + 1;
    if(i != first_tail_index_holder - 1)
    {
        printf(" ");
    }
  }
}

Queue *queue_create()
{
  Queue *queue = (Queue *)malloc(sizeof(Queue));
  queue->items = (int *)malloc(SIZE * sizeof(int));
  queue->capacity = SIZE;
  queue->head = queue->tail = 0;

  return queue;
}

void queue_enqueue(Queue *queue, int element)
{
  if(queue->tail == queue->capacity)
  {
    queue->items = (int *)realloc(queue->items, queue->capacity * 2 * sizeof(int));
    queue->capacity *= 2;
  }
  (queue->items)[queue->tail] = element;
  queue->tail++;
}

int queue_dequeue(Queue *queue)
{
  if(queue->head < queue->tail)
  {
    return (queue->items)[queue->head++];
  }
  else
  {
    return -1;
  }
  return 0;
}

Това е кодът на програмата с горещият картоф.

1. Дефинираме променливите и създаваме опашката.

2. От 25-39 ред слагаме числата в опашката.

3. От 42-54 ред вадим елемента най-отпред, слагаме го най-отзад на опашката и продължаваме да го повтаряме, докато не стигнем броя подавания на картофа, махаме елемента, до който сме стигнали и после продължаваме с разместването, докато елементите не се наредят в началният ред.
Например: Числата ни са 1,2,3,4,5 (тоест имаме 5 играча), задали сме 33 паса. Слагаме 1-цата най-отзад и се получава 2,3,4,5,1. После 2-ката и се получава 3,4,5,1,2. И така, докато не стигнем 33-тият пас. В случая при него ще имаме редица 3,4,5,1,2 , тоест изгаря играч номер 3. Премахваме 3тият елемент и продължаваме да повтаряме, докато не наредим редицата - 1,2,4,5.

4. От 56-64 ред принтираме елементите като ги вадим директно от опашката.

5. От 67-75 ред заделяме паметта, която ще ни е нужна.

6. От 77-85 ред enqueue-ваме елементите.

7. От 88-99 ред dequeue-ваме елементите. (Функцията е int, защото трябва да върне нещо. В случая -1, ако има грешка или 0, ако няма. Това ни трябва, за да знаем, че няма повече елементи и като сложим dequeue да ни даде грешка, ако няма повече елементи в опашката.)

Надявам се да съм бил полезен поне малко и благодаря на тези, които ще направят +1 показвания ;D