큐(queue)

: 줄을 서는 것

: FIFO(First In First Out) 형식의 자료구조

표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황

선형 큐와 원형 큐가 있다
선형 큐는 계속 데이터가 앞으로 밀려나는 문제가 생기는데(앞쪽은 채워지고 뒤쪽은 빠져나가므로), 이것을 해결하기 위한 것이 원형큐

여기서는 원형 큐에 대해 공부하고 구현해볼 것이다

---

큐의 연산 (원형 큐)

• int empty()
  : 비어있으면 1 반환, 그렇지 않으면 0 반환
  rear(맨 끝을 가리키는 포인터)랑 front(맨 처음을 가리키는 포인터)가 같을 때

• int full()
  : 다 차있으면 1 반환, 그렇지 않으면 0 반환
  rear에서 하나 증가한 값이 front와 같을 때
  rear + 1이 0이 되어야할수도 있으므로 qsize로 나눈 나머지가 front와 같을 때

• int peek()
  : 큐의 맨 위(보관된 값 중 가장 처음에 저장된) 값을 반환
  큐가 비어있을 경우에는 null을 반환

• void enqueue()
  : 큐가 꽉 차있지 않다면, rear를 하나 증가시키고 그 자리에 데이터를 삽입
  큐가 꽉 차있다면 메모리 확장할 예정

• int dequeue()
  : 큐가 비어있지 않다면, front를 하나 증가시켜서 맨 위 데이터를 하나 제거
  제거된 데이터를 반환

---

큐의 구현

+) 1주차 과제 조건
동적 메모리할당과 구조체를 이용해서 스택과 큐 구현하기
스택(큐)에 원소 추가, 삭제하는 기능이 있어야 함
스택(큐)에 할당된 메모리 이상으로 원소가 추가 될 때 메모리 확장도 구현해야함
메모리 할당 해제도 구현해야 함

2주차가 연결 리스트여서 배열로 구현해보겠다

원형 큐 메모리 확장 주의해야될 점

배열 크기 확장 후, 원소의 위치를 복사해서 조정해줘야됨

예를 들어서, 메모리 공간을 6에서 12로 확장했다면,
확장 후 원소는 차례대로 인덱스 0부터 복사해서 채워넣고
rear의 위치는 요소들의 맨 뒤에
front는 11에 위치하도록 만들어줘야된다

---

소스코드

#include <stdlib.h>

typedef struct queue
{
    int front;
    int rear;
    int *data;
    int max;
    int cnt;
}queue;

void initQueue(queue *q, int size);
int empty(queue *q);
int full(queue *q);
int peek(queue *q);
void qExpand(queue *q);
void enqueue(queue *q, int data);
int dequeue(queue *q);

void initQueue(queue *q, int size)
{
    q->data = (int *) malloc(size * sizeof(int));
    if (!q->data)
        return ;
    q->front = size - 1;
    q->rear = size - 1;
    q->max = size;
    q->cnt = 0;
}

int empty(queue *q)
{
    if (q->rear == q->front)
        return (1);
    return (0);
}

int full(queue *q)
{
    if ((q->rear + 1) % q->max == q->front)
        return (1);
    return (0);
}

int peek(queue *q)
{
    int first_data;

    first_data = (q->front + 1) % q->max;
    if (!empty(q))
        return (q->data[first_data]);
}

void qExpand(queue *q)
{
    int i;
    int count;
    int *buf;

    buf = (int *) malloc(q->max * sizeof(int));
    count = q->cnt;
    i = 0;
    while (i < count)
    {
        buf[i] = dequeue(q);
        i++;
    }
    q->max *= 2;
    q->data = (int *) realloc(q->data, q->max * sizeof(int));
    if (!q->data)
        return ;
    initQueue(q, q->max);
    i = 0;
    while (i < count)
    {
        enqueue(q, buf[i]);
        i++;
    }
    free(buf);
}

void enqueue(queue *q, int data)
{
    if (!full(q))
    {
        q->rear = (q->rear + 1) % q->max;
        q->data[q->rear] = data;
        q->cnt++;
    }
    else
    {
        qExpand(q);
        enqueue(q, data);
    }
}

int dequeue(queue *q)
{
    if (!empty(q))
    {
        q->front = (q->front + 1) % q->max;
        q->cnt--;
        return (q->data[q->front]);
    }
}

---

백준 18258 큐2

큐1은 잘 돌아가는데 큐2가 틀렸습니다 라고 뜸..

위는 큐1 (문제로 링크 걸어뒀음)

위는 큐2 (문제로 링크 걸어뒀음)

두 문제의 차이점은 명령의 수 N의 범위가 다르다는 것이다
근데 나는 scanf로 크기를 받아와서 int형태로 저장시킨 후 그걸 하나하나 돌려줬다
2,000,000는 int 범위를 넘어가지 않으니까 충분히 가능하다고 생각했는데..!?
원형큐니까 메모리가 충분하지 않을까 생각했는데..?!
왜 안될까
큐1부터 틀렸는데 여기는 예외 느슨하게 해주고 큐2에서 빡세게 잡은걸까..?
머리가 안돌아가니 스터디에서 물어봐야겠다

+) 스터디 이후 다시 고민해봄
알고보니 realloc을 해주고 이전에 값이 있는 위치에 그냥 덮어씌워버려서
front가 밀려버렸다
중간에 realloc후 initQueue로 초기화를 해주니 해결..!