[자료구조] Queue(큐) 구현 c++ [컴공과고씨]

들어가기 앞서 Linked Queue 구현을 위한 더 쉬운 이해를 위해 스택에 관한 앞 글인 https://hagisilecoding.tistory.com/141 를 보고 오시는게 좋습니다.

 

큐는 스택과 반대입니다. 스택은 들어간 것이 먼저 나중에 나오지만 큐는 먼저 들어간 것이 먼저 빠져 나온다고 생각하면 됩니다. 

 

그렇기에 구현 할 때도 조금 더 생각을 해주어야 합니다.

스택은 top 변수로 늘려주고 빼주고 하면 되지만 큐 같은 경우는 변수를 두 개 두고 앞쪽 dequeue할 변수 한 개 enqueue할 변수 한 개 총 두개를 컨트롤 해주어야합니다.

 

문제는 이렇게 하면 Dequeue를 했을 때 낭비되는 칸이 생기게 됩니다. 

이런식으로 그래서 %연산을 이용해서 circular(순환) 하도록 만들어 주는 것입니다.

front 변수가 이제 dequeue를 담당하고 rear가 enqueue를 담당하는 변수라 생각하고 똑같이 +1을 해주는데

이때 %를 사용하여 circular하게 해준다.

이거 처럼 배열이 다 차고 만약 dequeue를 했다면 앞쪽에 빈칸이 있기 때문에 앞 공간을 다시 이용해준다.

여기서 우리는 주의할점이 큐가 다 찬것과 비어있다는 것을 구분하기 위해서 한 공간을 비어둔다. 

처음 시작 점이 두 변수 둘다 -1이기 때문에 큐가 비어있다는 것은 rear와 front가 같을 때 이다.

그럼 큐가 다 찼다는 것은? front 하고 rear+1하고 같을 때로 정의 한다. 위처럼 말이다.

위 그림 상 front가 가르키는 곳이 비어있지만 저기를 채워버리게 되면 큐가 비어있다는 정의와 가득차있다는 것과 같게 되어 구별이 어려워진다. 그래서 rear+1 이 front와 같은 경우를 큐가 다 찼다고 정의를 해준다. 

그럼 하나의 공간만 낭비하고 나머지 공간들은 순환하며 계속 사용할 수 있게 된다.

 

Linked Queue

위쪽은 dynamic array를 활용한 queue 구현이였다면 이제는 Linked Queue를 구현해보자.

스택과 마찬가지로 NodeType을 사용합니다.

NodeType의 구성은 stack에서의 NodeType 처럼 info와 next가 있습니다.

 

class에서 변수를 보면 front 와 rear가 있는데 둘다 노드타입을 가르키는 포인터로 선언되어있습니다.

처음 생성자에는 front와 rear를 둘다 NULL로 초기화 합니다.

즉 큐가 비어있다는 것은 NULL입니다.

스택을 이해하셨다면 Linked queue는 더욱 쉽습니다.

Enqueue

Enqueue할 때는 새로운 노드타입을 생성 후에 info에 정보 넣고 next에는 NULL을 넣어줍니다.

그리고 front가 NULL이라면 처음 값을 생성하는 것이기 때문에 front에 새로운 노드를 연결한 후 

rear에 연결해주고 NULL이 아니라면 rear->next 즉, 마지막 노드의 next가 새로운 노드를 가르키게 한 후 rear에 새로운 노드를 넣어주면 됩니다.

또한 Linked를 이용한 방법은 순환이 아닌 뒤로 쭉 노드를 연결하는 방식입니다. 그래서 dequeue을 할 때도 맨 앞의 노드를 그냥 삭제하면 되어서 순환 방식을 쓰지 않아도 됩니다. 즉, 가득 찬 상태는 그냥 새로운 노드를 만들때 오류가 나면 try catch 문으로 처리를 해줍니다.

Dequeue

Dequeue 같은 경우 임시 포인터를 만들어 front가 가르키고 있는 노드를 저장해 줍니다. 그 후  front 포인터를 front->next가 가르키고 있는 노드에 연결 해줍니다. 만약 마지막 노드라면 front->next에는 NULL이 저장되어있기 때문에 큐가 비었다는 것은 front가 NULL이 될때라는 것을 알 수 있습니다. 그렇기 때문에 이때는 rear도 NULL로 만들어줍니다.

그 후 임시 포인터를 delete 해주면됩니다.

 

MakeEmpty

MakeEmpty 함수는 큐를 비우는 것으로 이것은 주의를 해주어야합니다. 마찬가지로 소멸자에 MakeEmpty 함수를 주어 메모리가 누수되는 것을 방지해야합니다. 이거 같은경우 큐가 빌때까지 즉, front 포인터가 NULL이 될때까지 while문을 걸어주고 그 후 는 dequeue하는 거 처럼 임시 포인터를 삭제하는 식으로 진행 해주면 됩니다. 

 

시간복잡도

시간 복잡도

 

 

main.cpp

제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다.

버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 큐를 통해 구현해 놓았다.

예시로 N = 7 일 때는 카드가 위에서부터 1,2,3,4,5,6,7 이 되고 1 버리고 2를 맨 밑으로, 3 버리고 4를 맨 밑으로 ....

하면 1,3,5,7,4,2,6 이 답이다.

 

전체코드는 https://github.com/goragoraki/Data-Structure 여기에서 볼 수 있습니다.