서론
많은 사람들의 push_swap 구현을 많이 본 것은 아니지만, 주변에서 흔히 들은 내용으로는 보통 push_swap에서 stack을 구현할 때 Double Linked List를 이용하여 구현했다고 들었다.
Linked List를 이용하는 이유는 스택의 크기가 계속 동적으로 변하기 때문이다.
또한 push_swap에서 존재하는 stack은 일반적인 stack과 다르게 시작과 끝 두 부분에서 데이터의 삽입과 삭제가 일어나게 된다. 사실 deque (덱) 과 유사한 형태라고 볼 수 있다. 그러기 때문에 Linked List를 넘어서 Double Linked List를 이용하여 시작과 끝에 대한 주소 정보를 유지하여야 한다.
하지만 Double Linked List를 구현하고 삽입, 삭제 함수를 실수 없이 구현하고 그 상황에서 메모리 누수가 일어나지 않게 만드는 것이 간단하지만은 않은 일이다. 물론 직접 구현하고 고쳐가며 학습에는 큰 도움이 될 수 있다. 하지만 나는 좀 더 간단하고 메모리 누수 늪에서 벗어날 수 있도록 Circular Queue를 이용하여 구현해 보았다.
Circular Queue
우선 그림을 먼저 보자.
구조체를 하나 만들고 그 안에 배열과 front, rear 에 대한 정보를 저장한다.
circular queue의 장점은 배열로 구현할 수 있다는 것이다. 위 처럼 front 와 rear사이에 유효한 데이터를 저장하면서 queue의 형태를 띈다.
참고로 circular queue의 구현 방법은 여러가지이다. rear가 마지막을 가리키는 경우, 마지막 다음을 가리키는 경우 등 여러가지 방법이 있는데, 여기서는 위 사진과 같이 front는 단순히 첫 데이터 인덱스, rear는 마지막 인덱스를 나타내겠다.
여기서 의문 점이 들 수 있는 것은 데이터가 만약 8개보다 더 많이 들어오는 경우는 어떡할 것인지에 대한 것이다. circular queue의 단점은 최대로 들어갈 수 있는 데이터의 크기가 제한이 있다. 최대로 차면 더 이상 들어갈 수 없다. 하지만 우리가 해결하고자 하는 push_swap은 데이터의 개수가 유동적으로 변하지 않는다. 처음에 들어온 argv의 인자의 개수가 최대 개수가 된다. 그러면 그 크기로 a와 b를 생성하면 된다.
이제 본격적으로 한번 deque를 구현해보자.
deque에서 기본적으로 사용하는 method는 push_front, pop_front, push_back, pop_back이다.
맨 앞과 맨 뒤에서만 데이터의 삽입과 삭제가 일어난다.
여기서 중요한 것은 위 그림처럼 front가 0을 가리킬 때 push_front를 어떻게 하냐이다.
0의 그 전 인덱스는 7이 되어야 한다.
arr[idx -1] = 10;
C
복사
이러한 식으로 하면 0일 때 당연히 seg fault 발생
void push_front(data)
{
arr[ (idx + (전체크기) - 1) % (전체크기)] = 10;
}
C
복사
이러한 식으로 해야한다.
push_back의 경우는
arr[ (idx + 1) % (전체크기)] = 10;
C
복사
이러한 식으로 계속 인덱스가 원을 그리며 순환해야 한다.
물론 front와 rear의 update도 잊지 말고 해야 한다.
그리고 이렇게 구현하려면 전체크기에 대한 정보도 구조체에 갖고 있으면 좋다.
또한 유용한 것은 deque의 길이에 관한 것인데, 이 또한 front 와 rear의 수식으로 간단히 해결할 수 있지만 문제점이 하나 있다. 그것은 배열이 꽉 차있을 때와 비어있을 때를 구분할 수 없다.
위에서 말하지 못했지만 참고로 비어있는 경우는 rear과 front 하나 뒤에 위치해야한다.
마찬가지로 꽉 찼을 경우도 같다.
이를 해결하기 위해 길이에 대한 정보도 구조체에 넣어주고 잘 update 시켜주자.
이제 pop하는 경우를 생각해보자.
pop은 더 쉽다.
기존 데이터 반환하고 그냥 단순히 front, rear만 적절히 옮겨주면 된다.
기존 데이터 지울 필요없다. 쓰레기 값으로 배열에 남아있겠지만 어차피 사용안하고 나중에 덮어 씌워질 것이다.
이렇게 하면 구현 끝이다.
나중에 배열 메모리 해제 해주면 leak걱정은 하나도 안해도 된다.
나는 하지 않았지만 좀 더 안정적인 코드를 원한다면 push, pop 전에 배열의 크기를 확인 후 비어있거나 꽉 차면 예외처리하면 좋다. 나는 이를 통해 push_swap 에 존재하는 명령어를 구현 시 거기서 예외처리를 해주었기 때문에 문제는 발생하지 않았다. 위에서 구현한 deque를 이용해 명령어 구현은 쉽게 할 수 있을 것이다.
최종 코드
