6/21(수) IT 자료구조(7일차) / 8. 큐(Queue)

8. 큐(Queue)

큐(Queue)는 데이터의 삽입과 삭제가 각각 다른 끝에서 이루어지는 선형 자료구조임.

큐는 데이터가 들어온 순서대로 처리되는 선입선출(First-In-First-Out, FIFO) 구조를 가지고 있음.

큐는 일상 생활에서 줄을 서는 것을 생각하면 이해하기 쉬움.

가장 먼저 온 사람이 가장 먼저 처리되는 것과 같은 원리임.

큐는 주로 "enqueue"와 "dequeue"라는 두 가지 기본 연산을 지원함.

"enqueue" 연산은 큐의 뒤쪽에 원소를 추가하는 작업을 의미하며,

"dequeue" 연산은 큐의 앞쪽에 있는 원소를 제거하고 반환하는 작업을 의미함.

큐에서 데이터를 확인하는 연산으로는 "front" 또는 "peek"이 있을 수 있음.

큐는 다양한 응용 분야에서 사용됨.

예를 들어, 작업 스케줄링, 메시지 큐, 네트워크 패킷 처리, 버퍼 등에서 큐가 활용됨.

또한, 그래프 알고리즘인 너비 우선 탐색(BFS)에서도 큐가 사용되어 가까운 정점부터 탐색하는 데 활용됨.

8-1. ADT(Abstract Data Type)

큐(Queue)의 ADT는 큐의 동작과 속성을 기술한 것이며,

실제로는 배열, 연결리스트, 원형 버퍼 등 다양한 방식으로 구현될 수 있음.

ADT는 사용자에게 추상적인 인터페이스를 제공하여 큐를 사용할 수 있게 하고,

구체적인 구현 방식은 구현자에게 달려있음.
큐는 다양한 응용 분야에서 유용하게 사용될 수 있으며, 대기열 관리, 작업 스케줄링, 네트워크 버퍼 등에 사용됨.

Enqueue(item): 큐의 뒤쪽에 새로운 항목(item)을 추가.
Dequeue(): 큐의 앞쪽에 있는 항목을 제거하고 반환.
Front(): 큐의 앞쪽에 있는 항목을 반환하지만 제거하지는 않음.
IsEmpty(): 큐가 비어 있는지 여부를 확인.
Size(): 큐에 저장된 항목의 수를 반환.

8-2. 구현: 배열

배열을 이용한 큐 구현:

인덱스를 사용하여 요소의 추가와 제거를 효율적으로 관리할 수 있으나,

배열의 크기가 고정되어 있기 때문에 큐의 최대 용량을 넘어서는 요소를 추가할 수 없는 한계가 있음.

요소 삭제 후 배열의 앞쪽으로 이동하는 연산이 필요하므로, 요소를 삭제할 때마다 배열의 이동이 필요함.

이로 인해 큐의 dequeue 연산이 시간 복잡도 O(N)이 될 수 있음.

시간 복잡도 O(N):
알고리즘이 입력 크기 N에 대해 수행하는 연산의 시간이 선형적으로 증가하는 경우를 나타내는 표기법.

시간 복잡도는 알고리즘의 실행 시간이 입력 크기에 어떻게 의존하는지를 나타내며,
O(N)은 입력 크기에 비례하여 선형적으로 증가한다는 의미.
예를 들어, 입력 크기 N의 리스트에서 모든 항목을 확인하는 경우, 이 알고리즘의 시간 복잡도는 O(N)임.
이는 입력 크기에 비례하여 연산 횟수가 증가하기 때문임.

8-2-1. 의사 코드

1) 필수요소
queue = [ ] : 큐의 원소들을 저장할 리스트(배열)

2) 메서드
.enquene() : 맨 끝에 원소를 추가

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

.dequeue() : 맨 앞의 원소를 삭제

def dequeue(self):
return self.queue.pop(0)

.front() : 맨 앞의 원소를 알려줌

def front(self):
return self.queue[0]

.rear() : 맨 뒤의 원소를 알려줌

def rear(self):
return self.queue[-1]

.is_empty() : 큐가 비었는 지 확인

def is_empty(self):
return len(self.queue) == 0

.dequeue_all() : 큐 비우기

def dequeue_all(self):
self.queue = []

8-2-2. 실제 코드

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

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

  def dequeue(self):
    return self.queue.pop(0)

  def front(self):
    if self.is_empty():
      return None
    else:
      return self.queue[0]

  def rear(self):
    if self.is_empty():
      return None
    else:
      return self.queue[-1]

  def is_empty(self) -> bool:
    return len(self.queue) == 0

  def dequeue_all(self):
    self.queue.clear()

  def print_queue(self):
    print('큐 처음부터 시작 : ', end = '\n[\n')
    for i in range(len(self.queue)):
      print(self.queue[i], end = '\n')
    print(']')
    print()