1. 큐를 복습해보자
이른 아침부터 아이유 콘서트 입장을 대기하던 사람이
콘서트장에 가장 먼저 입장해야 한다.
First In, First out
다른 예시로,
창고에서 유통기한이 임박한 순서대로 재료들을(눈에 보이는 쪽으로)배치시켜야 한다. 유통기한이 임박한 것일수록 먼저 납품된 것이니깐!
군생활 역시 그러하다. 먼저 입대한 사람이 먼저 나와야 한다. 너무 와 닿는다.
2. 큐 설계
(물론,
from queue import Queue 정의 및 queue = Queue() 선언을 통해
큐 object를 바로 사용할 수 있다.
직접 코드를 보지않고, 원리를 통해 혼자 만들어 봤다.
(개념만 이해한 상태로 혼자 고민하여 코드를 작성하는 과정이 재밌기 때문이다.
그 후에, 사람들이 만든 코드를 바라보는 재미가 있다.)
1) 데이터 push
2) 데이터 delete
3) 데이터 show
3. 코드
class Queue: # 큐 클래스 정의하는 부분
def __init__(self):
self.item_list = []
# 이 부분까지 stack 자료구조와 동일하다.
def push(self, data):
self.item_list.append(data)
def delete(self):
# 리스트가 텅 비어있을땐 return
if not self.item_list:
return
else:
# 방법1.
# self.item_list.reverse()
# first_data = self.item_list.pop()
# self.item_list.reverse()
# return first_data
# 방법2.
result = self.item_list[0]
self.item_list.remove(self.item_list[0])
return result
# 방법3. 내장 클래스 큐 사용시
# another way
#return self.item_list.get()
def show(self):
print(self.item_list)
# 큐 선언
queue = Queue()
# 큐에 데이터 입력 (물론 반복문을 통해 넣어도 된다.)
queue.push(5) # queue.item_list = [5]
queue.push(10) # queue.item_list = [5, 10]
queue.push(7) # queue.item_list = [5, 10, 7]
queue.push(89) # queue.item_list = [5, 10, 7, 89]
queue.push(4) # queue.item_list = [5, 10, 7, 89, 4 ]
queue.push(123) # queue.item_list = [5, 10, 7, 89, 4, 123 ]
# 입력된 데이터를 보기
print(f'pushed data result')
queue.show() # queue.item_list
# 데이터 추출 시작(FIFO)
print(f'pop bigins')
for i in range(len(queue.item_list)):
data = queue.delete()
print(data)4. 코드 설명
데이터를 pop하는 부분을 좀 더 보자.
방법1은 아래와 같다.
self.item_list.reverse()
first_data = self.item_list.pop()
self.item_list.reverse()
return first_data데이터가 입력된 순서를 우선 reverse시킨다.(역방향으로 정렬)
ex) [12, 4, -90, 3, 66] -> [66, 3, -90, 4, 12]
그렇게 되면 맨 마지막에 넣은 데이터가 맨 앞으로 가게 된다. (66)
이때, pop을 통해 맨 처음 데이터를 추출 및 삭제한다.
그 다음 다시, reverse 메소드를 통해 데이터를 원상태로 복귀시킨다.
[12, 4, -90, 3]
리스트 배열을 원상태로 복구시킨 이유는
데이터 delete 후 사용자가 다시 데이터 push를 할 수도 있기 때문이다.
방법2는 아래와 같다.
result = self.item_list[0]
self.item_list.remove(self.item_list[0])
return result데이터가 append를 통해 계속해서 늘어나든 말든,
item_list[0]이라는 맨 처음 데이터만 삭제한다.
즉, 0번째 인덱스 데이터만 계속 remove 시킨다.
물론 delete 메소드 정의 안에 item_list가 empty 일때는 바로 return되도록 했다.
첫 번째 방법보다 코드가 더 간결할 뿐만 아니라, 직관적이며 좀 더 효율적이라고 생각한다.
reverse 메소드는 아무래도 반복문으로 작성되었을 것이기 때문이다.
if not self.item_list: return
방법3은 아래와 같다.
return self.item_list.get()from queue import Queue를 활용한 것으로
get()메소드를 통해 맨 처음의 데이터를 추출 및 삭제해준다.
5. 큐에 대한 단상
큐 역시 굉장히 친숙한 개념이다.
계산대, 편의점, 정류장 등에서의 줄서기 문화 말이다.
어제 배운 '스택'과 오늘 배운 '큐'는 '리스트'를 기본적인 뼈대로 사용한다.
- sizable한 리스트(리스트 길이가 가변적)이며,
- linear하다.(선형적이다.)
스택도 그렇고 큐 역시, 데이터 set이 많다면 비효율적이다.
먼저 입력된 데이터를 먼저 사용해야할 프로그램엔 '큐'를,
먼저 입력된 데이터를 나중에 사용해야할 프로그램엔 '스택'을 사용한다.
자료구조라는 것이 궁극적으로는 설계하는 프로그램에 최적화하는 것이 중요하다고 생각한다.'
'메모리는 적게', '검색은 빠르게'가 모두가 추구하는 목표이자 이상향이라고 생각한다.
그런 면에서 큐는 저장할 데이터가 증가할수록, 메모리 할당의 부담이 있다.
게다가,
내가 찾고자 하는 데이터를 검색하는데 최악의 경우
그게 가장 마지막에 넣은 데이터일 수도 있다.
즉, 빅오는 n인 된다. O(n)
