큐

JngHoon_2·2022년 10월 12일

FIFO 선입선출 자료구조 큐

자료구조

목록 보기

6/10

큐(Queue)란?

스택이 나중에 들어온 데이터가 먼저 나가는 구조인데 반해서 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 자료구조이다.

이러한 특성을 선입선출(FIFO: First In First Out)이라고 한다.

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택에서 삽입과 삭제가 같은 쪽에서 일어 났지만 큐에서는 다른 쪽에서 일어난다는 것이다.

큐의 추상 자료형

큐에 저장하는 자료에도 특별한 제한이 없다. 큐의 연산들도 스택과 매우 유사하다.
큐의 추상 자료형을 정의 하면 다음과 같다.

객체	선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모임
연산	enqueue(e): 주어진 요소 e를 큐의 맨 뒤에 추가한다.
	dequeue(): 큐가 비어 있지 않으면 맨 낲의 요소를 삭제하고 반환한다.
	isEmpty(): 큐가 비어 있으면 true, 아니면 false를 반환한다.
	peek(): 큐가 비어 있지 않으면 맨 앞의 요소를 삭제하지 않고 반환한다.
	isFull(): 큐가 가득 차 있으면 true, 아니면 false를 반환한다.
	size(): 큐의 모든 요소들의 개수를 반환한다.
	display(): 큐의 모든 요소들을 출력한다.

스택에서는 top으로 불리는 변수 하나만을 이용하여 삽입과 삭제 연산의 위치를 알 수 있었지만, 큐에서는 삽입과 삭제가 후단과 전단에서 각각 독립적으로 이루어지므로 양쪽의 위치를 기억해야하고, 따라서 두개의 변수가 필요하다.

큐의 활용

일상생활에서 대부분의 일들이 줄서기와 같이 먼저 들어온 순서대로 처이되는 것처럼 컴퓨터에서도 큐는 매우 광범위 하게 사용되고 있다. 컴퓨터 장치들 사이에서 데이터를 주고 받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 버퍼(buffer)라고 한다.

큐의 구현

1. 선형 큐

배열을 선형으로 사용하여 큐를 구현하는 방식이다. 삽입을 하기 위해서는 요소들을 이동시켜야한다. 하지만 이 방법은 매우 번거롭고 비효율적인 방법이다. 삭제 연산의 시간복잡도는 O(1)인 반면, 삽입연산의 시간 복잡도는 O(n)이다. 따라서 문제점이 많아 이 방법은 잘 사용되지 않는다.

2. 원형 큐

배열을 선형이 아닌 원형으로 생각하면 위 선형 큐의 문제점이 해결된다.
front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값이 0이되도록 하는 것이다. 즉, 배열이 원형이로 처음과 끝이 연결되 있다고 생각하면 된다. 여기서 주의 해야할 것은 front와 rear의 개념이 약간 변경된다는 것이다.먼저 초기 값은 -1이 아닌 0이다.
front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다. 다음 그림은 원형 큐에 데이터가 삽입, 삭제될 때 front와 rear의 변화를 보여준다.

큐의 공백 강태와 포화 상태를 알아보자.
1. 공백 상태는 front와 rear의 값이 같은 상태
2. 포화 상태는 원형 큐에서 하나의 자리를 제외한 나머지가 전부 차있는 상태
→ 전부 차있으면 front와 rear의 값이 같으므로 포화 상태와 공백 상태가 구별되지 않는다.

원형 큐의 구현

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

inline void error( char* str ) {
	fprintf(stderr, "%s\n", str);
	exit(1);
};

#define MAX_QUEUE_SIZE	100

class CircularQueue
{
	int front;	// 첫 번째 요소의 앞의 위치				
	int rear;	// 마지막 요소의 위치				
	int data[MAX_QUEUE_SIZE];	// 요소의 배열
public:
	CircularQueue()	{ front = rear = 0; }
	~CircularQueue() { }
	bool isEmpty()	{ return front == rear; }
	bool isFull()	{ return (rear+1)%MAX_QUEUE_SIZE == front; }

	void enqueue( int val ) { // 큐에 삽입
		if( isFull() )
			error("  error: 큐가 포화상태입니다\n");
		else {
			rear = (rear+1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
	}
	int dequeue( ) {	// 첫 항목을 큐에서 삭제하고 반환
		if( isEmpty() )
			error("  Error: 큐가 공백상태입니다\n");
		else {
			front = (front+1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}
	int peek( ){		// 첫 번째 항목을 큐를 삭제하지 않고 반환
		if( isEmpty() )
			error("  Error: 큐가 공백상태입니다\n");
		else 
			return data[(front+1) % MAX_QUEUE_SIZE];
	}
	void display( ) {	// 큐의 모든 내용을 순서대로 출력
		printf( "큐 내용 : ");
		int maxi = (front < rear) ? rear : rear+MAX_QUEUE_SIZE;
		for( int i = front+1 ; i<=maxi ; i++ )
			printf( "[%2d] ", data[i%MAX_QUEUE_SIZE]);
		printf( "\n");
	}
};