큐란?
- 큐는 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태인 선형구조
큐 ADT
- 데이터: 선입선출(FIFO)의 접근 방법을 유지하는 항목들의 모음
- 연산
- Queue(): 비어 있는 새로운 큐를 만듦
- isEmpty(): 큐가 비어있는지를 검사
- enqueue(x): 항목 x를 큐의 맨 뒤에 추가
- dequeue(): 큐의 맨 앞에 있는 항목을 꺼내 반환
- peek(): 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환
- size(): 큐의 모든 항목들의 개수를 반환
- clear(): 큐를 공백상태로 만듦
큐의 구현 방법
- 원형 큐 이용 → 선형 큐는 비효율적(enqueue(item) 연산: O(1), dequeue()연산: O(n))
- 원형 큐
- 배열을 원형으로 사용
- 리스트의 크기 고정
- 전단과 후단을 위한 2개의 변수(front: 첫번째 요소 하나 앞의 인덱스, rear: 마지막 요소의 인덱스)
- 삽입: rear를 하나 증가 → 그 위치에 항목 삽입: O(1)
- 삭제: front를 하나 증가 → 그 위치 항목을 삭제: O(1)
- 변수증가: front = (front+1) % MAX_QSIZE, rear = (rear+1) % MAX_QSIZE
- 공백상태: front == rear
- 포화상태: front == (rear+1) % MAX_QSIZE
원형 큐의 시간 복잡도
- enqueue(x) 연산: O(1)
- dequeue() 연산: O(1)
원형 큐 구현
MAX_QSIZE = 10 # 원형 큐의 크기
class CircularQueue:
def __init__(self): # 생성자
self.front = 0 # 큐의 전단 위치
self.rear = 0 # 큐의 후단 위치
self.items = [None] * MAX_QSIZE # 항목 저장용 리스트
def isEmpty(self): # 공백상태면 True, 아니면 False 반환
return self.front == self.rear
def isFull(self): # 포화상태면 True, 아니면 False 반환
return self.front == (self.rear + 1) % MAX_QSIZE
def clear(self): # 큐를 공백상태로 초기화
self.front = self.rear
def enqueue(self, item): # 후단에 item을 추가
if not self.isFull(): # 포화상태가 아니면
self.rear = (self.rear + 1) % MAX_QSIZE # 후단 증가
self.items[self.rear] = item # 후단 위치에 삽입
def dequeue(self): # 전단의 항목을 꺼내(실제로 꺼내지 않음) 반환
if not self.isEmpty(): # 공백상태가 아니면
self.front = (self.front + 1) % MAX_QSIZE # 전단 증가(꺼내는 과정)
return self.items[self.front] # 전단 위치의 항목 반환
def peek(self): # 전단의 항목을 꺼내지 않고 반환
if not self.isEmpty(): # 공백상태가 아니면
return self.items[(self.front + 1) % MAX_QSIZE] # 전단 위치의 항목 반환
def size(self): # 큐의 크기 반환
return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
def display(self): # 큐의 항목을 전단부터 출력
out = []
if self.front < self.rear: # 전단 < 후단
out = self.items[self.front+1:self.rear+1]
else:
out = self.items[self.front+1:MAX_QSIZE] + \
self.items[0:self.rear+1]
print("f={},r={} ==> {}".format(self.front, self.rear, out))
덱이란?
- 덱은 스택이나 큐보다는 입출력이 자유로운 자료구조
- 전단과 후단에서 삽입과 삭제가 모두 가능한 선형구조
덱 ADT
- 데이터: 전단과 후단을 통한 접근을 허용하는 항목들의 모음
- 연산
- Deque(): 비어 있는 새로운 덱을 만듦
- isEmpty(): 덱의 공백상태를 검사
- addFront(x): 항목 x를 덱의 맨 앞에 추가
- deleteFront(): 덱의 맨 앞에 있는 항목을 꺼내 반환
- getFront(): 덱의 맨 앞에 있는 항목을 삭제하지 않고 반환
- addRear(x): 항목 x를 덱의 맨 뒤에 추가
- deleteRear(): 덱의 맨 뒤에 있는 항목을 꺼내 반환
- getRear(): 덱의 맨 뒤에 있는 항목을 삭제하지 않고 반환
- isFull(): 덱의 포화상태를 검사
- size(): 덱의 모든 항목들의 개수를 반환
- clear(): 덱을 공백상태로 만듦
원형 큐의 구현 방법
- 원형 덱 이용 → 효율적, 시간 복잡도: O(1)
- 원형 덱
- 원형 큐 + 새로운 기능(addFront(), deleteRear(), getRear())
- addFront(), deleteRear() → 반시계 방향 회전(변수감소)
- 변수감소: front = (front-1+MAX_QSIZE) % MAX_QSIZE, rear = (rear-1+MAX_QSIZE) % MAX_QSIZE
원형 덱의 시간 복잡도
- addFront(x) 연산: O(1)
- deleteFront() 연산: O(1)
- addRear(x) 연산: O(1)
- deleteRear() 연산: O(1)
원형 덱 구현
from CircularQueue import * # 원형 큐 모듈 가져옴
class CircularDeque(CircularQueue): # 원형 큐 상속
def __init__(self): # 생성자
super().__init__() # 부모 클래스의 생성자를 호출
def addRear(self, item): # 원형 큐의 enqueue와 동일한 연산
self.enqueue(item)
def deleteFront(self): # 원형 큐의 dequeue와 동일한 연산
return self.dequeue()
def getFront(self): # 원형 큐의 peek와 동일한 연산
return self.peek()
def addFront(self, item): # 새로운 기능: 전단 삽입
if not self.isFull(): # 포화상태가 아니면
self.items[self.front] = item # 항목 저장
# 반시계 방향으로 회전, 전단 감소
self.front = (self.front-1+MAX_QSIZE) % MAX_QSIZE
def deleteRear(self): # 새로운 기능: 후단 삭제
if not self.isEmpty(): # 공백상태가 아니면
item = self.items[self.rear]
# 반시계 방향으로 회전, 후단 감소(꺼내는 과정)
self.rear = (self.rear-1+MAX_QSIZE) % MAX_QSIZE
return item
def getRear(self): # 새로운 기능: 후단 peek
if not self.isEmpty(): # 공백상태가 아니면
return self.items[self.rear]
