[C언어] Stack&Queue(3) - isStackPairwiseConsecutive 함수 구현하기

Stack&Queue(3) - isStackPairwiseConsecutive 함수 구현하기

스택 내 숫자가 짝수 단위로 연속적인지 확인하는 함수

주어진 요소 확인하기

구조체

• Stack: (struct) 스택 구조체
  • ll: (LinkedList) 스택 연산 구현을 위한 연결 리스트 구조체
• LinkedList: (struct) 연결 리스트 구조체
  • size: (int field) 연결 리스트 요소 갯수
  • *head: (pointer field) 연결 리스트 첫 노드의 주소
  • *tail: (pointer field) 연결 리스트 마지막 노드의 주소
• ListNode: (struct) 노드 구조체
  • item: (int field) 노드의 값
  • *next: (pointer field) 다음 노드의 주소

isStackPairwiseConsecutive 함수의 매개 변수

• *s: (pointer) 스택 주소

 

핵심 아이디어

• 스택이 비어있거나, 홀수 개이면 return 0
• 연속된다는 것은 두 값의 쌍의 차이가 1임을 의미
  • 16 15 (O) / 10 11 (O) / 10 6 (X)
• 쌍 중 하나라도 연속되지 않으면 return 0
• 모든 쌍이 연속되는 쌍이라면 return 1

 

구현하기

int isStackPairwiseConsecutive(Stack *s) {
	// 스택이 비어있거나 원소 개수가 홀수면 짝 검사 불가능
	if (s == NULL || s->ll.size % 2 == 1) return 0;
    
	// 스택에서 꺼낸 값을 임시로 저장할 버퍼 리스트 생성 및 초기화
	LinkedList *buf = malloc(sizeof(LinkedList));
	buf->head = NULL;
	buf->size = 0;
    
	int val1, val2;
	int isPair = 1;		// 초기값은 true로 설정
	
	// 스택에서 두 개씩 꺼내면서 짝 검사
	for (int i = 0; i < s->ll.size / 2; i++) {
		val1 = pop(s);
		val2 = pop(s);
        
		// 나중에 복원할 수 있도록 버퍼에 역순으로 저장 (stack 구조 고려)
		insertNode(buf, 0, val1);
		insertNode(buf, 0, val2);
        
		// 두 수의 차가 1이 아니면 실패 처리 및 반복문 종료
		if (abs(val1 - val2) != 1) {
			isPair = 0;
			break;
		}
	}
    
	// 버퍼에 저장된 값을 이용해 원래대로 스택 복원
	ListNode *cur = buf->head;
	while (cur != NULL) {
		push(s, cur->item);
		cur = cur->next;
	}
    
	free(buf);	// 메모리 누수 방지
	return isPair;	// 결과 반환 (1: 모두 짝 연속(성공), 0: 실패)
}