큐(Queue) 자료구조란? (C언어, Java, Python 예시코드)

큐(Queue)

 

 

(1) 큐(Queue) 자료구조란?

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식으로 동작하는 데이터 구조입니다. 이러한 특성 때문에 대기열, 작업 스케줄링, 메시지 처리 등 다양한 응용 분야에서 활용됩니다.

 

(2) 큐의 기본 동작

큐의 구조

1. 삽입(Enqueue): 큐의 끝(Rear)에 데이터를 추가.(예를들어 50을 큐에 추가할 경우 40에 위치한 rear를 한칸 오른쪽으로 밀고 그 칸에 추가)
2. 삭제(Dequeue): 큐의 앞(Front)에서 데이터를 제거.(현재 front가 위치한 10을 빼내고 deque 후 front는 20을 가리킴)
3. 보기(Peek): 큐의 앞에 있는 데이터를 제거하지 않고 확인.(단순히 현재 front가 가리키고 있는 값이 뭔지만 확인)

 

(3) 큐의 주요 특징

• 선입선출(FIFO): 먼저 삽입된 데이터가 먼저 제거됩니다.
• 단방향 흐름: 데이터는 Rear에서 들어오고 Front에서 나갑니다.
• 구현 방식: 배열 또는 연결 리스트로 구현 가능하며, 구현 방식에 따라 성능 차이가 있습니다.

 

(참고) 큐의 종류

1. 일반 큐: 기본적인 FIFO로 동작하는 큐
2. 원형 큐(Circular Queue): Rear가 끝에 도달하면 다시 처음으로 연결.(사용할 수 있는 메모리에 제한이 있는 경우 사용)
3. 우선순위 큐(Priority Queue): 데이터의 우선순위에 따라 처리 순서 결정. 일반적으로 Heap으로 구현함.
4. 이중 끝 큐(Deque): 양쪽 끝에서 삽입과 삭제가 가능.

반응형

---

(4)큐 구현 예시

C언어로 구현한 큐

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

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

void enqueue(int data) {
    if (rear == SIZE - 1) {
        printf("Queue is full!\n");
        return;
    }
    if (front == -1) front = 0;
    queue[++rear] = data;
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty!\n");
        return -1;
    }
    return queue[front++];
}

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

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    printf("Dequeued: %d\n", dequeue());
    display();
    return 0;
}

 

 

Java로 구현한 큐

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(10);
        queue.add(20);
        queue.add(30);
        System.out.println("Queue: " + queue);

        int removed = queue.poll();
        System.out.println("Dequeued: " + removed);
        System.out.println("Queue after dequeue: " + queue);

        int front = queue.peek();
        System.out.println("Front element: " + front);
    }
}

 

 

Python으로 구현한 큐

from collections import deque

queue = deque()

queue.append(10)
queue.append(20)
queue.append(30)
print("Queue:", list(queue))

removed = queue.popleft()
print("Dequeued:", removed)
print("Queue after dequeue:", list(queue))

front = queue[0]
print("Front element:", front)

---

(5) 큐의 활용 사례

1. 운영체제의 작업 스케줄링: 프로세스 대기열 관리.
2. 프린터 대기열: 요청된 인쇄 작업을 순서대로 처리.
3. 네트워크 패킷 처리: 데이터를 순서대로 처리.
4. BFS(너비 우선 탐색): 그래프 탐색에서 사용.

큐는 간단하지만 강력한 자료구조로, 프로그래밍에서 다양한 문제를 해결하는 데 중요한 역할을 합니다.