인하대 윤정희 교수님 문제해결을 위한 자료구조와 알고리듬_큐와 덱(예습)

---

큐(Queue)

선입선출(FIFO, First-In First-Out)의 자료구조. 
가장 먼저 들어온 데이터가 가장 먼저 나감.

매표소 줄서기와 같다고 보면 됨

활용

컴퓨터의 **버퍼(buffer)**로 사용
(CPU와 주변 장치 간 데이터 처리 속도 차이를 조정).

코딩 구조:
데이터 삽입(enqueue): 큐의 끝에서 추가.
데이터 삭제(dequeue): 큐의 앞에서 제거.
참조(peek): 가장 앞에 있는 데이터를 확인.

구현 방법

---

선형 큐: 

배열을 이용해 구현.
문제점: 데이터 삭제 후에도 빈 공간이 유지되어 비효율적.

코딩 예시

class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        self.items.append(item)  # Rear(끝)에 데이터 추가
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)  # Front(앞)에서 데이터 삭제
        return "Queue is empty!"
    
    def peek(self):
        if not self.is_empty():
            return self.items[0]  # Front의 데이터 반환
        return "Queue is empty!"
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# 테스트
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.peek())     # 2
print(q.size())     # 2

 

---

원형 큐

배열을 원형으로 간주하여 빈 공간 활용.
Front와 Rear 포인터를 회전시키는 구조.
응용: **링 버퍼(Ring Buffer)**로 사용
 오래된 데이터를 삭제하고 최신 데이터만 유지.

코딩 예시

 

---

덱(Deque, Double-Ended Queue)

개념: 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐.
특징:
스택과 큐의 연산을 모두 포함.
**전단(front)**과 **후단(rear)**에서 삽입 및 삭제 가능.
연산:
addFront: 전단에 삽입.
addRear: 후단에 삽입.
deleteFront: 전단에서 삭제.
deleteRear: 후단에서 삭제.
구조적 유사성:
원형 큐를 상속하여 구현 가능.
기존 큐 연산에 새로운 연산(deleteRear, addFront)을 추가 구현.
파이썬에서 큐와 덱 구현
queue 모듈:
Queue 클래스: 기본적인 큐 연산 제공.
collections 모듈:
deque 클래스: 덱 구현에 적합, 큐와 스택 연산 모두 지원.

코딩 예시

from collections import deque

# 덱 생성
dq = deque()

# 삽입
dq.append(1)       # Rear에 추가
dq.appendleft(2)   # Front에 추가

# 삭제
print(dq.pop())    # Rear에서 삭제 (1 출력)
print(dq.popleft()) # Front에서 삭제 (2 출력)

# 현재 덱 상태
dq.extend([3, 4, 5])         # Rear에 여러 값 추가
dq.extendleft([0, -1, -2])   # Front에 여러 값 추가
print(list(dq))  # [-2, -1, 0, 3, 4, 5]

# 연산
print(dq[0])  # Front의 값 (-2)
print(dq[-1]) # Rear의 값 (5)