JArchive 프로그래밍 일기

큐

큐는 먼저 들어온 일부터 먼저 처리하는 자료구조 입니다. 

선입 선출, First In First Out (FIFO) 라고 합니다. 

큐의 기능 

큐의 가장 앞 요소를 전단, 마지막 요소를 후단이라고 합니다. 

(스택은 최상위 노드가 있는 입구에서만 삽입/제거가 수행됩니다. )

큐는 전단에서 Dequeue (제거) 되고, 후단에서만 Enqueue (삽입) 됩니다. 

순환 큐 

유의할 점은 큐가 비었는지 가득찼는지 구분을 위해 큐를 실제 용량보다 1 크게 만드는 것입니다. 

용량이 7인 큐를 만든다고 하면, 

구현할 때는 8인 큐를 만듭니다. 

비었을 때는 전단과 후단이 같은 곳을 가리킵니다 

큐가 꽉 찼을 때는 후단 바로 다음이 전단이 됩니다. 

이렇게 후단과 전단 사이에 공간을 두어 큐의 상태를 구분합니다. 

후단은 실제 데이터가 있는 칸의 바로 다음칸을 가리키고 있음을 유의해야 합니다.

후단 인덱스는 항상 빈 칸을 가리키고 있어야 합니다. 

순환 큐 구현

노드와 큐 구조체를 선언합니다.

typedef struct Node {
	int data;
};

typedef struct Cqueue {
	int capacity;
	int front;
	int rear;
	Node* nodeArray;
};

Cqueue구조체에서 nodeArray 포인터는 자유저장소에 존재하는 배열의 첫번째 칸을 가리킵니다. 

공백과 포화를 구분하기 위해 실제 capacity + 1하기 위한 '더미 노드'를 하나 둡니다.  

큐를 만들고 메모리 해제하는 함수 

void CreateCqueue(Cqueue** cqueue, int capacity) {

	(*cqueue) = (Cqueue*)malloc(sizeof(Cqueue));

	(*cqueue)->capacity = capacity;
	(*cqueue)->front = 0;
	(*cqueue)->rear = 0;
	(*cqueue)->nodeArray = (Node*)malloc(sizeof(Node) * (capacity + 1));

}

nodeArray 라는 이름의 배열은 사용자가 요구한 용량보다 1개 크게 만들어집니다. 더미 노드를 포함하기 때문입니다. 

void FreeCqueue(Cqueue* cqueue) {

	free(cqueue->nodeArray);
	free(cqueue);
}

삽입(Enqueue)

뒤에서 삽입하니까 rear를 관리합니다. 

rear는 항상 삽입'할' 타겟 인덱스를 가리키고 있습니다.

즉, 빈 공간을 가리키고 있다는 뜻입니다. 

capacity + 1인 인덱스는 공백/포화를 구분할 더미노드의 위치입니다. 

void Enqueue(Cqueue* cqueue, int data) {

	int position = 0;

	if (cqueue->capacity + 1 == cqueue->rear) {
		position = cqueue->rear;
		cqueue->rear = 0;
	}
	else {
		position = cqueue->rear++;
	}

	cqueue->nodeArray[position].data = data;
}

제거(Dequeue)

앞에서 제거하니까 front를 관리합니다. 

front와 capacity가 같은 상황은 전단이 배열 맨 끝에 와있다는 것입니다. 

노드를 하나 제거 하면, 인덱스를 0으로 돌려놔야 합니다. 

이 경우를 제외하면 front를 하나 감소시키면 됩니다.

int Dequeue(Cqueue* cqueue) {

	int position = cqueue->front;

	if (cqueue->front == cqueue->capacity ) {
		cqueue->front = 0;
	}else{
		cqueue->front++;
	}
	
	return cqueue->nodeArray[position].data;
}

큐의 공백과 포화 확인하기 

공백 : front 와 rear 가 같은 곳을 가리키고 있습니다. 

int IsEmpty(Cqueue* cqueue) {
	return 	(cqueue->front == cqueue->rear);
}

포화: rear의 바로 다음이 front 입니다. 또는 rear에서 front를 빼면 그 길이가 capacity가 됩니다. 

int IsFull(Cqueue* cqueue) {
	if (cqueue->front < cqueue->rear) {
		return (cqueue->rear - cqueue->front == cqueue->capacity);
	}
	else {
		return (cqueue->front == cqueue->rear + 1);
	}
}

메인함수 - 삽입/제거 해보기 

5개를 저장할 수 있는 배열을 만들고, 8번 삽입, 6번 제거해봤습니다. 

삽입 전에 포화인지 검사하고 포화이면 탈출합니다. 

제거 전에 비었는지 검사하고 비었으면 탈출합니다. 

int main(void) {

	int i = 0; 
	Cqueue* queue;

	// 5개를 저장할 수 있는 배열 
	CreateCqueue(&queue, 5);

	// 8번 삽입 
	for (int cnt = 1; cnt < 9; cnt++) {
		if (!IsFull(queue)) {
			printf("%d를 삽입.\n", cnt);
			Enqueue(queue, cnt);
		}
		else {
			printf("큐가 꽉 찼습니다.\n");
			break;
		}
	}

	// 6번 제거
	for (int cnt = 1; cnt < 7; cnt++) {
		if (!IsEmpty(queue)) {
			printf("%d 를 제거.\n", Dequeue(queue));
		}
		else {
			printf("큐가 비었습니다.\n");
			break;
		}
	}

	return 0;
}

오늘 한 일 

잠시 놓았던 자료구조를 다시 봤다. (링크드 리스트, 스택, 큐, 트리)

생각거리 

3월 3일(화) ~ 3월 5일(목) 3일 동안 할아버지를 잘 보내드리고 왔다. 할아버지 이제 할머니 곁에서 편히 쉬세요. 

오늘 한 일 

스택으로 사칙연산 함수, 큐, 트리 기본구조를 공부했다. 

내일은 코딩에 비중을 두고 진행해야겠다. 

생각거리 

공부 집중을 위해 공부하는 공간을 바꿔보는 것도 가끔 해볼 만한 시도다.

오늘 한 일 

스택을 응용하여 사칙연산 계산을 하는 함수를 만들고 있다. 

책에 나온 코드를 참고하려고 하는데, 애를 먹었다.

생각거리 

사칙연산 계산 함수가 하루 안에는 끝날 줄 알았는데. 

이해 안가는 것이 한 두개가 아니었고 힘들었다. 

오늘 한 일 

알고리즘 스터디에서 더블,환형 링크드 리스트, 스택, 큐를 공부했다. 

나는 배열로 짜는 스택, 리스트로 짜는 스택을 맡았고,

스터디원은 리스트와 큐를 맡았다. 

리스트로 짜는 스택을 만들 때 불필요해 보이는 코드가 있어서 같이 고민했다. 

다음주에는 내가 스택으로 짜는 사칙연산과 큐를 준비해가기로 했다. 

생각거리

알고리즘 공부를 오랜만에 하려니 쉽지가 않다. 

그래도 이정도 해내가고 있는 것에 자신감을 갖고 화이팅해야지.

코로나가 4월에 피크라는데, 앞으로 2달동안은 정말 몸사리면서 주의해야겠다.

더 이상 확진자가 안나왔으면 좋겠다. 

오늘 한 일 

배열로 스택을 짰다. 

링크드 리스트로 스택을 짰다. 

생각거리 

스택 짜는게 약간 헷갈린다. 

내일은 사칙연산계산기를 스택으로 짜보고, 큐를 공부할 계획이다. 

윈도우 시스템 프로그래밍 책을 보다가 막힌 부분이 있었다. 매크로가 기억이 안난다. 

기본서를 다시 봐야겠다. 

오늘 한 일 

SQLD 모델링쪽 공부했다. 

리스트를 다시 짜봤다. 

배열로 스택을 다시 짜봤다. 

생각거리

연차가 끝나고 실질적으로 회사에 안나간지 25일이 지났다. 거의 한달.

시간이 빠르다. 

SQLD 시험이 코로나 때문에 4월 11일로 연기되서 맥빠진다. 

코로나 확진자가 977명이다. 조심하자 조심!