오늘은 큐(Queue)에 대해 알아볼 것이다.
큐를 한 문장으로 표현하자면 First In First Out이다. 즉, 선입선출이다.
비유를 해주자면 음식점에 사람이 많으면 줄을서서 그 음식점에 들어가는 것이다.
그림으로 표현하면 위와같은 이미지로 생각하면 된다.
큐를 이해하려면 큐의 구조와 용어를 알아야한다.
먼저 용어는
- enQueue(인큐) - 데이터 삽입
- deQueue(데큐) - 데이터 추출
- front(머리) - 첫 번째 데이터
- rear(꼬리) - 마지막 데이터
큐는 위의 이미지와 같은 구조를 가지고있다. 이 구조를 계속 생각하며 큐를 이해하려고하면 더욱 편하다.
먼저 가장 기본적인 큐의 구조는
이미지와 같다. -1,0,1,2,3 은 인덱스 번호이다.
- enQueue삽입
위의 이미지같은 구조에서 삽임을 하려면 rear를 0번으로 옮기고 데이터를 넣어줘야한다.
이렇게 rear를 -1에서 0으로 옮겨주고 데이터를 삽입하면
이런 이미지처럼 된다.
rear를 쉽게 말하면 마지막 데이터를 가리키고있다.
- deQueue추출
반대로 추출은 front가 움직인다고 생각하면 편하다.
front를 -1에서 0으로 옮겨주고 데이터를 추출한다.
그럼 다음과 같은 구조가 나온다.
- 큐가 꽉 찼을 때
이렇게 큐가 다 찼다면 rear는 가장 끝을 가리키고 있을 것이다. 계속 삽입해서 꽉 찼을 때
즉
rear == SIZE-1 이다. 여기서 SIZE는 큐의 크기를 말한다. 총4칸이니 SIZE는 4이다.
하지만 여기선 함정이있는데 뒤에서 설명해주겠다.
- 큐가 비었을 때
!!! 여기서 front와rear의 위치가 같다면 큐가 비어있단 뜻이다.
계속 추출해서 front가 rear와 같은 값을 가리킬 때.
- 데이터를 확인할 때
마지막은 데이터를 확인할 때이다.
front +1을 가리켜서 다음에 추출될 데이터를 확인할 수 있다.
그럼 이제 코드를 짜고 직접 설명하며 해보겠다.
함수구현이다.
첫 번째 함수부터 설명하면
def isQueueFull() 은 함수이다.
여기서 def는 define의 줄임말로 파이썬에서 함수를 선언할때 사용하는 키워드이다. is QueueFull은 함수명이다.
함수 선언 후 글로벌뒤에 붙는건 변수이다
이건 만약 rear가 SIZE-1과 같지 않다면 False를 출력하라는 뜻이다. 여기서 !=는 같지 않다 라는 뜻이다.
rear가 SIZE -1 과 같고 front가 -1이라면 True를 출력해라. == 꽉찼다는 뜻.
도식화해보면 이러한 상태이다.
이 함수는
이런 상황일때를 대비해 둔 함수이다.
단순하게, rear랑 SIZE-1 이 같을때 다 찼다고 하면 큐의 앞쪽이 비어있는 상황에도 다 찼다고할 것이다. 그래서 다음과 같은 코드를 짜준것이다.
먼저 for문을 설명하면 for 변수 in range(시작,끝) 이다. 즉, 시작과 끝이 같아지면 끝난다.
위의 코드를 도식화로 설명하면
이런 구조일때, SIZE=4 이고 front+1=2 가된다.
그럼 i에 들어갈 변수는 2,3이 나온다.
대입해보면
queue[1] = queue[2]
queue[2] = None 은
이렇게 되고 다음 변수인 3을 넣으면
다음과 같이 나온다. 이제
를 적용하면
다음과 같은 상태가 된다.
참고로 elif 와 else 의 차이를말하자면 elif 는 조건문 2같은거다. if에서 실패하면 elif로 넘어가고 또 elif가 있다면 두 번째 elif가 실패하면 세번째 elif로 넘어가는거다. 모든 elif까지 다 실패했을때 else가 작동된다.
코드를 읽는법을 알았다면
빠르게 설명해보겠다.
isQueueEmpty 는 아까 위에서 설명했듯이 front와rear가 같을때 비어있다는 얘기이다.
enQueue는 삽입로 isQueueFull로 큐가 다 찼다면 큐가 다 꽉찼다는걸 출력해주고 그게 아니라면 rear+=1 꼬리를 한칸 오른쪽으로 넘겨주고 그 자리에 queue[rear]=data 데이터를 삽입한다.
deQueue는 추출로 삽입과 비슷한 원리로 돌아간다.
peek은 확인하는것으로 isQueueEmpty로 큐가 비어있는지 확인한 후 비어있지않다면 front+1로 다음 추출할 데이터를 출력해 확인이 가능하다.
다음은 메인코드 부분이다
이 코드들은 쉽게 말해서 위의 함수들을 사용할 수 있게만드는 조작키 설정같은 느낌이다.
이렇게 코드를 구현하고 실행해보면
다음과 같이 출력되는걸 볼 수 있다.