[데이터 구조와 활용] 큐

1. 큐

 (1) 큐(Queue)란?

  - First in First Out 선입 선출 구조를 따르는 선형 데이터 구조임

  - 먼저 추가된 원소가 먼저 제거되는 구조를 가짐

  - 양쪽 끝이 열려있는 구조로 한쪽에서 삽입(enqueue 또는 push)되고 반대쪽에서 삭제(dequeue 혹은 pop)됨

  - 큐의 주요 연산

연산	설명	시간복잡도
enqueue(x), push(x) = queue.append()	큐의 맨 뒤에 원소 x 추가	O(1)
dequeue(), pop() = queue.popleft()	큐의 맨 앞 원소 제거 및 반환	O(1)
front() = queue[0]	큐의 맨 앞 원소 확인(제거안함)	O(1)
back() = queue[-1]	큐의 맨 뒤 원소 확인(제거 안함)	O(1)
is_empty() = len(queue)	큐가 비어있는지 확인	O(1)

 - 큐의 활용 사례 : 

   운영 체제의 작업 스케줄링, 프린터 작업 대기열, 네트워크 패킷 처리, 너비 우선 탐색

2. 큐 구현

 (1) 파이썬을 활용한 큐 구현

queue = [] queue.append(10) queue.append(20) queue.append(30) queue.append(40) print(queue) pop_item = queue.pop(0) print(pop_item) print(queue)

 * 문제점 : pop(0)을 호출하면 리스트의 첫 번째 원소가 제거되면서 나머지 원소들이 한 칸씩 이동해야 하므로 O(n)이 소요됨

 (2) pop으로 지우지 않고 front 변수를 이용하여 인덱스만 내보내는 형식 사용

queue = [] front = 0 queue.append(10) queue.append(20) queue.append(30) queue.append(40) print(queue) print(queue[front]) # pop 대신 인덱스 증가 front += 1 print(queue[front]) # is_empty 연산 = 큐가 비어있는지 확인 print(len(queue) -front == 0)

  * 시간 복잡도 분석

  - push(x) = 파이썬 리스트의 append() 연산은 스스로의 끝에 원소를 추가하기 때문에 O(1) 소요

  - pop(i) = front 변수를 증가시키는 방식은 데이터는 그대로 두고 인덱스만 변경해 데이터를 이동시키지 않으므로 O(1) 소요

  - is_empty() = 길이 확인 후 -연산으로 O(1)

  - front = 인덱스 접근 O(1)

  * 하지만 front 변수가 계속 증가하면 리스트 크기가 불필요하게 커질 수 있음

(3) 순환 큐 (circle Queue) 방식 사용

size = 5 queue = [None] * size front, rear = 0, 0 queue[rear] = 10 rear = (rear + 1) % size queue[rear] = 20 rear = (rear + 1) % size print(queue) queue[front] = None front = ( front + 1) % size print(queue)

 - 배열 기반 큐에서 메모리를 효율적으로 사용하고 인덱스 조정으로 out 시간도 효율적으로 사용하기 위해 사용

 - 순환 큐는 front, rear로 인덱스를 조정하여 리스트의 처음과 끝이 연결된 것 처럼 동작

 - 파이썬에서는 직접 구현하기보다 collections.deque를 사용함

 - 리스트를 사용한 순환 큐 규현 : 순환 큐는 배열의 크기를 초과하지 않으면서 원소를 효율적으로 추가 제거 가능 

3. 큐 활용

 - collections.deque 활용 = 상위 연산 모두 시간복잡도 O(1)로 구현됨

 - 리스트는 동적 배열 기반으로 제거 O(n) 소요되지만 deque는 연결 리스트 기반으로 구현되어 맨 앞의 데이터도 빠르게 제거 가능

 (1) BOJ18258

import collections import sys input = sys.stdin.readline q = collections.deque() n = int(input()) for _ in range(n) :     a = list(input().split())     if a[0] == "push" :         q.append(int(a[1]))     elif a[0] == "front" :         if len(q) == 0 :             print(-1)         else :              print(q[0])     elif a[0] == "back" :         if len(q) == 0 :             print(-1)         else :              print(q[-1])     elif a[0] == "size" :         print(len(q))     elif a[0] == "empty" :         print(int(len(q) == 0))     elif a[0] == "pop" :         if len(q) == 0 :             print(-1)         else :              mid = q.popleft()             print(mid)     else :         break

 (2) BOJ26042

import collections import sys input = sys.stdin.readline n = int(input()) q = collections.deque() m, s = 0, 100000 for _ in range(n):     data = list(map(int, input().split()))     if data[0] == 1 :         q.append(data[1])         if m < len(q) :             m = len(q)             s = data[1]         elif m == len(q) :             s = min(s, data[1])     elif data[0] == 2:         q.popleft() print(m ,s)

 (3) BOJ2161

import collections import sys input = sys.stdin.readline n = int(input()) q = collections.deque() for i in range(1, n+1) :     q.append(i) while len(q) != 0 :     print(q.popleft(), sep=' ', end=' ')     if len(q) == 0 :         break     a = q.popleft()     q.append(a)