많은 사람들의 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를 이용하여 구현해 보았다.
우선 그림을 먼저 보자.
구조체를 하나 만들고 그 안에 배열과 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를 어떻게 하냐이다.