목차
🎈 목차
1). Queue란 무엇인가??(간단한 구조 &개념)
2). Queue 구현 설명 - "Queue.h"
3). Queue 구현 설명 - "Queue.c"
4). Queue 구현 설명 - "Queue main.c"
🎆 1). Queue란 무엇인가??(간단한 구조 &개념)
1. Queue란 ??
나의 블로그에 정리한 Stack의 개념
=> gogo !!! 링크텍스트
🎇 2). Queue 구현 설명 - "Queue.h"
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <crtdbg.h>
typedef int element;
typedef struct node /*노드 구조체*/
{
element data; /*데이터 영역 : element(int 형) 데이터 저장*/
struct node* next; /*포인터 영역*/
} NODE;
typedef struct queue /*Queue 관리 구조체*/
{
NODE* begin; /*begin pointer(begin node 가리킴) */
size_t size; /*연결 리스트의 크기 - 실제 data node의 개수*/
} QUEUE;
void q_construct(QUEUE**); /*큐 초기화*/
void q_destruct(QUEUE**); /*큐 소멸자 */
bool q_empty(QUEUE*); /*큐가 비었는지 확인 */
size_t q_size(QUEUE*); /*큐 size 보이도록 나타냄*/
void q_push(QUEUE*, element); /*스택에 원소 삽입*/
element q_pop(QUEUE*); /*스택에 원소 삭제*/
void q_clear(QUEUE*); /*스택을 초기화*/
- <stdio.h>=>Standard Input/Output library (표준입출력 라이브러리),
- <stdlib.h>=>stdlib.h는 C 언어의 표준 라이브러리로, 문자열 변환, 사 난수 생성, 동적 메모리 관리 등의 함수들을 포함하고 있다.
- <stdbool.h> => standard boolean이라는 뜻으로 ,표준 Bool형을 정의하기 위한 헤더파일이다.
- <string.h>=>문자열 처리를 위한 헤더 파일
- <crtdbg.h>=>메모리 누수 탐지 기능을 탑재한 헤더 파일로 프로그램의 malloc이나 free와 같은 메모리 할당 해제가 여기에 정의된 함수를 이용하여 메모리를 추적 할 수 있다.
**그리고 타입 재정의 개념 링크 => Go Go
//https://sciphy.tistory.com/893
** 😎 => 큐의 include 한것은 그전 Linkedlist의 헤더 파일과 동일하며, 노드 구조체와 Queue구조체와 각 함수들은 약간 다르다(주석 참고)
✨ 3). Queue 구현 설명 - "Queue.c"
#include "Queue.h"
/*-----------------------------------------------------------------------------------------
Function name : q_construct - 큐 생성 및 초기화
Parameters : *queue - *queue 구조체의 주소
------------------------------------------------------------------------------------------*/
void q_construct(QUEUE **queue)
{
*queue = (QUEUE*)malloc(sizeof(QUEUE)); /*큐 생성*/
if (*queue != NULL) /*큐 생성에 성공했을경우*/
{
(*queue)->begin = (NODE*)malloc(sizeof(NODE)); /*큐 begin을 동적할당*/
(*queue)->size = 0; /*size=0으로 초기화*/
if ((*queue)->begin != NULL) /*큐 begin 생성에 성공 했을경우*/
{
(*queue)->begin->next = (NODE*)malloc(sizeof(NODE)); /*begin 다음 노드에 생성*/
(*queue)->begin->data = 0; /*begin 데이터 값 0으로 초기화*/
if ((*queue)->begin->next != NULL) /*begin 다음 노드 생성에 성공했을경우*/
{
(*queue)->begin->next->next = NULL; /*begin 다음 다음 노드가 가리키는 곳을 null로 초기화*/
}
}
}
}
/*-----------------------------------------------------------------------------------------
Function name : q_destruct - 큐 소멸자
Parameters : *queue - *queue 구조체의 주소
------------------------------------------------------------------------------------------*/
void q_destruct(QUEUE** queue)
{
if (*queue != NULL) /*큐 생성에 성공한경우*/
{
for (NODE* now = (*queue)->begin; now != NULL; free((*queue)->begin)) /*begin을 가리키는 now 노드가 null을 가리킬 때 동안 노드를 free 시켜주기*/
{
(*queue)->begin = now;
now = now->next;
}
free(*queue); //큐 free 시켜주기
*queue = NULL;// 큐 null로 지정
}
}
/*-----------------------------------------------------------------------------------------
Function name : q_empty- 큐가 비었는지 확인
Parameters : queue - queue 관리 구조체의 주소
Return : queue->size= 0
------------------------------------------------------------------------------------------*/
bool q_empty(QUEUE* queue)
{
return queue->size == 0; // 큐 size 0으로 리턴
}
/*-----------------------------------------------------------------------------------------
Function name : q_size - 큐 사이즈 확인
Parameters : queue - queue 관리 구조체의 주소
Return : queue->size
------------------------------------------------------------------------------------------*/
size_t q_size(QUEUE* queue)
{
return queue->size; // 큐 size 리턴
}
/*-----------------------------------------------------------------------------------------
Function name : q_push - 큐에 원소 삽입
Parameters : queue - queue 관리구조체의 주소
: data - queue 노드 데이터
------------------------------------------------------------------------------------------*/
void q_push(QUEUE* queue, element data)
{
NODE* node = (NODE*)malloc(sizeof(NODE)); /*노드 생성*/
if (node != NULL) /*노드생성 성공시 */
{
node->data = data; /*노드에 데이터 삽입*/
node->next = queue->begin->next; /*노드의 다음노드를 가리키는것을 queue->begin->next가 가리켜준 곳으로 설정*/
queue->begin->next = node; /*queue->begin->next는 노드를 가리키게 설정*/
}
queue->size++; /*queue->size 증가*/
}
/*-----------------------------------------------------------------------------------------
Function name : q_pop - 큐에 원소 삭제
Parameters : queue - queue 구조체의 주소
Return : result
------------------------------------------------------------------------------------------*/
element q_pop(QUEUE* queue)
{
NODE* now = queue->begin; /*now 노드를 queue->begin으로 설정*/
for (NODE* temp = now->next; temp->next->next != NULL;) /*now->next를 가리키는 temp가 temp 다음 다음을 가리킬때 NULL일경우까지 옮겨준다.*/
{
now = now->next; //now 노드 이동
temp = temp->next; // temp 노드 이동
}
element result = now->next->data; /*now 다음 노드의 데이터를 result로 이동시켜주기*/
NODE* temp = now->next->next; /*temp는 now 노드의 다음 다음을 가리키도록 설정*/
free(now->next); /*now 다음을 free(시켜주기)*/
now->next = temp; /*now 다음을 temp 로 설정*/
queue->size--; /*queue->size 감소*/
return result; /*result 반환*/
}
/*-----------------------------------------------------------------------------------------
Function name : q_clear - 큐의 모든 원소 삭제
Parameters : queue - queue 관리 구조체의 주소
------------------------------------------------------------------------------------------*/
void q_clear(QUEUE* queue)
{
for (; !q_empty(queue); q_pop(queue));
}
=> 위의 파일은 주석에 설명이 포함 되어 있음.
🎉 4). Stack 구현 설명 - "Queue main.c"
#include "Queue.h"
// main source code
void queue_test()
{
QUEUE* queue = NULL;
q_construct(&queue);
q_push(queue, 1);
q_push(queue, 2);
q_push(queue, 3);
q_push(queue, 4);
printf("%d\n", q_pop(queue));
printf("%d\n", q_pop(queue));
printf("%d\n", q_pop(queue));
q_push(queue, 1);
q_push(queue, 2);
q_push(queue, 3);
q_push(queue, 4);
printf("%d\n", q_pop(queue));
printf("%d\n", q_pop(queue));
printf("%d\n", q_pop(queue));
printf("%d\n", q_pop(queue));
printf("%d\n", q_pop(queue));
q_destruct(&queue);
printf("\n\nCHECK\n\n");
}
int main()
{
_CrtDumpMemoryLeaks();
}