크래프톤 정글 WEEK5 Day 36 - Stack and Queue

회고

오늘 스택 큐 과제 다 풀었다!!

연결리스트에 비해 비교적 쉬워서 푸는데 금방 걸렸다. CSAPP 6장 읽다가 포기..... 마저 다 읽을 수 있을지 (자칭 캔들) 강민님 티스토리 봐야겠당

 

CSAPP 

CSAPP 6-1

 

Stack and Queue

1. createQueueFromLinkedList

 

큐(링크드 리스트 기반) 생성 / 홀수 값 제거

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
	/* add your code here */
	ListNode *temp = ll->head;
	
	while(temp != NULL){
		enqueue(q, temp->item);
		temp = temp->next;
	}
}

void removeOddValues(Queue *q)
{
	/* add your code here */
	if(q ==NULL)
		return;

	int count = q->ll.size;

	for(int i = 0; i<count; i++)
	{
		int item = dequeue(q);		//큐의 모든 item을 순회하면서 각 큐에서 제거
		if(item % 2 == 0)		//그 아이템이 짝수인 경우 다시 큐에 추가
			enqueue(q, item);
	}
}

 

createStackFromLinkedList

 

스택(링크드 리스트 기반) 생성 / 짝수 제거

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
    /* add your code here */
	ListNode *temp = ll->head;

	while(temp != NULL)
	{
		push(s, temp->item);
		temp = temp->next;
	}
}

void removeEvenValues(Stack *s)
{
	/* add your code here */
	Stack stack;			//새로운 stack 생성
	stack.ll.head = NULL;
	stack.ll.size = 0;

	while(!isEmptyStack(s))
	{
		push(&stack, pop(s));	//원래 스택에서 아이템을 꺼내 임시 스택에 넣음
	}

	while(!isEmptyStack(&stack))
	{
		int item = pop(&stack);		//임시 스택에서 아이템을 꺼내서 홀수인 경우, 원래 스택에 다시 pop
		if(item % 2 == 1)
			push(s,item);
	}
}

 

3. isStackPairwiseConsecutive

 

스택 내의 숫자들이 짝수로 연속적인지 아닌지 검사한다.

int isStackPairwiseConsecutive(Stack *s)
{
  	/* add your code here */
	Stack temp;
	temp.ll.head = NULL;
	temp.ll.size = 0;

	if(s->ll.size % 2 != 0)		//stack의 size가 홀수이면 return 0 -> 쌍으로 연속되지 못하기 때문
		return 0;

	while(!isEmptyStack(s))
	{
		push(&temp, pop(s));
	}

	while(!isEmptyStack(&temp))
	{	
		int item = pop(&temp);
		int item1 = pop(&temp);

		if(abs(item - item1) != 1)
			return 0;
	}
	return 1;
}

 

4. reverseQueue

 

스택을 사용해서 큐를 뒤집는다.  

void reverse(Queue *q)		//스택을 이용해서 q에 삽입
{
	/* add your code here */
	Stack s;
	s.ll.head = NULL;
	s.ll.size = 0;

	while(!isEmptyQueue(q))
	{
		push(&s, dequeue(q));	//스택에 push (LIFO) 
	}

	while(!isEmptyStack(&s))
	{
		enqueue(q, pop(&s));	//다시 큐로 삽입 (FIFO)
	}
}

 

5. recursiveReverseQueue

 

재귀를 사용해서 큐를 뒤집는다.

void recursiveReverse(Queue *q)
{
	/* add your code here */
	if(q->ll.head == NULL)	return;
	int temp = dequeue(q);
	recursiveReverse(q);
	enqueue(q,temp);
}

 

6. removeUntilStack

 

종문님께서 딱 두 줄로 끝낼 수 있다고 알려주셨는데, peek() 함수를 사용해서 스택의 가장 위에 있는 항목을 확인해서 그 값이 value가 아니면  pop시키면 끝!

void removeUntil(Stack *s, int value)
{
	/* add your code here */
	while(!isEmptyStack(s) && peek(s) != value)
		pop(s);
}

//스택의 가장 위에 있는 항목 반환
int peek(Stack *s){			
    if(isEmptyStack(s))
        return MIN_INT;
    else
        return ((s->ll).head)->item;
}

 

7. balanced

 

() [] {} 문자들로 구성된 식이 균형을 이루고 있는지를 판단하는 함수이다.

 

이것도 갓종문 찬스!

ASCII 코드를 사용해서 풀면 된다!

() -> 40,41 [] -> 91,93 {} -> 123,125 를 보면  1, 2 차이나는 걸 활용하면 된다.

스택이 비어있다는 의미는 균형이 잡혔다는 의미

int balanced(char *expression)
{
	/* add your code here */
	Stack stack;
	stack.ll.head = NULL;
	stack.ll.size = 0;
	int i = 0;

	//ASCII - () -> 40,41 [] -> 91,93 {} -> 123,125 
	while(expression[i])
	{
		char exp = expression[i];
		if(peek(&stack) == exp -1 || peek(&stack) == exp -2)	//ASCII 코드에서 1, 2차이 나는 경우
			pop(&stack);
		else
			push(&stack,exp);
		
		i += 1;
	}

	if(isEmptyStack(&stack))
		return 0;		//균형이 잡혀있다를 의미
	else
		return 1;
}

 

아스키 문자

 

33에서부터 126까지의 ASCII 문자