연결 리스트로 구현한 큐

연결된 큐 (linked queue)

배열로 구현된 큐에 비해 코드가 약간 더 복잡해지고 메모리 공간을 더 사용하지만 크기가 제한되지 않는 장점이 있으며, 인덱스로 쓰이던 정수 rear, front 는 포인터로 사용된다.

C

소스코드

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct QueueNode {
    element item;
    struct QueueNode* link;
} QueueNode;

typedef struct {
    QueueNode *rear, *front;
} QueueType;

void init(QueueType* q) {
    q->front = NULL;
    q->rear = NULL;
}

int is_empty(QueueType* q) {
    /* 
    rear, front 두 포인터 중
    첫 요소를 가리키는 front 만
    NULL 임을 확인하면 된다.
    */
    return (q->front == NULL);
}

void enqueue(QueueType* q, element item) {
    QueueNode* temp = (QueueNode *)malloc(sizeof(QueueNode));
    if (temp == NULL) {
        printf("메모리 할당 오류\n");
    }
    else {
        temp->item = item;
        temp->link = NULL;
        if (is_empty(q)) {
            q->front = temp;
            q->rear = temp;
        }
        else {
            q->rear->link = temp;
            q->rear = temp;
        }
    }
}

element dequeue(QueueType* q) {
    QueueNode* temp = q->front;
    element item;

    if (is_empty(q)) {
        printf("큐 공백 에러");
    }
    else {
        item = temp->item;
        q->front = temp->link;

        /*
        마지막으로 남은 노드를 삭제했다면
        rear 도 역시 NULL 을 가리키게끔 함.
        */
        if (q->front == NULL) {
            q->rear = NULL;
        }

        free(temp);
        return item;
    }
}

element peek(QueueType* q) {
    if (is_empty(q)) {
        printf("큐 공백 에러");
    }
    else {
        return q->front->item;
    }
}

int main() {
    QueueType q;
    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    return 0;
}

출력

dequeue()=1
dequeue()=2
dequeue()=3

Python

소스코드

class Node():
    def __init__(self, item):
        self.item = item
        self.link = None

class Queue():
    def __init__(self):
        self.front = None
        self.rear = None

    def is_empty(self):
        return self.front == None

    def enqueue(self, item):
        temp = Node(item)
        if self.is_empty():
            self.front = temp
            self.rear = temp
        else:
             self.rear.link = temp
             self.rear = temp

    def dequeue(self):
        temp = self.front
        if self.is_empty():
            print("큐 공백 에러")
        else:
            item = temp.item
            self.front = temp.link

            if self.front == None:
                self.rear = None

            return item

    def peek(self):
        if self.is_empty():
            print("큐 공백 에러")
        else:
             return self.front.item

if __name__ == "__main__":
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    print("dequeue()={0}".format(q.dequeue()))
    print("dequeue()={0}".format(q.dequeue()))
    print("dequeue()={0}".format(q.dequeue()))
    print("dequeue()={0}".format(q.peek()))

출력

dequeue()=1
dequeue()=2
dequeue()=3
dequeue()=4