<게시물 내부링크>
자료구조 Queue(큐)에 대한 이해
Queue motivation 큐를 배워야 하는 이유
큐는 한번에 하나의 정보를 입력하거나 출력할 수 있는 자료구조에요.
저장할때에는 제일 뒷부분에 저장하고, 출력할때에는 맨 앞의 정보를 출력해요.
큐의 구조와 동작을 이해하면
컴퓨터 및 프로그래밍 언어의 실행구조에 관한 이해에도 도움이 되어요.
자바스크립트는 비동기(Asynchronous) 함수를 실행하면,
그 함수의 종료를 알리는 콜백을 테스크 큐라는곳에 저장한답니다.
거기에서 태스크(작업)들은 자신의 차례를 기다리게 됩니다.
이벤트 루프가 콜백이 저장된 큐를 확인하고,
콜스택의 작업이 비어있으면 콜백함수를 콜스택으로 옮겨서 실행하게 하지요.
또 컴퓨터 프로세스의 스케줄링에도 작업 큐 라는 구조가 이용된답니다.
서비스 쪽을 생각해볼까요?
게임매칭을 기다리는것을 큐돌린다, 큐잡고있다 라고 말하곤해요.
큐에 줄을 선다는 뜻이 있기도 하지만
실제로 대기하는 유저정보를 큐에 저장하는 경우가 많아요.
그래서 큐는 차례대로 일을 처리해야하는 푸시서비스에서도 이용 된답니다.
큐도 스택과 같이 매우 잘 명명된 자료구조에요.
그래서 영단어 Queue를 이해하는것만으로도 큐의 구조와 동작을 이해할 수 있어요.
영단어 Queue의 뜻
큐는 자신의 차례를 기다리는 사람이나 작업의 줄을 말해요.
컴퓨터의 자료구조 큐도 마찬가지랍니다.
우리가 은행에서 업무를 보려고 번호표를 뽑아 기다리거나,
카페에서 커피한잔을 주문한후 대기할때를 생각해봅시다.
Q1: 이렇게 업무를 위해 자신의 차례를 기다릴때, 어떤 순서로 줄을 설까요?
A1: 먼저 도착한 순서대로 줄을 섭니다. 즉, 새로 도착한 사람은 줄의 맨 뒤에 섭니다.
Q2: 그렇다면 누구부터 일을 볼수있을까요?
A2: 특별한 사안이 없다면 먼저 줄을 선 사람부터 일을 봅니다.
이렇게 줄서기의 규칙을 다 이해하셨나요?
축하합니다! queue의 구조와 동작을 완전히 이해 하셨어요.
Queue의 처리순서
큐는 먼저 들어온것이 (First in) 먼저 처리되어요 (First out)
이러한 순서로 정보를 처리하는것을 FIFO 구조라고 부릅니다.
Queue의 동작: enque와 deque
큐를 구현하는데에도 스택처럼 필수 메서드 두개만 가지고있으면 충분합니다.
줄에 새로운 데이터가 삽입되는 enqueue
먼저 들어와 대기하던 데이터가 방출되는dequeue가 필요하죠.
Queue 개념 요약: FIFO, enqueue, dequeue
큐는 자료를 저장하는 데이터구조로써, 순서대로 처리되어야하는 작업의 정보를 저장하는데 쓰인다.
먼저들어온 정보가 먼저나가는 FIFO (First In First Out)구조를 가지고있다.
큐에는 정보를 맨 뒤에 삽입하는 enqueue, 맨 먼저 들어온 데이터를 방출하는 dequeue 메서드가 있다.
파이썬으로 구현한 Queue의 특징
저는 파이썬의 리스트 자료구조로 큐를 만들었어요.
dequeue를 delete연산자로 리스트의 0번 성분을 삭제하는 식으로 구현했죠.
이를 한번 실행하면 모든인덱스의 아이템들이 앞으로 한칸씩 이동하게 됩니다.
그런데 여기에는 필요이상으로 정보를 많이 이동시킨다는 단점이 있어요.
빅오 표기법으로 O(n)만큼의 시간복잡도가 걸려요.
만약 deque나 다른구조를 이용한다면 O(1)의 시간복잡도로 일을 처리할수 있답니다.
원래 포인터를 사용하는 언어에서는 각 포인터가 가르키는 자료의 주소를 한칸씩 당기는 방식으로
실제로 저장된 데이터의 주소를 옮기지는 않아요.
하지만 파이썬의 리스트를 사용한다면 실제로 데이터가 저장된 주소를 옮긴답니다.
Queue 코드
class MyQueue:
def __init__(self, input_queue: list = None):
if input_queue is None:
self._queue = []
else:
self._queue = input_queue
def enqueue(self, value):
"""
큐에 새로운 정보를 집어넣는 메서드입니다.
list.append를 사용해 리스트의 맨 뒤에 정보를 저장합니다.
"""
target = value
self._queue.append(target)
print(f"'{target}' is enqueued")
def dequeue(self):
"""
큐에 삽입된 정보를 출력하는 메서드입니다.
0번 아이템을 삭제하는 방식입니다.
만약 큐가 비어있다면 이를 알리는 메시지를 출력합니다.
:return:
"""
if len(self._queue) > 0:
target = self._queue[0]
del self._queue[0]
print(f"`{target}` is dequeued")
return target
else:
print("this queue is empty")
def is_empty(self):
"""
큐가 비어있는지 확인하는 메서드입니다.
만약 큐가 비어있지 않다면
큐를 보여줍니다.
"""
if len(self._queue) == 0:
print("queue is empty")
else:
target = self._queue
print(f"queue has datas like : '{target}' ")
Queue 인스턴스 만들어보기
## ["a", "b", "c"]가 들어있는 큐 자료구조를 만듭니다.
test_queue = MyQueue(["a", "b", "c"])
## 큐를 출력합니다.
test_queue.is_empty()
#출력결과: queue has datas like : '['a', 'b', 'c']'
## 큐의 성분 하나를 출력합니다.
test_queue.dequeue()
#출력결과: `a` is dequeued
## 큐를 출력합니다
test_queue.is_empty()
#출력결과: queue has datas like : '['b', 'c']'
# 앞의 성분이 출력된것을 알 수 있습니다.
## 큐에 새로운 원소 "d"를 집어넣습니다.
test_queue.enqueue("d")
#출력결과: 'd' is enqueued
## 큐를 출력합니다
test_queue.is_empty()
#출력결과: queue has datas like : '['b', 'c', 'd']
# 뒤에 성분이 입력된것을 확인할 수 있습니다.
읽어주셔서 감사합니다.
오류나 오탈자를 발견하시면 댓글로 알려주세요.
'it공부 (개념) > 자료구조와 알고리즘 그리고 파이썬' 카테고리의 다른 글
| 스택(stack)자료구조: 스택은 책더미와 같다. / 파이썬 리스트로 구현해 보기. /push, pop, dynamic array (1) | 2023.03.12 |
|---|---|
| 파이썬 자료구조(data structure)의 속성. sequence. mutable (0) | 2023.01.01 |