Queue는 새로운 요소가 한쪽 끝(뒤쪽)에 추가되고 다른 쪽 끝(앞쪽)에서 제거됩니다. FIFO(First In First Out)구조라고 할 수 있습니다.
고속도로 톨게이트를 차가 통과하는 상황을 생각해볼까요? 차를 잠시 정차했다가 통행증을 뽑아가야하는 상황입니다. 이때 톨게이트를 통과하는 순서는 먼저 온 차량 순이죠. Queue의 EnQue(Add)와 DeQue(Delete)의 동작과 유사하다고 볼 수 있습니다.
Queue에 대한 개념 설명을 넘어 상세한 구현 논리에 대해 설명해보겠습니다.
배열로 구현된 Queue의 클래스
member variable: int first, int rear, int MaxQueue, int items[MaxQueue+1]
member function: EnQue, DeQue, MakeEmpty, IsFull, IsEmpty
Queue의 초기화
배열형 Queue가 몇 개의 데이터를 수용하고 관리할 지는 Member변수인 MaxQueue로 결정됩니다. 만약 MaxQueue가 5라고 가정한다면 5개의 데이터를 수용할 수 있게 되는 것이죠. 그리고 이때 items는 크기 ‘MaxQueue + 1'짜리 배열로 선언되며 first, rear 각각에 MaxQueue의 값인 5가 대입됩니다.
EnQue(Queue에 데이터를 추가한다)
Queue 배열을 초기화 하게 되면 그림1 상태의 배열이 생성됩니다.
그림2는 배열에 1을 넣을 것이라는 보여줍니다. 리스트에서는 CurPointer, 스택에서는 Top이 배열 내에 데이터 추가시 어떤 자리에 추가될지 안내하는 역할이었죠? Queue에서는 그 역할을 R(rear)이 하게됩니다.
그림3을 보면 R이 [0]을 가리켰고 그곳으로 1이 추가된 것이 보입니다.
그림4를 보면 이번엔 2가 배열 내에 추가되려고 하네요?
이번에도 R이 배열 내에 어떤 위치에 추가되면 좋을지 2에게 안내해주고 그 자리로 2가 추가됩니다. R이 어떤 기준으로 데이터에게 빈자리를 안내하는지 설명이 없으니까 지금은 그냥 빈공간 중에 차례대로 자리안내 해주는 것처럼 보이네요. 지금부터 R이 어떤 논리로 빈자리에 데이터를 안내해주는 지 설명해드릴게요.
EnQue는 호출 시 크게 두 가지의 연산이 수행됩니다.
첫 번째는 EnQue가 호출되면 제일 먼저 데이터를 추가해도 되는지 여부를 IsFull함수를 내부에서 호출해 검사합니다. IsFull은 ‘(R+1)%배열의크기 == F’ 이면 배열 내에 자리가 더 이상 없다고 판단해서 True를 반환하게 되고 EnQue는 True로 반환된 IsFull에 의해 입력된 데이터를 추가하지 않고 함수를 종료하게 됩니다. 반대로 ‘(R+1)%배열의크기 != F’라면 False를 반환하게 되어 EnQue를 통해 입력된 데이터를 배열 내에 추가하게 되는 것이죠.
두 번째는 EnQue를 통해 데이터를 추가하게 될 시에 추가 될 데이터가 배열 내에 어느 위치에 저장될 것인가를 결정해줘야합니다. 결정법은 간단합니다. ‘R = (R+1)%배열의 크기’를 통해 R값을 갱신해주고 갱신된 R에 위치하도록 데이터를 추가하면 끝입니다.
정리하면 EnQue시 거쳐야하는 첫 단계는 ‘배열 내에 빈자리가 존재하는지 검사’, 두 번째는 ‘배열 내에 어떤 자리에 데이터를 넣어야하는지 검사’입니다.
위에서 배운 EnQue의 동작 논리를 복습해볼까요? 3이 들어올 예정이네요. 그렇다면 EnQue 함수를 호출해줘야겠네요. EnQue가 호출되면 먼저 배열 내에 빈자리가 있는지 체크합니다. (R+1)%배열의크기 == F의 결과로 말이죠. 좌항은 (1+1)%6이므로 2가 나오고 우항인 F는 5이니까 False가 반환되네요. 3을 넣기 위해 호출됐던 EnQue가 계속 수행됩니다. 이제 3이 들어갈 위치를 R이 가리켜줘야하니까 R값도 갱신해줄까요? ‘R=(R+1)%배열의크기’를 통해 갱신이 일어나므로 R은 2로 갱신되는 것이죠.
R이 안내해준 자리로 3이 배열 내에 추가되고 EnQue는 성공적으로 종료됩니다.
(‘R이 안내해준 자리로 3이 배열 내에 추가’ 코드화: items[R] = 3)
그림8에서는 EnQue를 여러번 반복 해봤습니다. 배열이 5개의 데이터로 채워졌네요. 그림8을 보시고 ‘배열은 분명 크기6짜리로 선언이 됐는데 왜 저 빈자리를 냅두는거지?’라고 생각하실수도 있습니다.
그림9처럼 하면 안되는건가? 라고 의문을 가지실수도 있고 말이죠. 하지만 그림8에서 EnQue를 진행하려고 한다면 EnQue내에 IsFull함수가 False를 반환할 것이고 EnQue가 아무것도 하지않고 종료될 것이기 때문에 그림9처럼은 될 수 없는 것이죠.
*그림8에서 EnQue를 호출한다면 ‘(R+1)%배열의크기 == F’은 True가 됨.
DeQue(Queue에서 데이터를 추출한다)
그림10이 Queue 배열에서는 꽉찬 상태라는 것을 EnQue를 통해 설명해드렸습니다. 그렇다면 이제 DeQue를 통해 데이터를 ‘추출’해내는 동작 논리를 살펴보도록 하겠습니다.
DeQue도 EnQue와 마찬가지로 두 단계의 절차가 있습니다. 첫 번째는 Queue 배열 내에 남은 데이터가 있는지 여부를 파악하는 것이고 두 번째는 지워질 데이터를 가리키도록 F값을 갱신하는 것입니다.
Queue내에 남은 데이터 여부 파악은 IsEmpty이라는 함수를 호출해서 그 반환값으로 판단합니다. IsEmpty는 (F==R)이면 True를 반환하고 (F!=R)이면 False를 반환합니다. True가 반환된다면 배열이 비어있다고 판단하는 것이기 때문에 DeQue는 데이터 추출을 시도하지 않고 그대로 종료가 됩니다. 그렇지않고 IsEmpty가 False로 반환된다면 아직 추출할 데이터가 남아있다고 판단하는 것이기 때문에 F를 갱신하여 데이터를 추출을 진행하게 됩니다. ‘F=(F+1)%배열의크기’가 그 갱신 연산이고 말이죠. 갱신된 F가 가르키는 위치의 데이터는 지워집니다. 동시에 DeQue함수가 종료되며 그 지워진 데이터를 반환합니다.
설명을 해드렸으니 이제 예시를 통해 이해를 돕겠습니다. 그림10에서 DeQue 함수를 호출을 한다면 어떤 상태로 변할까요?
그림10에서 DeQue를 호출하여서 ‘F=(F+1)%배열의크기’에 의해 F는 0으로 갱신되었으며 [0]에 위치하던 ‘1’이 삭제된 상태를 보여줍니다. (DeQue함수는 ‘1’을 반환할 것입니다.)
그림11에서 DeQue를 다시 호출한다면 어떨까요? 그림12처럼 F는 [1]로 이동할 것이며 [1]에 있던 ‘2’가 추출될 것입니다.(‘2’가 삭제되고 ‘2’는 DeQue함수의 반환 값이 됩니다)
남은 배열 내에 남은 3,4,5도 DeQue를 호출하면서 계속 진행해 보겠습니다.(그림 13,14,15 참고)
그림 15를 보시면 이제 배열 내에 아무런 데이터도 없다는 것을 알 수 있습니다. 그렇지만 실수로 DeQue를 다시 호출한다면 어떤 일이 발생할까요?
그림16처럼 F가 [5]로 이동할까요? 아닙니다. 아까 DeQue 수행 시 두 단계의 절차가 있다고 말씀드렸었죠? 그 중 첫 단계가 IsEmpty였으며 배열 내에 남은 데이터가 존재하는지 검사하는 것이라고도 말씀드렸었구요. 그림15 상태에서 DeQue를 통해 IsEmpty가 호출되면 (F==R)이기 때문에 True 반환 될 것이고 그렇다는 것은 배열 내에 아무런 데이터도 존재하지 않는다는 것이니까 DeQue는 어떤 데이터도 추출하지 않고 그대로 종료됩니다.
DeQue의 진실
그림11~15을 통해 DeQue의 동작 논리를 알려드렸는데요, 사실 추상적인 개념으로 설명 드린거라 실제 메모리 상에서 동작하는 원리와는 다릅니다.(그렇지만 그림11~15의 메커니즘으로 Queue를 이해하셔도 무방합니다.) 그렇지만 이왕 이해하는거 실제 동작 원리로 이해한다면 좋을 것입니다. 지금부터 DeQue 호출 시 실제 메모리에서 Queue 배열을 어떻게 다루는지 알아볼게요.
DeQue의 설명을 위해 다시 Queue 배열을 꽉 채워놨습니다. 여기에서 DeQue를 호출해볼게요.
그림17에서 DeQue를 1회 호출했을 때의 Queue 배열의 상태입니다. 그림11과는 좀 다른게 ‘1’이 아직 배열 내에 남아있다는 것입니다. 다시 DeQue를 호출해보겠습니다.
그림18에서 다시 한 번 DeQue를 호출했습니다. 역시 마찬가지로 그림12와는 다르게 ‘2’가 사라지지 않았네요. 다시 DeQue를 호출하겠습니다. 이번에는 연속으로 진행할게요.
그림20, 21, 22까지 총 5회의 DeQue를 호출했습니다. 그림15와 22를 비교해보면 15에서는 F가 거쳐간 곳에 데이터가 사라진 반면 그림22에서는 전부 남아있는것을 확인 하실수 있습니다. 하지만 제가 추상적인 개념으로 설명을 진행했던 그림11~15 과정으로 이해하셔도 Queue 배열의 DeQue를 이해하셔도 무방하다고 했었죠? 왜냐하면 그림18~22처럼 F가 지나간 곳에 배열 내에 데이터가 남아있다고는 하나 Queue에서는 저 데이터들을 삭제된 데이터 취급을 하기 때문이에요. 지금부터 왜 그런건지 설명해드릴게요.
그림22를 보시면 IsEmpty함수를 만족하는 조건(F==R)이기 때문에 의아하실수도 있습니다. ‘아니 아무리봐도 배열에 데이터가 남아있는데 저걸 왜 삭제된 데이터 취급을 하는거지?’라고 생각하실수도 있구요. 하지만 잘 생각해보시면 납득이 되실겁니다. Queue배열에 관련된 멤버함수가 어떤게 있었죠? IsEmpty, IsFull, EnQue, DeQue, MakeEmpty 뿐입니다. 그렇다는 것은 오직 이 5개의 함수로만 우리는 Queue 배열을 조작 및 접근이 가능하다는 것을 의미합니다.
(부연설명: 클래스에서 member variable은 private 접근자로 정보은닉이 되기 때문에 같은 member인 member function을 통해서만 접근이 가능하기 때문입니다.)
저 5개의 함수 이외에는 배열 내의 데이터에 함부로 접근할 수가 없습니다. ‘배열 내에 3번째 index에 어떤 데이터가 있는지 조회해봐야겠다’ 라는 생각으로 ‘items[2] 출력’ 이런식으로 코드작성을 할 수 없다는 말이지요. 그러니 데이터 조회를 위해서는 오직 DeQue를 통해 F를 갱신하고 그 갱신한 F에 위치한 데이터를 반환하는 식으로만 가능한 것입니다. 하지만 그림22를 봐주세요. [0], [1], [2], [3], [4]에 존재하는 데이터를 그림22상태의 F가 조회할 수 있을까요? 아니요, 불가능합니다. 배열에 값이 남아있다고 해도 F가 한 번 지나친 데이터는 IsEmpty 조건(R==F) 때문에 저 데이터에 다시 접근할 수가 없습니다. 그리고 IsEmpty가 F의 접근을 막는 동안 EnQue가 호출되면 어떻게 될까요? EnQue에 의해 갱신된 R이 새로 들어올 데이터들에게 저 자리([0], [1], [2], [3], [4])를 안내해줄 것이고 그렇게 되면 [0], [1], [2], [3], [4]의 데이터는 덮어씌워지겠죠? 이것이 삭제된 데이터 취급하는 이유입니다.
4줄 요약정리
- 삭제 데이터 취급이라는데 배열 내에 데이터가 남아있다?
2. 클래스 안의 데이터 조회는 멤버변수로만 가능하고 Queue 클래스에서는 오직 DeQue함수로만 배열 내의 데이터를 확인 할 수 있다.
3. DeQue함수를 통해 [0], [1], [2], [3], [4]에 접근가능하다 해도 1번씩 뿐이고 다시 접근하려 해봤자 IsEmpty가 막을 것이기 때문에 삭제된 데이터 취급 되는 것이다.
4. 그리고 EnQue 함수가 호출된다면 R에 의해 [0], [1], [2], [3], [4]는 새로운 값으로 채워질 것이다.
MakeEmpty(Queue 배열 내의 모든 데이터를 삭제한다)
그림 23을 보면 다시 배열이 데이터로 꽉 차있는 상태인 것을 알 수 있습니다. MakeEmpty를 호출해서 전부 삭제해보겠습니다.
그림24를 보시면 R이 [5]로 이동한 것을 확인할 수 있습니다. 그리고 이것이 MakeEmpty함수의 끝입니다. IsEmpty가 True로 반환 될 조건 기억하시나요? 그 조건은 F와 R이 같아야 한다는 것입니다. 말그대로 F와 R이 같으면 Empty가 되는 것이죠. 그렇기 때문에 MakeEmpty는 F와 R을 동일하게 만들어주는 연산을 수행해주면 그게 끝입니다.
*DeQue의 동작논리에서 설명드렸죠? 그림24처럼 [0], [1], [2], [3], [4]에 데이터가 남아있다고 해도 삭제된 데이터 취급을 해줍니다.
이번 글에서는 Queue를 배열로 구현 했을 때의 동작 논리에 대해 얘기해봤습니다. 추후에 Queue를 Linked로 구현했을 때의 동작 논리도 소개해드림으로써 같은 자료구조라도 구현 방식에 따라 다른 동작 논리를 보인다는 것을 설명해드리도록 하겠습니다! 오늘도 긴 글 봐주셔서 감사하며 다음 글에서는 Linked로 구현된 Unsorted List에 대한 설명으로 돌아오겠습니다.
