[Jungle][TIL] 240417 Stack and Queue

createQueueFromLinkedList(LinkedList *ll, Queue *q)
: 연결리스트에 저장된 모든 정수들로 큐 만들기
앞에 있는 정수들을 enqueue first, 그 다음 정수들 순서로 enqueue해야 한다.

예시 현재 연결 리스트 1 , 2, 3, 4, 5 -> Resulting queue도 1, 2, 3, 4, 5 출력되도록

void createQueueFromLL(LinkedList *ll, Queue *q) 
{
	//큐가 비어있지 않다면 비우고 시작
    if (isEmptyQueue(q) {
    	removeAllItemsFromQueue(q);
    }
    //연결리스트의 헤드를 가리키는 포인터
    // temp -> 연결리스트 순회 
    ListNode *temp = ll-> head; 
    
    while (temp!=NULL) {
    	enqueue(q, temp->item);
        temp = temp -> next; 
        //다음 노드로 이동
    
    }
    

}

---

void createStackFromLL(LinkedList *ll, Stack *s)
: 연결리스트를 이용하여 스택 생성

void createStackFromLL(LinkedList *ll, Stack *s) 
{	
	//처음에 빈 스택이 아니라면 비우고 시작 
	if (isEmptyStack(s)) {
    	removeAllItemsFromStack(s);
    }
    
    //연결리스트의 헤드를 가리키는 포인터
    //temp를 이용해서 연결리스트 순회
    ListNode *temp = ll-> head;
	
    //연결리스트 순회하면서
    // 스택에 item push
    // push한 후에는 다음 노드로 이동시킨다.
	while (temp!= NULL) {
    	push(s, temp-> item);
        temp = temp-> next; 
    }
}

---

int isStackPairwiseConsecutive(Stack *s)
스택에 있는 숫자들이 Pairwise consecutive인지 아닌지 판단. 연속된 쌍인지 아닌지 판단
예시 16, 15, 11, 10, 5, 4 -> pairwise consecutive

int isStackPairwiseConsecutive(Stack *s) 
{ 
	int a ;
    int b; 
    
    // 스택의 요소 개수가 홀수이거나
    //빈 스택이라면 return 0 -> not pairwise consecutive
    if ( s -> ll.size % 2 != 0 || s -> ll.size == 0) {
    	return 0;
    }
    
    // 빈 스택이 아닐동안에 
    while (!isEmptyStack(s)) {
    	a = pop(s);
        b = pop(s);
        
        if (abs(a-b) != 1) {
        	return 0;
        }
    }
    
    return 1 ;
}

---

void reverse(Queue *q):
큐의 요소들을 역순으로 출력하는 함수

예시)
1, 2, 3, 4, 5 -> 5, 4, ,3, 2, 1 출력한다.
q를 역순으로 재배열해야 함.

void reverse(Queue *q) {

	//새로운 스택 newStack 선언 및 초기화
	Stack newStack ;    
    newStack.ll.head = NULL;
    newStack.ll.size = 0;

	//큐가 비어있지 않은 동안
    //큐에서 dequeue한 요소를 
    //newStack에 push
	while(!isEmptyQueue(q)) {
    	int a ;
        a = dequeue(q);
        push(&newStack, a);
    }
    //newStack에 저장된 요소들을 pop하여
    //원래의 큐에 enqueue -> 역순으로 요소들 삽입하게 된다. 
    while (!isEmptyStack(&newStack)) {
    	int b; 
        b = pop(&newStack);
        enqueue(q, b);
    }
}

---

recursiveReverseQueue(Queue *q):
재귀 사용하여 역순으로 큐를 재정렬하기
1, 2, 3, 4, 5 => 5, 4, 3, 2, 1

void recursiveReverse(Queue *q) {
	int temp;
    
    //큐가 비어있는 경우 
    if (q->ll.head == NULL ) {
    	return;
    }
    
    temp = dequeue(q);
    
    //재귀
    recursiveReverse(q);
    
    enqueue(q, temp);
}

예시) 큐에 (1, 2, 3) 이 있을 때
temp = 1, q = 2, 3
재귀 호출 recursiveReverse
-> temp = 2, q = 3
재귀 호출 recursiveReverse
-> temp = 3, q = NULL
재귀 종료

=> 역순으로 enqueue 수행
enqueue(q, 3);
enqueue(q, 2);
enqueue(q, 1);
그렇게 되면 => 3, 2, 1 출력된다.

---

void removeUntil(Stack *s, int value)
: value가 처음으로 나올 때까지 모든 값들 pop

void removeUntil(Stack *s, int value) 
{
	//스택이 비어있는 경우 
	if (s-> ll.size ==0) {
    	return ;
    }	
    //스택 맨 위의 요소가 value가 아닌 경우
    //맨 위의 요소를 제거한다. 
    while (s->ll.head -> item != value) {
    	pop(s);
    }
   
}

---

int balanced(char *expression)
() {} [] 괄호가 balanced된 것인지 아닌지 판단하는 함수

int balanced(char *expression) {
	Stack newStack; 
   	newStack.ll.size = 0;
    newStack.ll.head = NULL;

	while (*expression) {
    	char cur = *expression;
        
        //여는 괄호인 경우
        //stack에 push
		if (cur == '(' || cur == '[' || cur == '{') {
			push(&newStack, cur);
		}
        
        else {
        	if (isEmptyStack(&newStack)) {
            	return 1; 
            }
            
           	char stack_pop = pop(&newStack); 
            
            if (
				(cur == ')' && stack_pop != '(') ||
				(cur == '}' && stack_pop != '{') ||
				(cur == ']' && stack_pop != '[')) 
			{
				return 1;
			}
 		}
        // 다음 문자로 이동
		expression++ ;	

	}
	// 스택이 비어있다면 balanced 
	// 스택이 비어있지 않다면 unbalanced
	if (isEmptyStack(&newStack)) {
		return 0;
	} else {
		return 1;
	}

}

닫는 괄호가 cur인데
스택이 비었다면 -> 괄호가 맞지 않는 것 unbalanced

expression의 모든 문자를 처리하고 나서
스택이 비었다면 balanced,
스택이 비지 않았다면 Unbalanced

case 2:
            if(balanced(str))
                printf("not balanced!\n");
            else
                printf("balanced!\n");
			break;

not balanced -> 1 return
balanced -> 0 return
초반에 이 return 값을 제대로 안읽어서 헷갈리고 삽질했다.

---

수정해야하는 점이 있다면 댓글로 알려주세요