[Data Structure] Linked list(Stack/Queue push and pop)

2018년... 1학기였나 자료구조를 배우고 과제로 linked list를 이용해서 스택과 큐 구현하는 과제가 있었다

복습할 겸 코드 리뷰

typedef struct home { // 단순 연결 리스트의 노드 구조를 구조체로 정의
	int index;
	char city[10];
	int post;
	struct home *link;
}home_t;

변수 이름은 그렇게 중요하지 않다... 일단 각 노드의 번호를 나타내는 정수형 index 변수와 그 안에 정보를 담는 문자열 city, 전화번호였나 우편번호를 저장하려고 정수형 post 변수를 정의했다.

그 다음 가장 중요한게 linked list를 구현할 것이기 때문에 다음 가리키는 노드가 자기 자신과 같은 형태의 구조체이다. 따라서 "자기참조구조체"를 사용해야하므로, 같은 형태인 home 구조체를 가리키는 포인터 변수 하나를 정의했다.

typedef struct Stack {
	home_t* top;
}Stack;

typedef struct Queue {//Queue 구조체 정의
	home_t *front; //맨 앞
	home_t *rear; //맨 뒤
	int count;//보관 개수
}Queue;

 다음은 위 정의한 노드를 이용해서 스택과 큐 구조체를 각각 정의해 준 것이다.

스택은 한구멍으로 들어가고 나가고(LIFO)가 이루어지기 때문에 가장 앞 노드를 가리키는 top 포인터 변수 하나만 선언해주었다.

큐는 맨 앞으로는 나가기만, 맨 뒤로는 들어가기만 하므로(FIFO) 앞을 가리키는 포인터와 뒤를 가리키는 포인터 하나씩하고 안에 몇개가 들어있는지 알아야 지금 비어있는지 아닌지 확인할 수 있기 때문에 정수형 count 변수를 준비했다.

void InitStack(Stack *stack) { //스택 초기화
	stack->top = NULL;

}
int IsEmpty(Stack *stack) { //스택이 비었는지 확인
	return stack->top == NULL;
}

스택 초기화의 경우는 맨 처음 노드를 삽입할 때, 원소가 없기 때문에 가장 처음 노드가 가리키는 것이 NULL이 되어야 하기 때문에 따로 정의하였다.

IsEmpty는 스택이 비었을 때는 pop과 같은 연산을 진행하면 안되기 때문에 비어있다면 위와 같이 top이 NULL임을 리턴하도록 하였다.

void Push(Stack *stack, home_t* p) {//스택에 보관
	home_t *now = (home_t *)malloc(sizeof(home_t)); //노드 생성
	now->index = p->index;//데이터 설정
	strcpy(now->city, p->city);
	now->post = p->post;
	now->link = stack->top;//now의 link링크를 현재 top으로 설정   
	stack->top = now;   //스택의 맨 앞은 now로 설정
}

먼저 노드를 삽입하는 Push 함수이다.

동적할당을 이용하여 노드 공간을 할당하고, 각각의 노드 내의 정보를 설정해준다.

스택은 위와 같이 노드가 추가될 때마다 top이 새로 삽입된 노드로 바뀐다. 

해당 부분을 처리해주는 것이 코드 밑에 두줄이다. 

int Pop(Stack *stack) {//스택에서 꺼냄
	home_t *now;
	int re;

	if (IsEmpty(stack)){
		return 0;
	}
	now = stack->top;//now를 top으로 설정
	re = now->index;//꺼낼 값은 now의 index로 설정

	stack->top = now->link;//top을 now의 link로 설정
	free(now);
	return re;
}

스택에서 노드를 삭제하는 Pop 함수이다. 비어있다면 삭제할 것이 없으니 먼저 비어있는지 확인한다.

스택에서의 pop은 항상 가장 꼭대기의 노드를 삭제하는 것이다. 따라서 현재 가장 top에 있는 노드가 가리키는 노드, 즉 now->link가 top 밑에 있는 노드이기 때문에 stack->top이 now->link를 가리키게 한 후, now를 삭제한다.

여기까지가 Stack의 push pop!! 다음은 Queue로 가겠슴다

void InitQueue(Queue *queue){
	queue->front = queue->rear = NULL; //front와 rear를 NULL로 설정
	queue->count = 0;//보관 개수를 0
}

int IsEmpty(Queue *queue){
	return queue->count == 0;    // 빈 상태
}

큐도 일단 초기화로 앞과 뒤를 가리키는 포인터를 NULL로 해준다. 그리고 보관하고 있는 노드도 없으니 0!

큐는 count로 노드 수를 관리하므로 count값이 0이면 비어있다고 리턴해주도록 IsEmpty를 구현했다.

void Enqueue(Queue *queue, home_t* p){
	home_t *now = (home_t *)malloc(sizeof(home_t)); //노드 생성
	now->index = p->index;//데이터 설정
	strcpy(now->city, p->city);
	now->post = p->post;
	now->link = NULL;

	if (IsEmpty(queue)) {//큐가 비어있을 때
		queue->front = now;//맨 앞을 now로 설정       
	}
	else {//비어있지 않을 때
		queue->rear->link = now;//맨 뒤의 다음을 now로 설정
	}
	queue->rear = now;//맨 뒤를 now로 설정   
	queue->count++;//보관 개수를 1 증가
}

Queue에서 삽입 연산은 Enqueue라고 한다고 합니다... 머 암튼

얘도 일단 노드를 삽입하니까! 동적할당으로 노드 공간을 마련해주고, 데이터 설정을 한다.

그리고 큐가 비어있는지 확인하고, 비어있다면 맨앞=맨뒤=지금넣는노드 이므로! 맨 앞을 새로 삽입한 노드로 설정하고, 비어있지 않다면 맨 뒤 노드가 가리키는 다음 노드에다가 새로 삽입하는 노드를 추가한다.

그다음 현재 큐를 가리키는 구조체의 마지막 노드를 가리키는 포인터를 새로 삽입하는 노드로 설정하고, count 값을 증가한다.

int Dequeue(Queue *queue){
	int re = 0;
	home_t *now;
	if (IsEmpty(queue)){//큐가 비었을 때
		return re;
	}
	now = queue->front;//맨 앞의 노드를 now에 기억
	re = now->index;//반환할 값은 now의 인덱스로 설정
	queue->front = now->link;//맨 앞은 now의 다음 노드로 설정
	free(now);//now 소멸
	queue->count--;//보관 개수를 1 감소
	return re;
}

그다음 큐에서 값을 끄내는 Dequeue

비어있다면! 삭제할 필요가 없다

비어있지 않다면은 삭제는 맨 앞 노드를 해야한다. 따라서 이제 큐의 맨 앞을 가리키는 포인터는 맨 앞 노드의 다음 노드를 가리키도록 하고, 맨 앞 노드를 free 해준다. 그리고 count까지 1 감소시키면 끝!

 

여기까지 일단 linked list를 이용한 스택과 큐 구현이다..!

https://github.com/kongbiji/Linked_list

kongbiji/Linked_list

전체 소스코드는 여기 있고, 사실 소스코드 안에 보면 큐랑 스택말고도 그냥 linked list에서의 삽입, 삭제, 검색 연산도 구현하였다. 나머지 애들은 다음에 리뷰하도록~