7장 큐

https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9/dashboard

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

◆  큐
  ●  큐의 개념
  ●  큐의 ADT
  ●  큐의 사용 예시

---

◆  큐의 개념

    ● FIFO(First In First Out), 가장 먼저 들어간 원소가 가장 먼저 나오는 자료 구조
    ● LILO(Last In Last Out)과 동일하다

---

◆  스택의 ADT 

int front  // 큐에서 가장 마지막에 팝한 위치를 기록합니다.
                  => 가장 먼저 푸시된 원소의 위치
이렇게 알고 있는게 더 편할 것.

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/queue.cpp

codingtest_cpp/STL/queue.cpp at main · dremdeveloper/codingtest_cpp

---

std::queue는 C++ STL에 포함된 컨테이너 어댑터입니다.
- FIFL(First-In-First-Out) 원칙에 따라 동작하는 데이터 구조입니다.
좋은 사용 시기:
- 데이터를 순서대로 처리해야 할 때, 예를 들면, 너비 우선 탐색(BFS) 알고리즘, 대기열 구현 등.
성능 이슈:
- STL queue는 일반적으로 빠른 연산을 제공합니다. 하지만, 중간 요소에 직접 접귾할 수 없습니다.
중간 요소를 검색하거나 수정하려면 다른 자료구조를 사용하는 것이 좋습니다.

#include <iostream>
#include <queue>
using namespace std;

void queue_func();

int main()
{
	queue_func();
	return 0;
}

void queue_func()
{
	queue<int> q;

	// push : 큐의 끝에 요소 추가, O(1)
	q.push(1);
	q.push(2);
	q.push(3);

	// front : 큐의 첫 번째 요소에 접근, O(1)
	cout << "Front element : " << q.front() << endl; // 출력 : Front element : 1

	// pop : 큐의 첫 번째 요소에 접근, O(1)
	q.pop();
	cout << "Front element after pop : " << q.front() << endl; // 출력 : Front element after pop : 2

	// empty : 큐가 비었는지 확인, O(1)
	if (!q.empty()) {
		cout << "Queue is not empty" << endl; // 출력 : Queue is not empty
	}

	// size : 큐의 크기 확인, O(1)
	cout << "Queue size : " << q.size() << endl; // 출력 : Queue size : 2

	// 성능 저하 예제:
	// queue는 중간 요소에 직접 접근할 수 없으므로, 중간 요소를 검색하거나 수정하는 연산이 필요한 경우
	// queue 보다는 다른 자료구조를 사용하는 것이 좋습니다.
}

---

◆  큐의 사용 예시(줄서기)

큐를 이용해서 줄 서는걸 시뮬레이션을 돌린다.
front는 가장 먼저 들어온 원소의 위치이고
rear은 가장 최근에 들어온 원소의 위치이다.

---

◆  큐의 사용 예시(요세푸스 문제)

 1. N명의 사람들이 원형으로 둘러앉고, 각 사람들 번호를 1~N로 매김
 2. 시작 위치부터 K번째 사람 제거
 3. 제거한 위치로부터 다시 K번째 사람 제거
 4. ③과정을 한 명이 남을 때 까지 반복

◆  큐의 사용 예시(요세푸스 문제, N=5 , K=2)

◆  큐의 사용 예시(요세푸스 문제를 배열로 푼다면?)

◆  큐의 사용 예시(요세푸스 문제를 로 푼다면?)

k번째 원소 제거
k-1번째 까지는 팝 &푸시로 뒤로 뺌  k번째 제거

N=5, K=2
팝 &푸시 하면 뒤로 보내고 제거할건 제거하고
원형인것 처럼 구현한다.
이런식으로 반복한다.

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/queue_josephuse.cpp

codingtest_cpp/Algorithm_with_DataStructure/queue_josephuse.cpp at main · dremdeveloper/codingtest_cpp

#include <iostream>
#include <queue>
using namespace std;

void queue_josephus_func();
int main()
{
	queue_josephus_func();
	return 0;
}
int josephus(int N, int K) 
{
	// Step 1 : 큐 초기화 및 요소 삽입
	// 시간 복잡도 : O(N)
	// 큐를 초기화하고 1부터 N까지 요소를 삽입합니다.
	// 예시 : N =5 일 경우, 큐는 [1,2,3,4,5]로 초기화됩니다.

	queue<int> q;
	for (int i = 1; i <= N; ++i) {
		q.push(i);
	}

	// Step 2 : 제거 과정 시뮬레이션
	// 시간 복잡도 : O(N*K)
	// 큐의 크기가 1이 될 때까지 반복합니다.
	while (q.size() > 1) {
		// 첫번쨰 K-1개의 요소를 큐의 뒤로 이동시킵니다.
		for (int i = 0; i < K - 1; ++i) {
			q.push(q.front());
			q.pop();
		}
		// K번째 요소를 제거합니다.
		q.pop();
	}

	// 마지막으로 남은 요소가 생존자입니다.
	return q.front();
}

void queue_josephus_func()
{
	int N = 5; // 예시: 5명의 사람이 있을때
	int K = 2; // 예시: 매 2번째 사람을 제거할 때

	// 생존자를 출력합니다.
	cout << "The survivor is: " << josephus(N, K) << endl;
}

/*
동작 과정 예시:
1. 큐 초기화: [1, 2, 3, 4, 5]
2. 첫 번째 반복:
   - [1, 2, 3, 4, 5] -> [2, 3, 4, 5, 1] -> [3, 4, 5, 1]
3. 두 번째 반복:
   - [3, 4, 5, 1] -> [4, 5, 1, 3] -> [5, 1, 3]
4. 세 번째 반복:
   - [5, 1, 3] -> [1, 3, 5] -> [3, 5]
5. 네 번째 반복:
   - [3, 5] -> [5, 3] -> [3]
6. 생존자: 3
*/

---

◆  정리

- 스택 : LIFO, 함수 호출 관리, 페이지 탐색, 괄호 짝 맞추기
- 큐 : FIFO, 줄서기, 요세푸스
- 스택인 경우 "가장 최근 원소"를 봐야하는 경우에 사용
   * 추후 DFS, 백트래킹에서 사용
- 큐는 들어온 순서대로 나갈 때 사용
   * 추후 BFS에서 사용

10월 셋쨋주까지 문제 15~ 17번 코드 구현 예정