2022.04.11. push_swap 스택구현-2, 스택 명령어 만들기(push_to another_stack, swap, rotate, reverse rotate), 정렬부 구현

 

어제 pop_front함수로 a_stack에서 top에 존재하는 노드를 추출해서 이를 push_front로 b_stack의 top에 해당 노드를 넣는 메인문을 테스트해본 결과, a스택을 출력하자 추출된 top node만 나오고, b스택에는 추가한 노드가 top에 저장되지 않은 결과를 얻었다. 결과를 얻자마자 t_stack 구조체에 편의상 저장해둔 노드의 갯수(counts)와 top_index(스택이 비었을땐 -1, 비어있지 않을땐 node.index)를 출력해본 결과,해당 값들은 의도한 대로 동작했을 경우에 나올 정상값을 반환했다. 다시 한번 push, pop 함수들을 돌아봤지만 문제점을 발견하지 못했다. 그래서 main 문을 보니, stack들에 초기 값을 넣어주는 초기화 과정에서 스택의 출력을 위해 지정한 변수 curr1, curr2 값이 초기화 됬을 당시에 head를 가리키는 상태 그대로 후에 pop, push 함수를 이용해 변동사항을 만든후에 똑같은 변수 currq, curr2부터 출력을 시작해서 생긴 문제였다. 테스트 파일 만들때 출력을 위해 이용하는 i등의 변수 초기화 시점에 주의해야겠다.

stach_main.c의 curr1과 curr2값을 push, pop 함수 호출 후 다시 각각 stack의 head를 가리키게 해서 출력하니 의도한 결과를 잘 확인 할 수 있었다.

 이제 과제에서 요구한 pa, pb, sa,sb, ss, ra, rb, rr, rra, rrb, rrr명령어들을 구현할 차례이다. 각각의 명령어에 대한 함수에서 각 명령을 처리하고 단순하게 명령을 "출력"하는 형태로 만들 수도 있지만, char *를 반환 함으로써, 각 명령을 내릴때마다 "pa\n"와 같은 char string을 반환 하게 하고, 이를 잠시 char **형 버퍼에 저장해 두었다가, 합칠 수 있는 명령어 인경우 명령어를 내리는 횟수를 최소화 해볼까 한다.(ex sa, sb가 연달아 나온경우 ss만 출력)따라서 위 명령어들은 char * 자료형을 반환하게 만들 생각이다.

push_stack 명령어 함수

 확실히, push_front/back, pop_front/back 함수를 미리 만들어두고 명령어 함수들을 만드니 훨씬 간단하다. 게다가 pa, pb 각각 만들어야하나 했는데, 하나의 함수를 만들어 두고 대상을 a, b로 다르게 하면 되니, 훨씬 간단하다.

pa, pb를 수행할 do_pstack 함수 구현 완료/ 후에 return ("")은 return (NULL)로 수정하였음

pa명령어를 내려서 비어있던 a_stack에 b의 top을 옮긴 모습

rotate_stack 명령어 함수

ra, rb를 수행할 rstack 구현 완료

rb 명령을 내려, b의 top이 bottom으로 rotate 된 모습 확인

+ rotate 관련 명령은, ra, rb, rr로 총 3개 이지만, a스택과 b스택에 둘다 일어나게하는 모든 명령어(rr, ss, rrr)은 실제로 함수로 구현하지는 않고, 명령어 출력시에 "명령어 버퍼(char **)"내에 "ra\n" , "rb\n"등이 차례로(중간에 다른값 없이)있을때, "rr\n"만 출력하는 식으로 만들것이기 때문에 rr을 따로 구현하지 않았다.

 

swap_stack 명령어 함수(counts < 2인 경우 사용 불가)

임시로 저장하는 용도인 t_node *형을 하나만 선언해서 바꿀 수도 있으나, 이미 구현한 pop, push 함수를 이용해 간단 구현하기 위해 t_node *를 두개 선언했다.

sb 명령으로 b_stack 내 top 노드와 그 다음 노드가 변경된 모습

단, 현재 이 swap_stack 함수에서는, 파라미터로 들어오는 스택의 노드 갯수가 2개 미만(counts <2)인 경우를 따로 고려하지 않았으므로, 사용에 주의를 요한다. counts<2인 경우 굳이 swap 명령이 아니더라도 rotate명령으로도 같은 효과를 얻을수 있기때문에, swap 명령은 counts <2인 경우 사용하지 않을 작정으로 구현했다.

 

reverse_rotate_stack 명령어 함수

rotate_stack 명령어 함수랑 다를게 별로 없었다.

rrb 명령어로 bottom에 있던 노드가 top으로 rotate 된 모습

이제 값 입력값 파싱 및, 필요한 스택(실질적으론 덱) 구현, 스택관련 함수 구현이 끝났으니, 정렬부를 구현할 차례인데, 그 전에, 파싱한 입력 값들을 스택 a(head, tail이 존재하는 양방향 연결 리스트) 들어온 순서대로 저장해야한다.

 

스택a에 입력 순서대로 저장

원래는 들어온 입력 값의 오름 차순으로 0부터 indexing 하는 arr4i배열에 값을 넣으면서 스택a에 입력값을 저장하려고 했는데, 현재 new_node를 만드는 함수에서 arr4i에서 해당 content의 indexf를 찾아 넣는 부분이 포함되어있어서, 차라리 indexing 하는 부분을 따로 함수로 빼고, 이 함수의 호출이 마쳐진 이후(arr4i 배열이 오름차순으로 정렬이 끝난 후에 index 값을 저장하는것이 낫겠다고 판단되었다.)

push_back 함수를 호출해서 입력값 순서대로 저장은 했으나, arr4i 배열이 정렬되기 전의 Index가 저장되어 버린다.

올바르지 않은 index가 스택에 저장된 모습

현재까지 push_swap 프로그램의 main 문을 거의 하나의 함수로 쭉쭉 써내려가고 있었는데, 이제 작은 함수들로 한번 분리 하는게 좋을 것 같다. 더 이상 길어지면 가독성이 너무 떨어져서 작업하면서 헷갈릴것 같다.

작은 함수들로 자를 걸 고려해서 짜긴 했지만, line 수가 너무 많아지고 변수도 많아져서 가독성이 안 좋은 int main의 상태

 

 

 

 

 

---------------------------------------------정렬 구현부 시작-----------------------------------------------

이전 04.02 학습 log에 남겼던 정렬부 구상

이전에 했던 구상에서 다른점은, 표본을 뽑아 들어온 입력값의 평균값을 구할 필요가 없어졌다는 것이다. 입력값을 받아 들이면서, 각각의 입력값에 오름 차순 순으로 index를 매겼기 때문에, index를 매긴 값의 /2한 값으로 정확한 가운데 값을 알게 되었기 때문. 또 이 index 값을 기준으로 스택을 정렬 할 것이다.

이제 정렬부 구현은 다음 단계가 남아있다.

 1. 중간값을 포함해서 그보다 큰 값은 스택a에 오름차순 정렬

2. 중간값 미만 값은 스택 b로 옮겨서 내림 차순 정렬

3. 스택a와 스택b 모두 정렬이 끝나면 스택 b의 값을 top부터 모두 스택 a로 옮기기