Queue
선입 선출의 자료구조 (First In First Out, FIFO)
- 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트이다.
- 먼저 들어오는 데이터가 먼저 나가게 된다.
EnQueue는 데이터 삽입 작동이며, DeQueue는 데이터 추출 작동이라고 한다.
Queue 코드
class Queue():
def __init__(self):
self.queue = []
self.index = 0
self.length = 0
def ft_push(self, X): #데이터 삽입, enQueue
self.queue.append(X)
self.length += 1
def ft_pop(self): #데이터 추출, deQueue
if self.length - self.index < 1:
print(-1)
else:
print(self.queue[self.index])
self.index += 1
def ft_size(self):
print(self.length - self.index)
def ft_empty(self):
if self.length - self.index < 1:
print(1)
else:
print(0)
def ft_front(self):
if self.length - self.index < 1:
print(-1)
else:
print(self.queue[self.index])
def ft_back(self):
if self.length - self.index < 1:
print(-1)
else:
print(self.queue[self.length - 1])- 큐의 size를 정해둔 경우, ft_pop을 사용할때 index가 하나씩 뒤로 밀리게 되고, 큐의 범위가 줄어들면서, 큐의 재사용또한 불가능하게 된다.
ft_push()
- 큐에 데이터를 넣는 역할을 한다.
- length 가 증가하며 배열에 데이터를 append 한다.
ft_pop()
- 큐에서 데이터를 빼는 역할을 한다.
- length가 줄어들며 맨 앞에서 데이터를 없에고 return 하기 때문에 index가 늘어난다.
- length - index는 큐의 실제 데이터가 있는 길이이다.
Queue의 문제점, 해결책
문제점
배열의 크기를 정해둔 경우, 삽입 및 삭제 반복 시 index가 마지막 인덱스를 가르키기 때문에, 큐의 앞 부분을 재 사용할 수 없다.
해결책
이는 실제 데이터는 시간 복잡도 때문에 앞으로 이동시키지 않지만, 인덱스는 증가하므로 일어난 문제이다.
그래서 생겨난 아이디어가 원형 큐 이다. 배열을 사용하면서, 앞 과 뒤가 원형처럼 이어져 있다고 가정한다.
