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