[C++ 자료 구조와 알고리즘] #7 자료 구조 (7) - std::queue (C++ STL container)

안녕하세요. C++을 다루기 위한 기본 적인 자료 구조와 코딩 테스트 등에서 응용될 수 있는 알고리즘을 알아보는 시간을 가지겠습니다.

 

이번 게시물은 std::queue를 간단히 설명해 보려 합니다. 

 

1) 특징

std::queue는 C++ 표준 라이브러리 컨테이너(C++ STL container) 중 하나로, queue 자료 구조를 구현하는데 사용됩니다. Queue은 선입선출(FIFO, First-In-First-Out)의 원칙에 따라 동작하는 자료 구조로 가장 먼저 들어간 자료가 가장 먼저 나오는 특징을 가집니다.

 

이와같은 std::queue에 대한 attributes와 관련 메서드 사용 예시를 알아보겠습니다.

 

2) 코딩 테스트 활용 예시

• BFS(Breadth-First Search): BFS 알고리즘은 그래프에서 최단 경로를 찾을 때 자주 사용됩니다. 큐를 사용하면 현재 노드와 인접해 있는 노드들을 큐에 삽입하고, 삽입된 순서대로 노드를 탐색해 나갈 수 있습니다.
• 캐시(Cache): 캐시는 최근에 사용된 데이터에 빠르게 접근할 수 있는 메모리 공간입니다. 큐를 사용하여 캐시에 데이터를 추가하고, 캐시 용량이 초과되는 경우 가장 오래된 데이터를 먼저 제거할 수 있습니다.
• 대기열 관리: 여러 작업을 처리해야 하는 시스템에서 큐는 작업을 순차적으로 처리하는 데 활용될 수 있습니다.

3) 속성 (Attributes)

std::queue는 <queue> 헤더를 포함해서 사용할 수 있습니다.

 

우선 다음과 같은 std::queue의 주요 속성과 멤버 함수를 통해 해당 자료 구조를 활용하는 방법을 자세하게 알아보겠습니다.

 

• push(element)
  : 큐의 뒤에 요소를 추가합니다.
• pop()
  : 큐의 앞에 있는 요소를 제거합니다.
• front()
  : 큐의 앞에 있는 요소를 반환합니다. 제거하지 않고 조회만 할 때 사용됩니다.
• back()
  : 큐의 뒤에 있는 요소를 반환합니다. 제거하지 않고 조회만 할 때 사용됩니다.
• empty()
  : 큐가 비어 있는지 여부를 확인합니다. 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• size()
  : 큐에 저장된 요소의 개수를 반환합니다.

 

4) 속성 사용 예시

다음은 std::queue의 속성 사용 예시입니다.

 

• push(element)
  : 큐의 뒤에 요소를 추가합니다.

std::queue<int> queue;
queue.push(10);
queue.push(20);
queue.push(30);

• pop()
  : 큐의 앞에 있는 요소를 제거합니다.

std::queue<int> queue;
queue.push(10);
queue.push(20);
queue.push(30);
queue.pop();

• front()
  : 큐의 앞에 있는 요소를 반환합니다. 제거하지 않고 조회만 할 때 사용됩니다.

std::queue<int> queue;
queue.push(10);
queue.push(20);
queue.push(30);
int frontElement = queue.front();

• back()
  : 큐의 뒤에 있는 요소를 반환합니다. 제거하지 않고 조회만 할 때 사용됩니다.

std::queue<int> queue;
queue.push(10);
queue.push(20);
queue.push(30);
int backElement = queue.back();

• empty()
  : 큐가 비어 있는지 여부를 확인합니다. 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

std::queue<int> queue;
bool isEmpty = queue.empty();

• size()
  : 큐에 저장된 요소의 개수를 반환합니다.

std::queue<int> queue;
queue.push(10);
queue.push(20);
queue.push(30);
int queueSize = queue.size();