큐 (연결리스트로 구현)

연결리스트로 큐를 구현하므로 크기에 제약이 없어 큐가 꽉 찼는지 검사할 필요가 없으므로 full() 함수가 필요가 없다. 큐의 기본적인 설명은 '선형 큐 (구조체로 구현)'에서 설명했으므로 생략하겠다. 원형 큐는 선형 큐를 보완한 형태지만, 여전히 배열 때문에 크기에 제약을 받는 단점을 보인다. 연결리스트로 구현한 큐는 이러한 단점을 없애서 큐를 구현할 수 있는 가장 효율적인 방법이라고 볼 수 있다. 구현 #include #include #include typedef struct Node //노드 정의 { int data; struct Node *next; }Node; typedef struct Queue //Queue 구조체 정의 { Node *front; //맨 앞(꺼낼 위치) Node *rear; ..

원형 큐 (구조체로 구현)

원형 큐의 기본 설명은 '원형 큐 (배열로 구현)'에서 이미 했으므로 생략하겠다. 바로 구조체로 구현한 원형 큐의 동작 상태를 볼 수 있는 코드로 넘어가겠다. 원형 큐 구현 #include #include #include #define MAX 5 typedef struct Queue { int queue[MAX]; int front, rear; }Queue; void init_queue(Queue* q) { q->front = q->rear = 0; //front, rear 0으로 초기화 } int empty(Queue* q) { return (q->front == q->rear); } int full(Queue* q) { return (q->front == ((q->rear+1)%MAX)); } voi..

원형 큐 (배열로 구현)

원형 큐 기본 설명 선형 큐의 단점을 되새겨 보면 dequeue() 함수를 실행함으로서 발생하는 사용할 수 없는 공간들이 생겼었다. 즉 그 공간들을 재활용할 수 있는 코드를 구현하지 않는 이상 메모리 누수가 생긴 것이다. 그래서 이런 단점을 보완한 것이 원형 큐이다. 이를 구현한 방법은 예시로 enqueue() 함수를 보이겠다. void enqueue(int data){ if(full()) { printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n"); return; } else { rear = (rear+1)%MAX; queue[rear]=data; } } 위의 함수를 보면 큐가 포화상태가 아닐 시, rear은 rear+1의 MAX로 나눈 나머지 값이 대입된다. dequeue() 함수도 이와..

선형 큐 (배열로 구현)

선형 큐의 기본 설명은 '선형 큐 (구조체로 구현)' 글에서 설명을 했으므로 생략하겠다. 단순 배열로 큐의 동작 상태를 보기 위해 구현한 코드를 바로 보이겠다. 선형 큐의 동작 상태 코드 #include #include #define MAX 5 int front; int rear; int data[MAX]; // 선형 큐 초기화 void init_queue() { rear = -1; front = -1; } // 선형 큐 상태 출력 void queue_print() { for (int i = 0; i

선형 큐 (구조체로 구현)

선형 큐 기본 설명 우선은 큐가 동작하는 모습을 이해하기 위한 코드의 설명을 하고 마지막에 스택을 구현했을 때처럼 직접 입력하는 코드는 따로 보이겠다. 밑의 그림을 보면 큐의 초기 상태는 front와 rear가 둘 다 -1에 있을 때다. 큐는 스택과 달리 먼저 들어온 것이 먼저 나가는 형태다. (FIFO, first in first out) 선형 큐의 동작 원리의 이해를 돕기 위해 몇 가지 동작을 해보겠다. 기본 코드는 다음과 같이 설정한다. #include #include #define MAX 5 typedef struct Queue{ int front; int rear; int data[MAX]; } Queue; [-1] [0] [1] [2] [3] [4] front, rear (NULL) (NULL..