선형 큐 : push 연산의 횟수만큼 크기를 할당하면 된다.

 Queue를 직접 구현해야 할 때에는 어떻게 해야 할까요? 사실, 선형 큐를 먼저 고려합니다. 큐는 먼저 넣은 친구가 먼저 빠지는 특성을 지닙니다. 예를 들자면, 은행 창구를 생각해 보세요. 먼저 번호표를 뽑은 손님이 먼저 처리됩니다. 그런가요? 그렇기 때문에, 포인터가 front하고 rear, 이렇게 2개가 있는데요. front는 제일 앞에 있는 것을, rear는 제일 뒤에, 넣을 위치를 가리킵니다.

 

 

---

 선형 큐를 구현할 때, 저는 is_full 처리를 하지 않아요. 그렇기 때문에 초기 크기를, 큐에 들어가는 원소의 갯수 + 10로 잡습니다. 예를 들어서, 가로 r개, 세로 c개의 맵이라면 BFS를 돌릴 때, rc만큼 들어가기 때문에 크기를 rc + 10 정도로 잡습니다.

 

 

 처음에 front와 rear의 값은 0으로 모두 같습니다. 이 때 비어 있는 상태라고 합니다. 비어 있는 상태에서 peek를 하거나, pop을 하면 invaild합니다. 따라서, 이 부분은 처리를 해 주어야 합니다. is_empty 메서드는 요래 작성하면 되겠네요.

 

 

 일단 1을 추가해 봅시다. 그러면, queue[rear]에 1을 넣었습니다. 그 다음에 어떻게 해야 하나요? 1의 다음 위치에 원소를 추가해야 합니다. 그렇기 때문에, rear를 하나 증가시킵니다.

 

 

 그러면 이렇게 되겠군요. 다음에 2를 추가할 거에요. 그러면 어떻게 해야 하나요? rear가 가리키는 자리에 2를 넣습니다.

 

 

 다음에 어떻게 해야 하나요? rear를 1칸 우측으로 이동시켜야 합니다. 만약에 그 다음에 3이 추가되는 경우에, 2의 뒤에 추가되어야 하기 때문입니다.

 

 

 push 메서드 끝났습니다. 어떻게 한다고 했나요? 뒤의 원소를 가리키는 포인터에 원소를 추가한 다음에, 포인터 값을, 그러니까 rear의 값을 하나 증가시키면 된다고 하였습니다.

 

 

---

 그러면 삭제는 어떻게 해야 할까요? 먼저 온 친구가 빠집니다. 그러면 1과 2 중에서, 먼저 넣어진 원소는 어떤 것인가요? 1입니다. 그러면, 1을 가리키는 포인터는 front인가요? rear 인가요?

 

 

 front 입니다. 따라서, 그냥 pop() 명령어만 들어온 경우에는, front만 하나 증가시켜 주면 됩니다.

 

 

 그런데 peek()이나 맨 앞에 있는 원소를 출력해야 하는 경우가 있습니다. 이 경우는 어떻게 해야 할까요? 1이 빠지면, 맨 앞에는 2가 있습니다. 2는 누가 가리키고 있나요? front 포인터가 가리키고 있어요. 따라서, queue[front]의 값을 출력하면 될 거에요.

 

 그런데, peek이나, pop이나 주의할 점이 하나 있어요.

 

 

 2를 삭제해 봅시다. 그러면 큐가 empty, 그러니까 비어 있는 상태가 됩니다. 이 상태에서 앞에 있는 원소를 빼는 거나, pop을 하는 연산이 vaild한 연산일까요? 아닙니다. 따라서, is_empty() 메서드를 통해서 해당 데이터 구조가 비어있는지 확인한 후에 수행을 해야 합니다.

 

 

---

 이제 간단한 예제 코드를 보도록 하겠습니다.

 

 

 먼저 int형을 담을 queue를 생성하였습니다. 그리고 0부터 9까지 수를 push한 후에, 맨 앞에 있는 원소를 출력한 후에 pop을 하는 루틴을 총 10회 반복하였습니다. 그러면 0부터 9까지가 차례대로 출력이 될 거에요. Queue의 생성자에 int형 변수를 하나 넣어주었는데요. 이는 큐에 들어갈 원소의 총 갯수, 즉 push 연산이 일어나는 총 횟수보다 크다고 보시면 됩니다.

 

 간단하게 구현하시려면, 큐의 push 연산이 일어나는 횟수보다 10이나 20정도 크게 할당하시면 됩니다.

 

 

 클래스 안에, front와 rear, 그리고 실제 큐 안에 있는 데이터를 저장할 배열인 rear를 선언하였습니다. 생성자에서 적당히 초기화를 잘 해주고 있어요.

 

 

 front와 rear의 값이 같으면 큐가 빈 겁니다. 따라서 이 때 is_empty()의 리턴 값이 참이 됩니다. 이것은 peek와 pop 함수 안에서 절찬리에 쓰이는데요. 큐가 비었을 때, 이 둘이 수행되면 vaild 하지 않기 때문입니다. 이 둘은 제가 다른 기능을 하게 했는데요. peek은 맨 앞에 있는 원소를 빼는 겁니다. 맨 앞의 원소는 front가 가리키고 있기 때문에, real[front]를 리턴하였습니다.

 

 

 그리고 pop은 단순히 front 값만 변경하면 됩니다. 따라서 이 값만 증가시켜주었습니다. rear는, 내가 뒤에 추가할 때, 데이터를 넣을 위치인데요. 처음에 real[rear]에 x를 넣어야 할 겁니다. 그리고, push 연산이 또 들어오는 경우에, 그 뒤에다가 또 원소를 추가해야 하기 때문에, rear의 값을 하나 증가시켜 주었습니다.