개발하는데 다 이유가 있겠지

1. 연결 리스트를 이용해 스택 만들기

• 큐는 선입선출(FiFO : First In, First Out)이고, 스택은 후입선출(LIFO : Last In, First Out)이므로 구현이 약간 다름

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
	ListNode *cur = ll->head;
	ListNode *cur_s = s->ll.head;
	ListNode *new_node;
	if (cur == NULL)
	{
		return;
	}

	while (cur != NULL)
	{	
    	// 새로운 노드를 만들고 메모리 할당을 받아 주소를 저장
		new_node = malloc(sizeof(ListNode));
        // 스택에 노드가 있는 경우
		if (s->ll.head == NULL)
		{
			s->ll.head = new_node;
			cur_s = new_node;
			new_node->item = cur->item;
			new_node->next = NULL;
		}
		else
		{
        	// 스택에 노드가 없는 경우
			new_node->next = cur_s;
			new_node->item = cur->item;
			s->ll.head = new_node;
			cur_s = new_node;
		}
		cur = cur->next;
	}
}

---

1-2. 스택에서 짝수만 제거하기

• 어제 했던 홀수 제거하기와 부등호만 다름

void removeEvenValues(Stack *s)
{
	ListNode *cur = s->ll.head;
	ListNode *prev = NULL;
	while (cur != NULL)
	{
		if (cur->item % 2 == 0)
		{
			if (prev == NULL)
			{
				// 처음이 짝수일 때
				s->ll.head = cur->next;
			}
			else
			{
				// 중간이 짝수일 떄
				prev->next = cur->next;
			}
			cur = cur->next;
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
}

---

2. 짝을 지어 비교해 연결된 숫자인지 비교하는 스택

• 전체의 개수가 홀수인 경우 0을 리턴
• 2개의 수가 연속되는 숫자로 이루어진 쌍이어야 함
• 전체의 개수가 짝수이면 두 개를 스택에서 pop해서 두 숫자의 차의 절대값이 1이면 연속된 숫자로 판단

int isStackPairwiseConsecutive(Stack *s)
{
	int size = s->ll.size;
	int first, second = 0;
	if (size % 2 == 0)
	{
		while (s->ll.head != NULL)
		{
			first = pop(s);
			second = pop(s);
			if (abs(first - second) == 1)
			{
				continue;
			}
			else
			{
				return 0;
			}
		}
		return 1;
	}
	else
	{
		return 0;
	}
}

---

3. 큐에 담긴 숫자들을 뒤집기

• 입력받아 큐에 저장된 숫자들을 스택에 옮겨 닮은 뒤 다시 큐로 옮겨담는 방식

void reverse(Queue *q)
{
	ListNode *cur_q = q->ll.head;
	Stack *s = malloc(sizeof(Stack));
	ListNode *cur_s = s->ll.head;

	if (q->ll.head == NULL)
	{
		return;
	}

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

	cur_q = q->ll.head;

	while (s->ll.head != NULL)
	{
		cur_q->item = pop(s);
		cur_q = cur_q->next;
	}
}

---

4. 재귀를 통해 큐를 뒤집기

• 미리 구현된 enqueue와 dequeue를 이용해 재귀를 통한 구현

void recursiveReverse(Queue *q)
{
	int temp = 0;
	if (q->ll.head == NULL)
	{
		return;
	}
	temp = dequeue(q);
    // 재귀를 통해 구현
	recursiveReverse(q);
	enqueue(q, temp);
}

---

5. 스택으로 지정한 값까지 출력하기

• 스택을 이용해 지정한 값과 동일한 값이 나올 때까지 미리 구현된 pop함수를 통해 탐색
• pop() 함수는 자동으로 head를 연결해줌

void removeUntil(Stack *s, int value)
{
	if (s == NULL)
		return;
	while (s->ll.head->item != value)
	{
		pop(s); 
	}
}

---

6. 문자열 좌우 균형 맞추기

• 문자열 중에서 여는 괄호들만 스택에 추가
• 닫는 괄호를 만나면 pop으로 꺼낸 괄호와 비교해서 짝이 맞는 괄호면 넘어가고 아니면 스택에 남겨짐
• isEmptyStack() 함수를 통해 현재 스택에 남은 것이 있는지 판단
• 남은 것이 있다면 짝이 맞게 위치하지 않았으므로 " not balanced"를 출력하게 됨

내가 짠 코드

int balanced(char *expression)
{
	Stack *s = malloc(sizeof(Stack));
	char temp;
	for (int i = 0; expression[i] != '\0'; i++)
	{
		if (expression[i] == '(' || expression[i] == '{' || expression[i] == '[')
		{
			push(s, expression[i]);
		}
		else if (expression[i] == ')' || expression[i] == '}' || expression[i] == ']')
		{
			temp = pop(s);
			if (temp == '(' && expression[i] == ')')
			{
				continue;
			}
			else if (temp == '{' && expression[i] == '}')
			{
				continue;
			}
			else if (temp == '[' && expression[i] == ']')
			{
				continue;
			}
		}
	}
	if (isEmptyStack(s) == 1)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

---

다른분 코드

int balanced(char *expression)
{
	Stack *s = malloc(sizeof(Stack));
	while (*expression != '\0')
	{
		if (*expression == '(' || *expression == '[' || *expression == '{')
		{
			push(s, *expression);
			expression++;
		}
		else if (*expression == ')' || *expression == ']' || *expression == '}')
		{
			if (*expression == ']' && peek(s) == '[')
			{
				pop(s);
				expression++;
			}
			else if (*expression == ')' && peek(s) == '(')
			{
				pop(s);
				expression++;
			}
			else if (*expression == '}' && peek(s) == '{')
			{
				pop(s);
				expression++;
			}
		}
		if (isEmptyStack(s) != 1)
		{
			return 1;
		}
	}
	return 0;
}