[C++/STL] - queue

1. queue란

Queue는 C++ STL의 하나로, 자료구조의 대표적인 FIFO(First In First Out) 알고리즘을 구현하는 데 사용된다

2. 특징

• Queue는 C++ STL의 하나로, 자료구조의 대표적인 FIFO(First In First Out) 알고리즘을 구현하는 데 사용된다.
• Queue는 container adapter로, 기본 컨테이너의 일부 함수만 사용하여 특정 요구에 맞게 변환된 컨테이너이다.
• Queue는 push() 함수를 사용하여 값을 추가하고, front() 함수를 사용하여 첫 번째 요소에 액세스하며, pop() 함수를 사용하여 동일한 요소를 제거한다.
• Queue는 먼저 들어간 자료가 먼저 나오는 구조(FIFO)를 따른다.
• Queue는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하며, 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행한다.
• Queue의 내부 구현에는 deque나 list가 사용된다.
• Queue는 그래프의 넓이 우선 탐색(BFS)에서 사용된다

3. 장단점

장점 :

• Queue는 자료 구조의 대표적인 FIFO 알고리즘을 구현하는 데 사용되므로, 구현이 간단하다.
• Queue는 내부적으로 deque나 list를 사용하기 때문에, 크기가 동적으로 조절되는 컨테이너이다.
• Queue는 그래프의 넓이 우선 탐색(BFS)에서 사용된다.
• Queue는 특정 컨테이너를 기반으로 하기 때문에, 컨테이너의 특성을 그대로 상속받아 사용할 수 있다.

단점 :

• Queue는 먼저 들어간 자료가 먼저 나오는 구조(FIFO)를 따르기 때문에, 자료를 중간에 삽입하거나 삭제하는 것이 불가능하다.
• Queue는 push() 함수를 사용하여 값을 추가하고, front() 함수를 사용하여 첫 번째 요소에 액세스하며, pop() 함수를 사용하여 동일한 요소를 제거하기 때문에, 요소에 대한 랜덤 액세스가 불가능하다.
• Queue는 스택이나 벡터와 같은 다른 STL 컨테이너에 비해 속도가 느리다.

4. 시간복잡도

C++ STL queue는 원소의 임의 접근, 검색, 삽입 및 삭제를 지원하지 않는다. Queue는 먼저 들어간 자료가 먼저 나오는 구조(FIFO)를 따르기 때문에, 자료를 중간에 삽입하거나 삭제하는 것이 불가능하다

1. 접근 - O(1)
   front() 함수를 사용하여 첫 번째 요소에 액세스하는 데 O(1) 시간이 걸린다.
2. 검색 - 지원 안함
3. 삽입 및 삭제 - O(1)
   push(), pop() 삽입과 삭제는 O(1)이다.

5. 사용법

1) 초기화

//queue 헤더 파일을 포함시켜야 Queue를 사용할 수 있다.
//queue를 선언할 때, queue의 데이터 타입을 지정해야 한다. 예를 들어, int형 queue를 선언하려면 다음과 같이 작성한다.
queue<int> q;
//push() 함수를 사용하여 값을 추가하고, front() 함수를 사용하여 첫 번째 요소에 액세스하며, pop() 함수를 사용하여 동일한 요소를 제거한다.
//queue를 초기화할 때, 중괄호({})를 사용하는 방법은 지원되지 않는다.

2) 멤버 함수

• push(): Queue의 끝에 요소를 추가한다.
• pop(): Queue의 처음 요소를 제거한다.
• front(): Queue의 처음 요소를 반환한다.
• back(): Queue의 마지막 요소를 반환한다.
• size(): Queue에 저장된 요소의 수를 반환한다.
• empty(): Queue가 비어있는지 여부를 반환한다.