큐 (Queue)

큐(Queue)란?

스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조이다.
큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다.

큐의 선입선출 구조

큐(Queue) 연산

• enqueue: 큐에 데이터를 넣는다.
• dequeue: 큐에서 데이터를 삭제한다.

큐(Queue) 구현

#define QUEUE_SIZE 100

int Queue[QUEUE_SIZE];
int front = -1, rear = -1;

void enqueue(int val) {
    if (rear >= QUEUE_SIZE - 1)
    	return; // overflow
    else
    	Queue[++Rear] = val;
}

int dequeue() {
    if (front == rear)
    	return 0; // empty
    else
    	return queue[++front];
}

원형 큐(Circular Queue)

선형 큐의 경우, front와 rear의 값이 배열의 끝으로 이동할 경우 큐의 앞 부분이 비어있어도 데이터를 삽입할 수 없는 문제점을 가지고 있다.

원형큐는 이 문제점을 해결하기 위해 배열의 끝을 배열의 처음과 연결한 형태이다.

원형 큐 구현

#define QUEUE_SIZE 100

int Queue[QUEUE_SIZE];
int size = 0, front = -1, rear = -1;

void enqueue(int val) {
    if (size >= QUEUE_SIZE)
    	return // overflow
    else {
    	size++;
        rear = (rear + 1) % QUEUE_SIZE;
        queue[rear] = val;
    }
}

int dequeue() {
    if (size == 0)
        return 0; // empty
    else {
        size--;
        front = (front + 1) % QUEUE_SIZE;
        return queue[front];
    }
}