[자료구조] 큐 (Queue) - 배열로 구현 (C, Python)

🖥️ 들어가며

---

큐 (Queue) 는 선입선출 (First In First Out) 구조입니다. 가장 대표적인 예시로는 식당에서 줄 서는 상황이라 할 수 있을 것입니다.

큐는 다양한 애플리케이션에서 매우 중요한 역할을 합니다. 예를 들어, 운영체제에서는 프로세스 관리를 위해 작업들을 큐에 넣고, 네트워크 시스템에서는 데이터 패킷의 전송을 위해 큐를 사용하여 데이터의 순서를 유지합니다.

또한 프린터의 작업 대기열, 웹 서버의 요청 처리 등 실생활에서도 큐의 원리를 적용한 시스템을 쉽게 찾아볼 수 있습니다.

 

큐는 여러 가지 방식으로 구현될 수 있습니다.

가장 기본적인 형태는 선형 큐(Linear Queue)이며, 이외에도 순환 큐(Circular Queue), 우선순위 큐(Priority Queue), 덱(Deque) 등이 있습니다.

이 포스팅에서는 선형 큐 를 집중적으로 포스팅합니다.

 

💡 순서 흐름

---

큐에는 Front 와 Rear 라는 개념이 존재합니다.

• Front : 먼저 들어간 데이터의 위치를 나타냅니다.
• Rear : 마지막에 들어간 데이터의 위치를 나타냅니다.

아래는 데이터가 삽입되고 삭제되는 과정을 간략히 그린 그림입니다.

 

💡 구현

---

구현해야 할 함수는 다음과 같습니다.

• enqueue() : 데이터 삽입
• dequeue() : 데이터 삭제, 반환
• isEmpty(), isFull() : 큐가 가득 찼는지, 아닌지 판정
  물론 enqueue 와 dequeue 에서 자체적으로 구현해도 무방합니다.
• display() : 큐에 어떤 데이터가 있는지 출력

 

🔍 isEmpty(), isFull()

---

• isEmpty()
• 초기 상태라면 Front 와 Rear 가 모두 -1 로 초기화되어 있습니다. 또한 위의 그림에서 Front 가 Rear 보다 크면 되지도 않을 뿐더러 비어있다고 할 수 있습니다.
• isFull()
• Rear 가 SIZE - 1 과 같으면 큐가 모두 찼다고 할 수 있습니다.

📌 C

// isEmpty()
if (front == -1 || front > rear) {
    printf("Queue underflow\n");
    return -1; // 반환 값 변경: 언더플로우 시 예외 값을 반환
}

// isFull()
if (rear == SIZE - 1) { 
    printf("Queue overflow\n");
} 

📌 Python

파이썬에서는 리스트를 동적으로 관리하므로 isFull() 이 필요가 없습니다.

# isEmpty()
if not self.queue:
    print("Queue underflow")
    return None

 

🔍 enqueue()

---

큐는 초기에 Front 와 Rear 가 모두 -1로 초기화되어 있습니다.

따라서 맨 처음 삽입이라면, Front = 0 연산도 추가로 수행해주어야 합니다.

📌 C

void enqueue(int n) {
    if (rear == SIZE - 1) {
        printf("Queue overflow\n");
    } else { 
        if (front == -1) {
            front = 0;
        }
        queue[++rear] = n;
    }
}

📌 Python

def enqueue(self, n):
    self.queue.append(n)

 

🔍 dequeue()

---

Front 를 1 증가시켜 데이터가 하나 빠져나갔다는 것을 기록한 다음, 빠져나간 데이터를 반환합니다.

📌 C

int dequeue() {
    if (front == -1 || front > rear) { // isEmpty()
        printf("Queue underflow\n");
        return -1; // 반환 값 변경: 언더플로우 시 예외 값을 반환
    } else {
        int dequeuedElement = queue[front++];
        if (front > rear) { // 모든 요소가 제거된 후 초기화
            front = rear = -1;
        }

        return dequeuedElement;
    }
}

📌 Python

def dequeue(self):
    if not self.queue:
        print("Queue underflow")
        return None
    return self.queue.pop(0)

 

🔍 display()

---

배열의 크기만큼 순회하면서 출력하면 됩니다.

📌 C

void printQueue() {
    if (front == -1) {
        printf("Queue is empty\n");
    } else {
        for (int i = front; i <= rear; ++i) {
            printf("%d\n", queue[i]);
        }
    }
    printf("\n");
}

📌 Python

def __str__(self):
    if not self.queue:
        return "Queue is empty"
    return "\n".join(map(str, self.queue)) + "\n"

def __iter__(self):
    return iter(self.queue)

 

C 코드 전문

---

#include <stdio.h>

#define SIZE 100

int queue[SIZE];
int rear = -1;
int front = -1;

void enqueue(int n) {
    if (rear == SIZE - 1) { // isFull()
        printf("Queue overflow\n");
    } else { // 초기 상태라면
        if (front == -1) {
            front = 0;
        }
        queue[++rear] = n;
    }
}

int dequeue() {
    if (front == -1 || front > rear) { // isEmpty()
        printf("Queue underflow\n");
        return -1; // 반환 값 변경: 언더플로우 시 예외 값을 반환
    } else {
        int dequeuedElement = queue[front++];
        if (front > rear) { // 모든 요소가 제거된 후 초기화
            front = rear = -1;
        }

        return dequeuedElement;
    }
}

void printQueue() {
    if (front == -1) {
        printf("Queue is empty\n");
    } else {
        for (int i = front; i <= rear; ++i) {
            printf("%d\n", queue[i]);
        }
    }
    printf("\n");
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    enqueue(4);
    enqueue(5);

    printQueue();

    dequeue();
    dequeue();

    printQueue();

    return 0;
}

 

Python 코드 전문

---

class Queue:
    def __init__(self):
        self.queue = []

    def __str__(self):
        if not self.queue:
            return "Queue is empty"
        return "\n".join(map(str, self.queue)) + "\n"

    def __iter__(self):
        return iter(self.queue)

    def enqueue(self, n):
        self.queue.append(n)

    def dequeue(self):
        if not self.queue:
            print("Queue underflow")
            return None
        return self.queue.pop(0)

if __name__ == "__main__":
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)

    print(q)  # str 메소드 소출

    q.dequeue()
    q.dequeue()

    print(q)

    # 큐를 반복할 수 있습니다.
    for item in q:
        print(f"요소 : {item}")