카테고리 없음

[DataScience Computing] Linear Data Structure 4 - Queue

정희명 2024. 4. 20. 18:38

1️⃣ Que

 

데이터를 선입선출(FIFO, First-In-First-Out) 방식으로 관리한다. 말 그대로 첫 번째, 데이터가 첫 번째로 나가는 구조를 의미한다. 큐는 일상 생활에서 흔히 볼 수 있는 줄 서기와 비슷한 방식으로 작동되며, 여러 종류의 컴퓨팅 작업에서 효율적인 데이터 관리를 위해 사용됩니다.

 

 

 

2️⃣ 큐의 연산 종류

  • Enqueue : 큐의 뒤쪽에 새로운 데이터를 추가한다.
  • Dequeue : 큐의 앞쪽에서 데이터를 제거하고 그 값을 반환한다.
  • Peek / Front : 큐의 맨 앞에 있는 데이터를 제거하고 그 값을 반환한다.
  • IsEmpty : 큐가 비어있는지 확인한다.
  • Size : 큐에 저장된 데이터의 개수를 반환한다.

 

 

3️⃣ 큐의 구현 방법

1. 배열기반 큐

  • 배열을 사용하여 데이터를 저장한다.
  • Enqueue는 배열의 끝에 데이터를 추가하는 것이 일반적이며, Dequeue는 배열의 첫 번째 요소를 제거하고 모든 요소를 한 칸씩 앞으로 이동시킨다.
  • 이러한 구현은 Dequeue 연산에서 비효율적일 수 있으므로, 보다 효율적인 관리를 위해 원형 큐(Circular Queue)를 사용하기도 한다.

 

2. 연결 리스트 기반 큐

  • 연결 리스트를 사용하여 데이터를 저장한다
  • 이 구조에서는 노드의 'next' 포인터가 다음 노드를 가르키도록 하여 큐를 구현한다.
  • Enqueue는 리스트의 끝에 새 노드를 추가하고, Dequeue는 리스트의 첫 노드를 제거함으로써 수행된다.
  • 각 연산은 일반적으로 O(1)의 시간 복잡도를 가진다.

 

3️⃣ Que의 활용 예

큐는 다양한 어플리케이션에서 활용된다. 예를 들어 운영체제에서는 프로세스 관리를 위해 작업을 큐에 넣고 처리한다. 네트워킹에서는 패킷을 전송할 때 큐를 사용하여 순서대로 전송한다. 또한, 데이터 스트림의 버퍼링, 콜 센터의 고객 서비스 대기열, 프린트 작업 대기열 등 많은 시스템에서 큐를 기본적으로 사용한다.

 

 

4️⃣ Python 코드 예제 : Que의 큐의 구현

  • 파이썬에서는 큐를 배열 기반 리스트나 'collections' 모듈의 'deque'를 사용하여 구현할 수 있다. 여기서는 'deque'를 사용하여 큐의 구현 방법을 알아보도록 하자.
from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)  # 큐의 끝에 아이템 추가
        print(f"Enqueued: {item}")

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty, cannot dequeue.")
            return None
        return self.queue.popleft()  # 큐의 앞에서 아이템 제거

    def front(self):
        if self.is_empty():
            print("Queue is empty, no front item.")
            return None
        return self.queue[0]  # 큐의 맨 앞 아이템 반환

    def is_empty(self):
        return len(self.queue) == 0  # 큐가 비어 있는지 확인

    def size(self):
        return len(self.queue)  # 큐의 크기 반환

# 큐 인스턴스 생성
q = Queue()

# 데이터를 큐에 추가
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

# 큐에서 데이터를 하나 제거
print("Dequeued:", q.dequeue())

# 큐의 맨 앞 데이터 조회
print("Front item:", q.front())

# 큐의 현재 크기 출력
print("Queue size:", q.size())

 

  1. 큐 클래스의 초기화
    • 'Queue' 클래스는 내부적으로 'deque'를 사용하여 데이터를 저장한다. 
    • 'Deque'는 양방향 큐를 구현하고 있으며, 'append'와 'popleft' 메소드를 사용하여 효율적으로 데이터를 관리합니다.
  2. 데이터 추가 : enqueue
    •  'enqueue' 메소드는 'deque'의 'append' 함수를 사용하여 큐의 끝에 데이터를 추가한다. 이 연산은 O(1) 시간 복잡도를 가지므로 매우 효율적이다.
  3. 데이터 제거 : dequeue
    • 'dequeue' 메소드는 'deque'의 'append' 함수를 사용하여 큐의 끝에 데이터를 추가한다. 이 연산은 O(1) 시간 복잡도를 가지므로 매우 효율적이다.
  4. 맨 앞 데이터 조회 : front
    • 'front' 메소드는 큐의 가장 앞에 있는 데이터를 조회합니다. 큐가 비어 있지 않다면 인덱스 0의 요소를 반환한다. 데이터를 제거하지 않고단순 조회만 하므로, 이 역시 O(1) 시간 복잡도입니다.
  5. 큐가 비었는지 확인 : is_empty
    • is_empty 메소드는 큐의 길이가 0인지 확인한다. 이 메소드는 큐의 상태를 확인할 때 유용하게 사용된다. 
  6. 큐의 크기 반환 : size
    • size 메소드는 큐에 저장된 아이템의 개수를 반환한다. 큐의 현재 상태를 확인할 때 유용하다.