[ C언어 ] 자료구조_큐(연결 리스트_LinkedList)

1. 큐 자료구조 설명

큐는 선입선출(FIFO) 구조로 스택은 마지막에 들어온 데이터를 먼저 내보내지만 큐는 들어온 순서대로 내보내는 자료구조입니다.

 

일상생활에서는 대기줄과 동일한 구조로 흔히 은행에서 들어온 순서대로 번호표를 제공하고 순서대로 일을 처리하게 되죠 이때 시스템에서 큐 를 사용하여 관리를 하는 것이죠

 

2. 큐 자료구조 구현(연결 리스트)

연결 리스트를 사용해서 큐를 구현하는 방법은 스택과 비슷합니다.

노드를 삽입하고 삭제할 때 앞뒤 순서만 다를 뿐이기 때문에 이전에 포스팅한 연결리스트(LinkedList)를 구현한 코드를 사용해서 구현하겠습니다.

[ C언어 ] 자료구조_LinkedList

만약 연결 리스트 LinkedList 를 모르시는 분은 위 블로그 URL로 들어가서 글을 봐주시기 바랍니다. 이미 알고 계시지만 코드가 없는 분들도 위 블로그에 코드를 만들어 놓았으니 복사해 주시기 바랍니다.

 

그럼 본격적으로 큐Queue 를 구현해 보겠습니다.

큐는 위에서 설명드렸다 싶히 데이터를 추가할 때는 앞에서 꺼낼 때는 뒤에서 이루어지기 때문에 LinkedList 를 구현할 때 만들어 놓은 init(), add(), remove_front(), get() 함수 를 사용해서 구현할 수 있습니다.

 

실제 코드를 통해 살펴보겠습니다.

 

Queue_LinkedList.h

typedef struct Queue Queue;

Queue* createQueue();
void destroyQueue(Queue* q);

void enqueue(Queue* q, int data);
int dequeue(Queue* q);
int isEmpty(Queue* q);

 

 

 

Queue_LinkedList.c

#include <stdlib.h>
#include "Queue_LinkedList.h"
#include "LinkedList.h"

struct Queue {
    LinkedList list;
};

Queue* createQueue() {
    Queue* q = malloc(sizeof(Queue));
    if (q == NULL) return NULL;
    init(&q->list);
    return q;
}

void destroyQueue(Queue* q) {
    while (size(&q->list) > 0) remove_front(&q->list);
    free(q);
}

void enqueue(Queue* q, int data) {
    add(&q->list, data);
}

int dequeue(Queue* q) {
    element data = get(&q->list, 0);
    remove_front(&q->list);
    return data;
}

int isEmpty(Queue* q) {
    return size(&q->list) == 0;
}

 

createQueue() 함수를 사용해서 동적으로 Queue 구조체 메모리를 생성합니다.

메모리가 정상적으로 생성 됐는지 확인을 한 다음 해당 메모리가 가지고 있는 LinkedList의 값을 초기화시켜서 사용할 수 있도록 만들어 주고 해당 메모리의 주소값을 반환합니다.

 

enqueue() 함수에서는 add() 함수를 사용해서 데이터를 앞에서 추가시켜 주고

dequeue() 함수에서는 뒤에 있는 값을 변수에 저장 후 remove_front()를 사용해서 메모리를 해제해 준 뒤 변수에 저장해 놓은 값을 반환해 줍니다.

 

main.c

#include <stdio.h>
#include "Queue_LinkedList.h"

void main()
{

	Queue* queue = createQueue();

	enqueue(queue, 1);
	enqueue(queue, 4);
	enqueue(queue, 2);
	enqueue(queue, 3);

	printf("%d ", dequeue(queue));
	printf("%d ", dequeue(queue));
	printf("%d ", dequeue(queue));
	printf("%d ", dequeue(queue));

	destroyQueue(queue);
    
	return 0;
}

 

실행결과

 

실제로 정상적으로 코드가 동작이 됩니다.

이상으로 이번에는 큐 자료구조를 간단하게 알아보고 이전에 만들어 놓은 LinkedList를 사용해서 큐를 구현 해 보았습니다.

 

저의 블로그를 봐주셔서 감사드립니다.