2. 큐의 구현

선형 큐 (linear queue)

선형 큐

: 1차원 배열을 써서 큐를 구현하는 방법

1. 1차원 배열을 정의하고 삽입, 삭제를 위한 변수인 front와 rear를 만든다
2. front는 큐의 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킨다
3. front와 rear의 초기값은 -1이다. 데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장된다.
4. 삭제할 때도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다

---

선형큐의 구현 ft. C언어

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

#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct { 				// 큐 타입
	int  front;         // 큐의 맨 앞 원소 위치
	int rear;           // 큐의 맨 뒤 원소 위치
	element  data[MAX_QUEUE_SIZE];  // 원소를 저장하는 배열
} QueueType;

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 큐 초기화 함수
void init_queue(QueueType* q)
{
	q->rear = -1;   // rear를 -1로 초기화
	q->front = -1;  // front를 -1로 초기화
}

// 큐의 원소 출력 함수
void queue_print(QueueType* q)
{
	for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
		if (i <= q->front || i > q->rear)  // 큐가 비어있거나 원소가 없는 부분은 |로 출력
			printf("   | ");
		else
			printf("%d | ", q->data[i]);  // 큐에 저장된 원소 출력
	}
	printf("\n");
}

// 큐가 포화상태인지 검사하는 함수
int is_full(QueueType* q)
{
	if (q->rear == MAX_QUEUE_SIZE - 1)  // rear가 배열의 마지막 원소인 경우 포화상태
		return 1;
	else
		return 0;
}

// 큐가 공백상태인지 검사하는 함수
int is_empty(QueueType* q)
{
	if (q->front == q->rear)  // front와 rear가 같은 경우 공백상태
		return 1;
	else
		return 0;
}

// 큐에 원소를 삽입하는 함수
void enqueue(QueueType* q, int item)
{
	if (is_full(q)) {   // 큐가 포화상태인 경우 오류 메시지 출력
		error("큐가 포화상태입니다.");
		return;
	}
	q->data[++(q->rear)] = item;  // rear를 1 증가시키고 원소를 삽입
}

// 큐에서 원소를 삭제하고 반환하는 함수
int dequeue(QueueType* q)
{
	if (is_empty(q)) {  // 큐가 공백상태인 경우 오류 메시지 출력
		error("큐가 공백상태입니다.");
		return -1;
	}
	int item = q->data[++(q->front)];  // front를 1 증가시키고 삭제할 원소를 저장
	return item;  // 삭제한 원소 반환
}

// main 함수
int main(void)
{
	int item = 0;
	QueueType q;

	init_queue(&q);  // 큐 초기화

	enqueue(&q, 10); queue_print(&q);
	enqueue(&q, 20); queue_print(&q);
	enqueue(&q, 30); queue_print(&q);

	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	return 0;

---

선형 큐의 응용 : 작업 스케줄링

• 큐는 운영 체제에서도 사용된다.
• 운영체제는 많은 작업들을 동시에 실행해야 한다.
• 만약 CPU가 하나뿐이고 모든 작업들은 우선순위를 가지지 않는다고 가정하면 작업들은 운영 체제에 들어간 순서대로 처리될 것이다.
• 이럴 때는 큐를 사용하여서 작업들을 처리할 수 있다

---

원형 큐

• 선형큐는 이해하기는 쉽지만 문제점이 있다.
• front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지를 못한다는 점이다.
• 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 한다.

 

• 큐는 다음과 같은 상태에 있을 수 있고 오른쪽에 삽입을 위한 공간을 만들기 위해서는 모든 요소들을 왼쪽으로 이동시켜야 한다.
• 이런 식으로 요소들을 이동시키면 해결은 되지만 매번 이동시키려면 상당한 시간이 걸리고 또한 프로그램 코딩이 복잡하다.

 

• 이 문제는 배열을 선형이 아닌 원형으로 생각하면 쉽게 해결된다.
• 즉 front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다.
• 즉 배열이 원형으로 처음과 끝이 연결되어 있다고 생각하는 것이다.
• 여기서 실제 배열이 원형으로 변화되는 것은 아니다.
• 그냥 개념상으로 원형으로 배열의 인덱스를 변화시켜주는 것뿐이다.

 

• 원형큐에서는 front와 rear의 개념이 약간 변경된다.
• 먼저 초기값은 -1이 아닌 0이다
• front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다
• 처음에 front, rear는 모두 0이고 삽입 시에는 rear가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입된다.
• 또 삭제 시에도 front가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제한다.

 

• front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타낸다
• 포화 상태와 공백 상태를 구별하기 위해서 원형큐에서는 하나의 자리는 항상 비워둔다(자리를 비워두지 않으면 오류 상태)
• 공백 상태 : front==rear
• 포화 상태 : front가 rear보다 하나 앞에 있는 상태

*만약 요소들의 개수를 저장하고 있는 추가적인 변수 count 변수를 사용할 수 있다면 한자리를 비워두지 않아도 된다.

---

원형 큐의 삽입, 삭제 알고리즘

삽입이나 삭제를 하기 전에 front나 rear를 원형 회전시켜서 하나 증가시키고 증가된 위치에 데이터를 삽입 또는 삭제한다.

원형큐의 구현에 있어서 중요한 것은 front와 rear를 원형으로 회전시켜야 한다는 것이고 이는 나머지 연산자 %를 이용하여 쉽게 구현이 가능하다

front <- (front+1) % MAX_QUEUE_SIZE
rear <- (rear+1) % MAX_QUEUE_SIZE

 front와 rear 값은 (MAX_QUEUE_SIZE-1)에서 하나 증가되면 0으로 된다.

즉 MAX_QUEUE_SIZE를 5로 정의하면, front와 rear 값은 0, 1, 2, 3, 4, 0과 같이 변화된다.

---

원형큐의 구현 ft. C언어

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

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
    element data[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

void error(char* message) // 오류 메시지 출력 함수
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init_queue(QueueType* q) // 큐 초기화 함수
{
    q->front = q->rear = 0;
}

int is_empty(QueueType* q) // 큐 공백 상태 검출 함수
{
    return (q->front == q->rear);
}

int is_full(QueueType* q) // 큐 포화 상태 검출 함수
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void queue_print(QueueType* q) // 큐 출력 함수
{
    printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
    if (!is_empty(q)) {
        int i = q->front;
        do {
            i = (i + 1) % (MAX_QUEUE_SIZE);
            printf("%d | ", q->data[i]);
            if (i == q->rear)
                break;
        } while (i != q->front);
    }
    printf("\n");
}

void enqueue(QueueType* q, element item) // 큐 삽입 함수
{
    if (is_full(q))
        error("큐가 포화상태입니다");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

element dequeue(QueueType* q) // 큐 삭제 함수
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

element peek(QueueType* q) // 큐에서 가장 먼저 들어온 데이터 반환 함수
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

int main(void)
{
    QueueType queue;
    int element;

    init_queue(&queue); // 큐 초기화
    printf("--데이터 추가 단계--\n");
    while (!is_full(&queue)) // 큐가 포화 상태가 될 때까지 데이터 삽입
    {
        printf("정수를 입력하시오: ");
        scanf("%d", &element);
        enqueue(&queue, element);
        queue_print(&queue);
    }
    printf("큐는 포화상태입니다.\n\n");

    printf("--데이터 삭제 단계--\n");
    while (!is_empty(&queue)) // 큐가 공백 상태가 될 때까지 데이터 삭제
    {
        element = dequeue(&queue);
        printf("꺼내진 정수: %d \n", element);
        queue_print(&queue);
    }
    printf("큐는 공백상태입니다.\n");
    return 0;
}

---

원형큐의 구현 ft. C++

CircularQueue.h

#pragma once
#include <iostream>
#include <cstdio>
#include <cstdlib>

const int MAX_QUEUE_SIZE = 100;

inline void error(const char* message) {
	printf("%s\n", message);
	exit(1);
}

template <typename T>
class CircularQueue {
protected:
	int _front;
	int _rear;
	T data[MAX_QUEUE_SIZE];
public:
	CircularQueue() : _front(0), _rear(0) {}
	void enqueue(const T& value);
	T dequeue();
	T peek();
	void display();
	bool isEmpty() { return _front == _rear; }
	bool isFull() { return (_rear + 1) % MAX_QUEUE_SIZE == _front; }
};

template <typename T>
void CircularQueue<T>::enqueue(const T& value) {
	if (isFull()) error("큐가 가득참!\n");
	else {
		_rear = (_rear + 1) % MAX_QUEUE_SIZE;
		data[_rear] = value;
	}
}

template <typename T>
T CircularQueue<T>::dequeue() {
	if (isEmpty()) error("큐가 비어있음!\n");
	else {
		_front = (_front + 1) % MAX_QUEUE_SIZE;
		return data[_front];
	}
}

template <typename T>
T CircularQueue<T>::peek() {
	if (isEmpty()) error("큐가 비어있음!\n");
	else {
		return data[(_front + 1) % MAX_QUEUE_SIZE];
	}
}

template <typename T>
void CircularQueue<T>::display() {
	std::cout << "[queue]: ";
	int max = (_front < _rear) ? _rear : _rear + MAX_QUEUE_SIZE;
	for (int i = _front + 1; i < max; i++)
	{
		std::cout << data[i] << " ";
	}
	std::cout << std::endl;
}

 

main.cpp

#include "CircularQueue.h"
using namespace std;

int main()
{
	CircularQueue<double> q;
	for (double i = 0.5; i < 15; i++)
		q.enqueue(i);
	q.display();

	q.dequeue();
	q.dequeue();
	q.dequeue();
	q.dequeue();

	q.display();

	return 0;
}