Chapter 07. 큐(Queue)

3.1 기본코드 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    MAX_COUNT = 6
};

typedef struct queue {
    int nArray[MAX_COUNT];
    size_t uCount;
    size_t uFront;
    size_t uBack;
} queue_t;

void enqueue(queue_t* _pQueue, int _nData);
int is_empty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
void print(queue_t* _pQueue);

int main(void)
{
    size_t i;
    queue_t q = { 0, };

    for (i = 0; i < 5; ++i) {
        enqueue(&q, (int)i * 2);
    }
    print(&q);

    printf("dequeue: ");
    for (i = 0; i <= 2; ++i) {
        printf("%d ", dequeue(&q));
    }
    printf("\n");
    print(&q);

    for (i = 0; i <= 2; ++i) {
        enqueue(&q, (int)i * 3);
    }
    print(&q);

    return 0;
}

void enqueue(queue_t* _pQueue, int _nData)
{
    assert(_pQueue->uCount < MAX_COUNT);

    _pQueue->nArray[_pQueue->uBack] = _nData;
    _pQueue->uBack = (_pQueue->uBack + 1) % MAX_COUNT;
    ++_pQueue->uCount;
}

int is_empty(queue_t* _pQueue)
{
    if (0 == _pQueue->uCount)
    {
        return TRUE;
    }
    return FALSE;
}

int dequeue(queue_t* _pQueue)
{
    int ret;

    assert(FALSE == is_empty(_pQueue));

    ret = _pQueue->nArray[_pQueue->uFront];
    _pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
    --_pQueue->uCount;

    return ret;
}

void print(queue_t* _pQueue)
{
    size_t i;

    assert(FALSE == is_empty(_pQueue));

    i = _pQueue->uFront;
    while(_pQueue->uBack != i)
    {
        printf("[%zu]: %d\n", i, _pQueue->nArray[i]);
        i = (i + 1) % MAX_COUNT;
    }
    printf("\n");
}

 

4.2 조세퍼스 수열

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    MAX_COUNT = 5001
};

typedef struct queue {
    int nArray[MAX_COUNT];
    size_t uCount;
    size_t uFront;
    size_t uBack;
} queue_t;

void enqueue(queue_t* _pQueue, int _nData);
int is_empty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
void print(queue_t* _pQueue);

int main(void)
{
    size_t i, j, N, M;
    queue_t q = { 0, };

    scanf("%zu %zu", &N, &M);

    for (i = 1; i <= N; ++i) 
    {
        enqueue(&q, (int)i);
    }
    print(&q);

    printf("dequeue: ");
    for (i = 0; i < N; ++i) 
    {
        for (j = 0; j < M - 1; ++j)
        {
            enqueue(&q, dequeue(&q));
        }
        printf("%d ", dequeue(&q));
    }

    return 0;
}

void enqueue(queue_t* _pQueue, int _nData)
{
    assert(_pQueue->uCount < MAX_COUNT);

    _pQueue->nArray[_pQueue->uBack] = _nData;
    _pQueue->uBack = (_pQueue->uBack + 1) % MAX_COUNT;
    ++_pQueue->uCount;
}

int is_empty(queue_t* _pQueue)
{
    if (0 == _pQueue->uCount)
    {
        return TRUE;
    }
    return FALSE;
}

int dequeue(queue_t* _pQueue)
{
    int ret;

    assert(FALSE == is_empty(_pQueue));

    ret = _pQueue->nArray[_pQueue->uFront];
    _pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
    --_pQueue->uCount;

    return ret;
}

void print(queue_t* _pQueue)
{
    size_t i;

    assert(FALSE == is_empty(_pQueue));

    i = _pQueue->uFront;
    while(_pQueue->uBack != i)
    {
        printf("[%zu]: %d\n", i, _pQueue->nArray[i]);
        i = (i + 1) % MAX_COUNT;
    }
    printf("\n");
}