크래프톤 정글 week05, day37 - 연휴 과제 - 큐, 스택

• 연결리스트의 노드들을 큐를 사용해 저장하고 노드가 홀수 값이면 제거

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
	// 현재 노드를 가리키는 포인터를 선언
	ListNode *cur;

	// 시작하기 전 매개변수로 받은 큐를 전부 없애기
	removeAllItemsFromQueue(q);

	// 현재 노드에 리스트의 첫 노드를 넣기
	cur = ll->head;
	// 현재 노드가 존재하는 동안 반복하며
	while(cur != NULL) {
		// 큐를 삽입(enqueue에 큐와 현재 노드의 값을 인자로 보내기)
		enqueue(q, cur->item);
		// 현재 노드를 다음 노드로 변경
		cur = cur->next;
	}
}

void removeOddValues(Queue *q)
{
	// 만약 큐가 비어있다면 반환
	if(q == NULL) {
		return;
	}

	// 큐의 리스트 노드 개수만큼 count에 넣기
	int count = q->ll.size;

	// 노드 개수만큼 반복
	for (int i = 0; i < count; i++) {
		// item 변수에 큐에서 삭제한 값을 넣기
		int item = dequeue(q);
		// 만약 삭제한 값이 짝수라면
		if(item % 2 == 0) {
			// 큐에 다시 추가하기
			enqueue(q, item);
		}
	}

}

 

 

• 연결리스트에서 스택을 사용해 값을 저장하고 노드가 짝수이면 제거

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
	// 현재 노드를 가리키는 포인터 선언
	ListNode *cur;

	// 스택을 전체 삭제 하기(초기화)
	removeAllItemsFromStack(s);
	// 현재 노드에 리스트의 첫 노드를 넣기
	cur = ll->head;
	// 노드가 빌 때까지 반복
	while(cur != NULL) {
		// 스택에 현재 노드의 값을 넣고 현재 노드를 다음 노드로 변경
		push(s, cur->item);
		cur = cur->next;
	}


}

void removeEvenValues(Stack *s)
{
	// 임시 스택을 생성
	Stack stack;
	// 스택의 리스트 노드 개수를 0으로 초기화하고 첫 노드를 NULL
	stack.ll.size = 0;
	stack.ll.head = NULL;

	// 스택이 빌 때까지 반복하며
	while(!isEmptyStack(s)) {
		// 임시 스택에 스택에서 뺸 값을 넣기
		push(&stack, pop(s));
	}

	// 임시 스택이 빌 때까지 반복하며
	while(!isEmptyStack(&stack)) {
		// 임시 변수 temp에 임시 스택에서 뺀 값을 넣기
		int temp = pop(&stack);
		// 만약 임시 변수의 값이 홀수라면
		if(temp % 2 == 1) {
			// 다시 스택에 임시 변수를 넣기
			push(s, temp);
		}
	}
}

 

 

• 스택에 들어있는 값이 쌍이 맞는지 확인하기(예시 : 60 59 14 13 8 7 은 쌍이 맞다)

int isStackPairwiseConsecutive(Stack *s)
{
	// 임시 스택을 생성하고 개수와 첫 노드를 초기화
	Stack tempStack;
	tempStack.ll.size = 0;
	tempStack.ll.head = NULL;

	// 만약 스택의 개수가 홀수면 바로 리턴0
	if(s->ll.size % 2 == 1) {
		return 0;
	}

	// 스택이 빌때까지 임시 스택에 때려넣기
	while(!isEmptyStack(s)) {
		push(&tempStack, pop(s));
	}

	// 임시 스택이 빌 때까지 스택을 두 개씩 꺼내서 temp1과 temp2에 넣기
	while(!isEmptyStack(&tempStack)) {
		int temp1 = pop(&tempStack);
		int temp2 = pop(&tempStack);

		// 절대값 temp1-temp2가 1이 아니면 바로 나감
		if(abs(temp1 - temp2) != 1) {
			return 0;
		}
	}

	// 스택이 비었다는 건 쌍이 맞다는 뜻이니 return 1 반환
	return 1;
}

 

 

• 큐에 있는 값들을 거꾸로 다시 넣기

void reverse(Queue *q)
{
	// 스택을 선언하고 초기화
	Stack stack;
	stack.ll.head = NULL;
	stack.ll.size = 0;

	// 큐가 빌 때까지 반복하면서
	while(!isEmptyQueue(q)) {
		// item변수에 큐에서 빼낸 값을 넣고
		int item = dequeue(q);
		// 그 값을 스택에 넣는다
		push(&stack, item);
	}

	// 스택이 빌 때까지 반복하며
	while(!isEmptyStack(&stack)) {
		// 스택의 값을 큐에 다시 삽입한다.
		enqueue(q, pop(&stack));
	}
}

 

 

• 재귀로 거꾸로 하기

void recursiveReverse(Queue *q)
{
	// 만약 큐가 비어있다면 리턴
	if(isEmptyQueue(q)) {
		return;
	}

	// item에 큐에서 뺀 값을 넣고
	int item = dequeue(q);
	// 큐를 인자로 재귀를 돌려서
	recursiveReverse(q);
	// item값을 큐에 삽입
	enqueue(q,item);
}

 

 

• 입력한 값이 나올때까지 스택에서 제거하기
  • 코드가 진짜 짧다

void removeUntil(Stack *s, int value)
{
	// 스택이 존재하고 스택의 값이 입력한 값과 같을때까지 팝팝
	while(!isEmptyStack(s) && peek(s) != value) pop(s);
}

 

 

• 입력된 괄호가 올바르게 닫혔는지 확인하는 함수

int balanced(char *expression)
{
	// 매개변수가 문자열이기 때문에 스택을 생성하고 초기화
	Stack tempStack;
	tempStack.ll.head = NULL;
	tempStack.ll.size = 0;

	// 문자열이 존재하는 동안 반복
	while(*expression) {
		// 만약 문자열이 {, [, (로 열린 괄호라면 그 값을 스택에 넣기
		if(*expression == '{' || *expression == '[' || *expression == '('){
			push(&tempStack, *expression);
		// 그게 아니라 }, ], )로 닫힌 괄호면서
		} else {
			// 만약 스택이 비어있다면 not balanced
			if(isEmptyStack(&tempStack)) {
				return 1;
			// 스택이 남아있고
			} else {
				// 스택을 pop한 걸 check에 담아
				char check = pop(&tempStack);
				// 만약 문자열이 ), ], } 이고 각 괄호별로 맞지 않다면
				if((*expression == ')' && check != '(') || 
					(*expression == ']' && check != '[') || 
					(*expression == '}' && check != '{')) {
						// not balanced
						return 1;
				}
			}
		}
		// 다음 문자로 이동
		expression++;
	}
	// 만약 스택이 비어있다면 balanced, 아니면 not balanced
	if(isEmptyStack(&tempStack)) {
		return 0;
	} else {
		return 1;
	}
}

 

이진트리와 이진 탐색트리가 남았는데 갈길이 멀다.

​

학습 시간 : 13 ~ 25시