[자료구조] - 큐(queue)의 구조, 선형큐 구현하기

1. 큐(queue)란?

큐(queue)라는 단어의 사전적인 뜻을 찾아보면, " (무엇을 기다리는 사람·자동차 등의) 줄" 이다. 계산을 기다리는 사람들의 줄을 생각하면 이해가 쉽다. 

새로운 사람이 줄을 설 때에는 맨 뒤에 서고, 맨 앞 사람부터 줄에서 나가게 된다.

 

선입선출 (FIFO : First - In - First - Out)

스택과 비교되는 큐의 중요한 특징이다. 스택에서는 가장 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO)의 특징을 가졌다면, 큐는 이와 반대로 먼저 들어온 데이터가 먼저 나가는 구조이다.  즉 큐에서 입력은 뒤쪽에서만 일어나며, 출력은 앞쪽에서만 일어난다. 큐에서 삽입이 일어나는 뒤쪽을 rear(후단), 삭제가 일어나는 앞쪽을 front(전단) 이라고 한다. 

큐의 구조

---

2.  선형큐 구현하기

큐도 스택과 같이 1차원 배열로 구현이 가능하다. (물론 다른 방법도 존재하나 1차원 배열을 이용하는게 가장 간단하다.) 큐의 첫번째 요소를 가리키는 변수 front 와, 큐의 마지막 요소를 가리키는 변수 rear 을 설정한다. 스택이 비어있는 초기 상태에는 front와 rear이 모두 -1의 값을 가진다. 스택에 요소를 삽입할 때마다 rear은 1씩 커지고, 스택에서 삭제가 일어날 때마다 front도 1씩 커진다. 

(큐 구현에 이용된 함수는 스택 구현시 선언한 함수와 매우 유사하므로 함수들이 이해가 잘 안간다면 "스택의 구조와 구현" 글을 참고하길 바란다. https://developer-cat.tistory.com/4)

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 1000
typedef int element;

typedef struct {
	int front;
	int rear;
	element data[MAX];
} QueueType;


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

//큐가 비어있는지 검사
int is_Empty(QueueType* q) {
	if (q->front == q->rear) return 1;
	else return 0;
}

//큐가 꽉 차있는지 검사
int is_full(QueueType* q) {
	if (q->rear == MAX - 1) return 1;
	else return 0;
}

//큐의 맨 끝에 삽입
void enqueue(QueueType* q, int item) {
	if (is_full(q) == 1) {
		cout << "Overflow";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	q->data[++(q->rear)] = item;
}

//큐의 맨 앞의 요소 제거 후 반환
int dequeue(QueueType* q) {
	if (is_Empty(q)) {
		cout << "Empty";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	else {
		int item = q->data[q->front+1];	//맨 앞의 요소는 front+1 의 인덱스에 있다.
		q->front++;
		return item;
	}
}

//큐의 맨 앞 요소 출력
int peek(QueueType *q) {
	if (is_Empty(q) == 1) {
		cout << "Empty!";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	else
		return q->data[q->front+1];
}

//main함수
int main() {
	QueueType q;

	init_queue(&q);
	enqueue(&q, 1);
	enqueue(&q, 2);
	enqueue(&q, 3);
	enqueue(&q, 4);
	
	cout << dequeue(&q) << "\n";
	cout << peek(&q) << "\n";
	cout << dequeue(&q) << "\n";
}

 

 

3. 배열로 구현한 선형큐의 문제점

1차원 배열로 구현한 선형큐에는 문제점이 있다. 큐에 요소를 삽입하든, 삭제를 하든 front와 rear의 값이 계속 증가만 하게 된다. 그러므로 삽입 삭제를 많이 하게 되면 언젠가는 front와 rear의 값이 배열의 끝 값에 도달하게 될 것이다. 그렇게 되면 배열의 앞부분이 비어 있음에도 불구하고 사용할 수 없게 된다. 따라서 앞부분에 빈 공간이 생기면 모든 요소들을 다시 앞쪽으로 이동시켜야 공간 낭비를 방지할 수 있다. 하지만 이런식으로 매번 데이터들을 이동시키는 것은 상당한 시간이 걸릴 뿐만 아니라 프로그래밍적인 부분에서 코드가 매우 복잡해지기 때문에 비효율적이다.