선형 자료구조 정리 (큐)

큐(Queue) 란?

큐(Queue)의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가지며, 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다.

Queue는 C++ 표준 라이브러리(STL, Standard Template Library)에 정의 되어 있어 필요할 때마다 만들어 사용하지 않고 include하여 사용하시면 편리합니다.

 

[그림 1.] 큐(Queue) 구조

Enqueue
큐 맨 뒤에 데이터 추가

Dequeue
큐 맨 앞쪽에 데이터 삭제

큐(Queue)의 특징

1. 먼저 들어간 자료가 먼저 나오는 구조(FIFO, First In First Out) 구조

2. 큐는 한 쪽 끝은 프론트(front)로 정하여 삭제 연산만 수행함

3. 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함

4. 그래프의 넓이 우선 탐색(BFS)에서 사용

5. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴

큐(Queue) 사용법

Queue 선언

#include <queue>  // queue가 들어있는 헤더파일
queue<int> s;     //int형 큐 선언
queue<char>s;     //char형 큐 선언

 

Queue 값 추가

// int형 스택 선언
queue<int> q; 

// queue에 값 1 추가
q.push(1);    

// queue에 값 2 추가
q.push(2);    

// queue에 값 3 추가
q.push(3);   

큐에서 값을 추가하고 싶다면 push(value)라는 메서드를 활용하면 됩니다. 큐에 값을 계속해서 추가해 나간다면 아래 그림과 같은 형태로 데이터가 쌓이게 됩니다.

 

[그림 2] 큐 데이터가 쌓이는 순서

Queue 값 삭제

// int형 큐 선언
queue<int> q; 

// queue에 값 1 추가
q.push(1);     

// queue에 값 2 추가
q.push(2);  

// queue에 값 3 추가
q.push(3);

// queue에 값 제거
q.pop();

 

Queue의 기타 메서드

 // queue의 크기 출력
q.size();     

 // queue가 비어있는지 check (비어있다면 true)
q.empty();    

// queue의 가장 첫번째 원소 출력
q.front();  

 // queue의 가장 마지막 원소 출력
q.back();