자료구조 - 큐 (Queue)

1. 큐란?

큐(Queue)는 데이터를 일시적으로 쌓아두기 위한 자료구조로, 먼저 들어온 데이터가 가장 먼저 나가는 First In First Out인 구조를 말한다. 위 Reference Code처럼 배열로 큐를 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. enqueue란 큐 맨 뒤에 데이터를 추가하는 것을 의미하며 dequeue란 큐 맨 앞쪽의 데이터를 삭제하는 것을 의미한다. 데이터가 삽입되는 곳을 front, 제거되는 곳을 back이라고 한다.

 

선언

queue<자료형> 큐 이름; 형태로 선언한다.

#include <queue>

queue<int> s1;

queue<float> s2;

queue<char> s3;

 

기본 메소드

1. push() : 큐 맨 뒤에 데이터 추가 = enequeue

2. pop() : 큐 맨 앞의 데이터 제거 = dequeue

3. front() : 큐 제일 앞에 있는 값을 반환

4. back() : 큐 제일 뒤에 있는 값을 반환

5. size() : 큐에 저장된 데이터 갯수를 반환

6. empty() : 큐가 비어있으면 true, 아닐 경우 false를 반환

큐명.메소드() 형태로 사용한다.

 

2. 시간 복잡도

1) 삽입 / 삭제

- 원소를 삽입 / 삭제하는 경우 : O(1)

 

3. 장단점

1) 장점

- 데이터의 삽입과 삭제가 빠르다. (맨 위/아래 원소 접근 O(1))

 

2) 단점

- 중간에 위치한 데이터로의 접근이 어렵다.

 

4. 응용

- 데이터를 입력된 순서대로 처리해야 할 때

- BFS (너비 우선 탐색) 구현할 때

 

[예시문제]

주어진 N(2<= N <=100)개의 수를 순서대로 Queue에 넣은 후 하나씩 꺼내 화면에 출력하시오.

 

[입력]

케이스 개수

데이터 크기

데이터

 

[Reference Code]

#include <stdio.h>

#define MAX_N 100

int front;
int rear;
int queue[MAX_N];

void queueInit(void) //큐 초기화
{
	front = 0; //front의 초기값은 0
	rear = 0; //rear의 초기값은 0
}

int queueIsEmpty(void) //큐가 비었나?
{
	return (front == rear); //front와 rear가 같을 때 큐가 비었으므로 ture 반환
}

int queueIsFull(void) //
{
	if ((rear + 1) % MAX_N == front)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int queueEnqueue(int value)
{
	if (queueIsFull())
	{
		printf("queue is full!");
		return 0;
	}
	queue[rear] = value;
	rear++;
	if (rear == MAX_N)
	{
		rear = 0;
	}

	return 1;
}

int queueDequeue(int *value)
{
	if (queueIsEmpty())
	{
		printf("queue is empty!");
		return 0;
	}
	*value = queue[front];
	front++;
	if (front == MAX_N)
	{
		front = 0;
	}
	return 1;
}

int main(int argc, char* argv[])
{
	int T;
	int N;

	scanf("%d", &T);

	for (int test_case = 1; test_case <= T; test_case++)
	{
		scanf("%d", &N);

		queueInit();
		for (int i = 0; i < N; i++)
		{
			int value;
			scanf("%d", &value);
			queueEnqueue(value);
			printf("setValue");
		}

		printf("#%d ", test_case);

		while (!queueIsEmpty())
		{
			int value;
			if (queueDequeue(&value) == 1)
			{
				printf("%d ", value);
			}
		}
		printf("\n");
	}
	return 0;
}

 

 

양 방향에서 삽입연산과 삭제연산이 모두 이루어지는 큐를 덱(Deque)라고 한다.