C언어로 스택과 큐 구현하기

이번 주 주된 과제는 기존 자료구조 형태를 이해하고 만드는 형태보다는 그 형태를 보다 깊게 이해했는지 확인하기 위해 응용 방안을 하나씩 구현하는 내용이다. 대학 과제처럼 도움이 될 수도 있고 딱히 별 의미가 없는 함수들이 존재하는 경우도 있었다. 하지만 이렇게 되서 이렇게 이렇게 된다라는 것을 아는 것은 도움이 된다.

특히나 몇몇 학우들은 있는지도 모르고 처음부터 끝까지 만들었다는데 무언가 그 쌩 고생했다는 감정은 무슨 느낌인지 이해하지만 난 기초적인 자료구조만큼 시간을 들이박아서 정직하게 결과가 나오는게 잘 없다고 생각한다. 약간 여유로웠던 나를 반성 해야겠지만 이번 주는 조금 여유가 필요했다고 생각중

---

기초 선언 코드

Queue, Stack 모두 Linked List 기반으로 이루어질 것이다. 그래서 전체적인 정의는 이런 모양새이다 :

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;


typedef struct _queue
{
	LinkedList ll;
} Queue;

Stack은 이렇게.

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;

typedef struct _stack
{
	LinkedList ll;
}Stack;

공용 사용 함수들이다.

int insertNode(LinkedList *ll, int index, int value){
	// Queue Stack의 전신은 사실 여기에 있다..
    // ll은 내부의 자료구조인 연결리스트 처음, index는 몇 번째, value는 실제로 넣을 값.
	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;
        // 뭔가 상태가 꼬롬한 애들은 즉시 중단한다.

    // 만약 비어있는 노드이던가, 첫 위치에 삽입을 시도하는 상황이라면, 연결 리스트의 첫 시작점을 갱신한다.
	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		if (ll->head == NULL)
		{
			exit(0);
		}
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	// 이 함수는 index로 위치를 지정 할 수도 있다. 
    // 하지만 크기 단위로써의 index 사용이 큐의 사용으로써 일치 할 수 있을 것이다.
	// 새로운 노드를 만들고, 이 노드를 이어주는 과정으로 계속된다.
	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		if (pre->next == NULL)
		{
			exit(0);
		}
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

int removeNode(LinkedList *ll, int index){
	// 노드 제거를 시도하는 함수이다. ll은 연결 리스트 전신 중 머리, index는 몇 번째.
	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// 첫 노드가 제거되는 경우, 이에 대한 별도 처리가 필요하다.
	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;
		return 0;
	}

	// 첫 노드가 아닌 경우엔 큰 염려가 없다. index 번째를 찾아서 제거한다.
	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
        // 이 내용에 제거 대상의 next 주소를 손실 없이 옮겨주는 내용이 포함되어있다.
	}

	return -1;
}

ListNode * findNode(LinkedList *ll, int index){
	// 특정한 노드를 찾아야한다. 이 함수는 넣을때 뺄 때 모두 활용된다. 가끔은 아님.
	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;
        // 상태가 꼬롬한건 즉시 종료한다.

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}
    // index 번째를 찾아야하니 순회 시도 때마다 index가 빠진다.
    // index가 0이 되면 while 문을 종료하고 마지막까지 갱신되었던 temp를 넘긴다.

	return temp;
}

---

기본적으로 스택이던 큐던 사용하기 전 정의를 해야한다.

Stack *s = malloc(sizeof(Stack));
Queue *q = malloc(sizeof(Queue));

s.ll.head = NULL;
s.ll.size = 0;
    
q.ll.head = NULL;
q.ll.size = 0;
// 초기화 안하면 무조건 문제 생긴다.

// use data structures..
// 할 거 다 하고..

free(s);
free(q);

만일 포인터 형태로 정의하지 않는다면 함수가 끝날 때 저절로 free 된다.

하지만 이번 주 의도도 그렇고 앞으로 malloc을 아무렇지 않게 논해야하는 만큼 이런식으로 확실하게 할 수 있도록 습관화 하기.

다른 애매모호한 함수들은 적지 않아도 큰 문제가 없어서 뺐다. 원하면 금방 만들어 쓸 수 있을정도이니까.

---

Queue

enqueue : Queue에 아이템을 삽입한다

void enqueue(Queue *q, int item) {
	insertNode(&(q->ll), q->ll.size, item);
    // Queue에 넣는 듯 보이지만 Queue 내의 연결 리스트에 삽입을 시도한다.
}

 

deQueue : Queue에서 아이템을 제거 (반환)한다

int dequeue(Queue *q) {
	int item;

	if (!isEmptyQueue(q)) {
		item = ((q->ll).head)->item;
		removeNode(&(q->ll), 0);
		return item;
        // Linked List 내에 size 함수를 통해 isEmptyQueue가 작동한다.
        // 어떻게보면 그냥 여기서 다이렉트로 알아도 되지만, 함수로 묶어보면 이쁘니까..
	}
	return -1;
}

 

Queue Quest #1. 연결 리스트에서 큐로 옮기기

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
	ListNode *tmp = ll->head;
    // 연결 리스트의 첫 번째를 지정해준다.
	while(tmp != NULL)
	{
    	// NULL이 아니라는 것은 여전히 유효한 연결 리스트 범위를 다루고 있다는 것.
		enqueue(q, tmp->item);
		tmp = tmp->next;
        // 해당 내용들을 추가해준다.
	}
    // ll의 활용여지는 모르니 맥락상 free 하기엔 부적합하다.
}

 

Queue Quest #2. 큐의 아이템을 스택을 이용하여 뒤집기

void reverse(Queue *q)
{
	Stack *tmpStack = malloc(sizeof(Stack));

	tmpStack->ll.head = NULL;
	tmpStack->ll.size = 0;
	tmpStack->ll.tail = NULL;

	while (isEmptyQueue(q) == 0)
	{
		int item = dequeue(q);
		push(tmpStack, item);
		// 비어 있지 않은 동안 모든 아이템을 뽑아서 stack에 넣는다.
	}

	while (isEmptyStack(tmpStack) == 0)
	{
		int item = pop(tmpStack);
		enqueue(q, item);
		// stack이 비어 있지 않은 동안 모든 아이템을 뽑는 즉시 다시 q에 넣는다.
	}
	free(tmpStack);
}

Queue Quest #3. 재귀적으로 큐의 아이템을 뒤집기

void recursiveReverse(Queue *q)
{
	int temp;

	if(q->ll.head == NULL)
		return;
        // q가 다 뽑히면 중단
	
	temp = dequeue(q);
    // 아이템을 하나 뽑아서 저장을 해둔다.
    // 물론 지역변수인 덕분에 이것은 재귀가 도는 동안에도 수정되지 않고 유지된다.
	recursiveReverse(q);
    
	enqueue(q, temp);
    	// q에 빼둔 것들을 다시 삽입한다.

}

 

 

---

push : 스택에 값을 추가하기

void push(Stack *s, int item)
{
	insertNode(&(s->ll), 0, item);
    // 들어온게 제일 먼저 뽑히는 특성상 연결 리스트의 0번에 지속적인 삽입이 이루어진다.
}

pop : 스택에서 값을 제거(반환)하기

int pop(Stack *s)
{
	int item;
	if (s->ll.head != NULL)
	{
		item = ((s->ll).head)->item;
		removeNode(&(s->ll), 0);
        // insertNode와 마찬가지로 0에 대해서만 수행한다.
		return item;
	}
	else
		return MIN_INT;
        // 비어있는 경우 별 의미없는 상수 값을 뱉는다. int 리턴이라서..
}

 

Stack Quest #1. 연결 리스트에서 스택으로 옮기기

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
	ListNode *tmp = ll->head;
	while(tmp != NULL)
	{
		push(s, tmp->item);
		tmp = tmp->next;
	}
    // 그냥 유효한 값들마다 전부 이렇게 삽입 시도한다.
}

 

Stack Quest #2. 스택의 아이템이 쌍 단위로 연속적인지 확인하기

만약 쌍이 2개, 다시 말해 아이템이 4개 있다고 하면, 4개는 각 쌍에 대해 연속적이여야한다.
하지만, 앞의 쌍에 대해 연속적인 정도(차이)만큼 연속적이여야만 한다.

• 예를 들어, 14 10 8 4는 연속적이다. 그러나, 14 10 5 2 는 연속이 아니다.

nt isStackPairwiseConsecutive(Stack *s)
{
	// 위배할 쌍이 없기때문에 비어있는 경우도 연속적이라고 정의하기.
    // 쌍이 연속적이라면, 연속적인 그 차이만큼 다음 쌍에 대해서도 적용되어야한다.
	int size = custom_stackSize(s);
    // size를 구하는 함수가 없어 스스로 구하는 함수를 작성했다. 이 내용이 좀 필요하다.
	int subValue = 0;
	int isFirstTime = 1; // using like bool | 1 : true | 0 : false
	int isWrong = 0; // 1 : wrong | 0 : not wrong
	while(isEmptyStack(s) == 0)
	{
		if(size % 2 == 1)
		{
			// 아이템이 홀수개라면 pairwise부터 성립하지 않으니 즉시 종료합니다.
			isWrong = 1;
			return 0;
		}
		else
		{
			int low = pop(s);
			int notLow = pop(s);
            // low notLow의 연산 관계를 더 커지는 상황만 고려했었다.
            // 하지만, 작아지는 경우나 차이가 0인경우도 어떻게보면 연속적이라 할 수 있다.
            // abs 함수가 있으니 그냥 이 김에 구현을 끝냈다.
			
			if(isFirstTime == 1)
			{
				isFirstTime = 0;
				subValue = abs(low - notLow);
				continue;
			}

			if(subValue == abs(low - notLow))
			{
				isWrong = 0;
			}
			else
			{
				isWrong = 1;
				break;
			}
		}
		}

		return !isWrong;
        // isWrong을 bool 처럼 쓰려고 했는데, 실 main에서 원하는 값이 다소 달라서 반전한다.
	}

Stack Quest #3. 찾고자 하는 아이템이 나올 때 까지 아이템 pop

void removeUntil(Stack *s, int value)
{
	int isContinue = 1;

	while (isContinue)
	{
		int poped = pop(s);
		if(poped != MIN_INT)
		{
        	// NULL이 아니면? 과 동의어로 생각하자.
            // MIN_INT를 던졌다는건 이거 이상으로만 숫자가 배치된다라는 암시 아닐까?
            // isContinue도 bool처럼 사용한다.
			if(poped == value)
			{
				isContinue = 0;
				push(s, poped);
			}	
		}
		else
		{
			isContinue = 0;
		}
	}

	// remove until 이니까 value가 나올 때 까지 시도하는게 맞다.
}

 

Stack Quest #4. 괄호 매칭 상태가 적절한지 확인하기

()[] 가능. ([)] 불가능. 

int balanced(char *expression)
{

// 스택이 연결 리스트 기반이며, 이 연결 리스트의 아이템은 int만 담을 수 있게 구성 되어있습니다.
// 전체적인 그림을 해치지 않는 선에서 구현하려고 하니, 각 괄호에 대해 매핑 시키는게 좋을 것 같습니다.
// 여기서 이용할 매핑은 () 는 1, {}는 2, []는 3 입니다.

// 열리는 괄호, 즉 ( { [ 가 들어오면 해당하는 숫자를 스택에 푸시합니다.
// 닫히는 괄호, 즉 ), }, ]가 들어오면 해당하는 숫자가 Stack의 top에 있는지 확인합니다.
	// 물론 top에 없으면, 즉시 프로그램을 종료합니다.
	// 0이 balanced True, 1이 NOT balanced 입니다.

	Stack *st = malloc(sizeof(Stack));

	st->ll.head = NULL;
	st->ll.size = 0;
	int item = 0;
	int notBalanced = 0;
	for (int i = 0; expression[i] != '\0'; i++) {
		char ch = expression[i];
		
		switch(ch)
		{
			case '(':
				push(st, 1);
				break;
			case ')':
				item = peek(st);
				if(item != 1)
				{
					notBalanced = 1;
				}
				else
					item = pop(st);
				break;
			case '{':
				push(st, 2);
				break;
			case '}':
				item = peek(st);
				if(item != 2)
				{
					notBalanced = 1;
				}
				else
					item = pop(st);
				break; 
			case '[':
				push(st, 3);
				break;
			case ']':
				item = peek(st);
				if(item != 3)
				{
					notBalanced = 1;
				}
				else
					item = pop(&st);
				break;

			default:
				break;
		}
		
		if(notBalanced == 1)
		{
			free(st);
			return 1;
		}
	}
	free(st);
	return 0;
}