큐(Queue)란?
스택의 경우에는 나중에 들어온 데이터가 먼저 나가는 구조였다.
하지만 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO : First In First Out)구조이다.
매표소에서 표를 끊는다고 생각해보자. 당연히 먼저 와서 줄을 선 사람이 먼저 표를 받고 자리를 떠날 수 있다. 만약 뒤에 온 사람이 먼저 표를 받는다면 먼저 온 사람이 몹시 화가 나는 상황이 발생할 것이다. 따라서 매표소 시스템을 구현하려면 큐를 사용해야 할 것이다.
큐의 기본 구조
큐의 기본 구조를 알아보자.
큐의 앞 부분을 전단(front), 뒷 부분을 후단(rear)라고 한다. 데이터의 이동 방향은 화살표 친 것과 같다.
그림으로 큐 이해하기
큐에서 필요한 연산들
create(max_size): 최대 크기가 max_size인 공백 큐를 생성한다.init(q): 큐를 초기화 한다.is_empty(q): 큐가 비어있는지 확인한다is_full(q): 큐가 가득 찼는지 확인한다enqueue(q, e): q의 끝에 e를 추가한다.dequeue(q): q의 맨 앞에 있는 e를 제거하여 반환한다peek(q): q의 맨 앞에 있는 e를 읽어서 반환한다
파이썬 리스트로 큐 구현
class Queue(object):
def __init__(self):
self.queue = []
def is_empty(self):
if len(self.queue) == 0:
return True
else:
return False
def dequeue(self):
if self.is_empty():
return -1
return self.queue.pop(0)
def enqueue(self, n):
self.queue.append(n)
pass
def printQueue(self):
print(self.queue)
q = Queue()
q.enqueue(3)
q.printQueue()
q.enqueue(7)
q.printQueue()
q.enqueue(5)
q.printQueue()
q.dequeue()
q.printQueue()
q.dequeue()
q.printQueue()
원형 큐
원형큐의 이해
앞서 배운 큐를 선형 큐라고 한다.
선형큐의 경우 enqueue의 시간복잡도가 O(1)이지만 dequeue의 경우에는 시간복잡도가 O(n)이다. 삭제할 때는 첫번째 요소를 삭제하므로 뒤에 있는 값들을 다 한칸씩 앞으로 당겨야 하기 때문이다.
이 문제는 배열을 선형으로 생각하지 말고 원형으로 생각하면 쉽게 해결된다.
즉, front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다.
그림으로 살펴보자.
초기 상태에서는 front(빨간색)와 rear(파란색)가 모두 0이다.
삽입할 때마다 rear가 1씩 증가한 뒤 증가된 위치에 새로운 데이터가 삽입된다.
삭제할 때는 front가 1 증가된 다음, 증가된 위치의 데이터를 삭제한다.
원형 큐에서는 front와 rear값이 같으면 큐가 비어있음을 알 수 있다.
원형큐에서는 하나의 자리는 항상 비워둔다. 포화 상태와 공백 상태를 구분하기 위해서이다.
따라서 front가 rear보다 하나 앞에 있으면 포화 상태가 된다.
* 만약 요소들의 개수를 저장하고 있는 추가적인 변수 count 변수를 사용할 거라면 한 자리를 비워두지 않아도 무방하다.
원형큐 파이썬 구현
원형큐의 구현에 있어서 중요한 것은 front와 rear를 원형으로 회전시켜야 한다는 것이다.
이는 나머지 연산자 %를 이용하여 쉽게 구현할 수 있다.
1. 원형큐 클래스 생성, 초기화
front와 rear를 모두 0으로 둔다.
class CircleQueue:
MAX_SIZE = 8 # 큐의 최대 사이즈
def __init__(self):
self.rear = 0
self.front = 0
self.queue = [0 for i in range(self.MAX_SIZE)]
2. 비어있는지 확인 (front == rear인지)
def is_empty(self):
if self.rear == self.front:
return True
return False
3. 가득 찼는지 확인
front보다 rear가 한칸 뒤에 있는지
def is_full(self):
if (self.rear + 1) % self.MAX_SIZE == self.front:
return True
return False
4. 데이터 삽입
rear를 한 칸 뒤로 이동한 후, 그 위치에 삽입하는 것임.
def enqueue(self, item):
if self.is_full():
return
self.rear = (self.rear+1)%(self.MAX_SIZE)
self.queue[self.rear] = item
5. 데이터 삭제
front를 한 칸 뒤로 이동한 후, 그 위치의 값을 삭제
def dequeue(self):
if self.is_empty():
return
self.front = (self.front + 1) % self.MAX_SIZE
return self.queue[self.front]
전체 코드
class CircleQueue:
MAX_SIZE = 8 # 큐의 최대 사이즈
def __init__(self):
self.rear = 0
self.front = 0
self.queue = [0 for i in range(self.MAX_SIZE)]
def is_empty(self):
if self.rear == self.front:
return True
return False
def is_full(self):
if (self.rear + 1) % self.MAX_SIZE == self.front:
return True
return False
def enqueue(self, item):
if self.is_full():
return
self.rear = (self.rear+1)%(self.MAX_SIZE)
self.queue[self.rear] = item
def dequeue(self):
if self.is_empty():
return
self.front = (self.front + 1) % self.MAX_SIZE
return self.queue[self.front]
