Queue 재학습 및 동적배열로 Queue 구현하기
큐를 구현하는 코드들에 대해 이해가 아직은 부족한 것 같아 다른 유튜버의 큐에 대한 개념을 재학습하고 동적할당을 이용해서 c언어로 구현해봤다.
가정 상황
int a[5]라는 배열이 있다고 가정해보자.
a[0]부터 a[4]까지 데이터가 1부터 5까지 들어갈 것이다.
1.기존 배열에서 직접 데이터를 삭제하는 방식
- 데이터로 메모리가 다 포화되어있다고 가정했을 때 FIFO하기 위해서 a[0]의 데이터 즉 첫번째 데이터를 빼야된다.(뺀다=끄집어내다=삭제한다)
- 우린 기존에 이 데이터를 끄집어내면 두번째부터 있는 뒤의 데이터들도 앞에서 빠진 자리때문에 한 칸씩 이동해야되는 비효율적인 방식을 썼다.(배열안에 많은 데이터들이 하나씩 이동하는데 시간과 비용이 듬)
- 큐
- 큐는 이런 문제를 해결하기위해 데이터를 꺼낼 때 실제 데이터를 저장해서 이동시키는 방식이 아닌 실제로 넣고(입력) 꺼낼(삭제) 위치가 어딘지만 알아서 이동하도록 하는 방식이다.
== 내 눈에 보이는 부분만 활성화 시키는 것
큐는 데이터를 뒤에서 들어와서 앞으로 나가는 형태로 구현이 된다.
이때 여기에서 front와 rear이라는게 등장하는데
front 변수 : 어느 위치에서 데이터를 꺼낼 것인지 가리킨다.
데이터는 앞에서 빠져나간다.
rear 변수 : 어느 위치에 데이터를 저장할 것인지 가리킨다.
= 데이터가 있는 요소 다음 요소를 가리킴
데이터는 뒤에서 들어온다.
이걸 가지고 우리는 위치를 파악하는 것이다.
큐는 일반적인 배열로 쓰면 크기가 한정되어있고 에러가 날 수 있어서 순환해서 계속 쓸 수 있는 애초부터 원형큐로 활용한다.(아래에서 왜 원형을 쓰는지 이유가 나온다.)
(마지막 요소(a[4])에 데이터가 들어가면 rear는 원래는 a[5]를 가리켜야되는데 5번째 공간은 MAX size에 존재하지 않음 그래서 에러남)
3.큐의 시뮬레이션
ㄱ.데이터를 넣어주는 경우(Enqueue)
처음에 큐가 비어있는 상태에선 front와 rear가 a[0]에서부터 시작한다.
즉,1번 데이터가 들어갈 위치도, 꺼낼 위치도 rear와front로 잡는다.
- 데이터 '1'을 a[0]에 넣으면 rear가 증가되어 a[1]을 가리킨다.이런식으로 데이터를 넣을때마다 rear는 증가된다.
(다음번엔 a[+1]에 넣을 차례라는걸 알려줌)
ㄴ.데이터를 꺼내는 경우(Dequeue)
꺼내다 = 큐에서 삭제하다로 보면됨
맨 처음 a[0]에 있던 데이터 '1'을 꺼내면 front가 증가되어 a[1]을 가리킨다.이런식으로 데이터를 꺼낼때마다 front는 증가된다.
-
데이터위치를 가리키고 있는 범위는 front부터 rear 전까지의 범위로 봐야되며,이렇게 인큐, 디큐가 일어날때마다 데이터의 범위 또한 실시간으로 변하는 것이다.
-
여기서 실제로 꺼내진 데이터가 삭제된 것은 X 그저 가리키는 데이터의 범위가 위처럼 정해져있는것이다. = 활성화된 범위에 따라 큐가 가지고있는 데이터들이 변하는것임
ex)앞 책상엔 여러 물건이 있는데 내 손은 2개라 몇 개만 들 수 있는것
ㄷ.위처럼 첫번째 데이터를 빼낸 상태에서 원형큐의 마지막 요소에 인큐를 하는 경우
rear는 다시 a[0]을 가리킨다.이때 데이터의 범위는 front가 가리키는 a[1]부터 rear 전인 a[4]까지다.
4.우리는 왜 큐를 원형큐로 쓰는 것인가?
위와 같이 일반적인 큐는 계속 데이터가 삽입되면 어느순간 MAX SIZE를 넘어가 에러가 난다.그래서 배열의 MAX SIZE와 rear의 값이 같다면 다시 rear의 값을 a[0]로 바꿔주는 작업이 필요하다.그러면 다시 순환하는 원형의 구조를 가지게된다.
원형의 구조에 위의 예시를 적용해서 MAX SIZE인 a[5]까지 데이터가 가득찬 상태에서 rear는 a[0]를 가리키고 추가로 '6'을 넣는다 가정하면 rear는 증가돼서 a[1]을 가리킨다.이때 활성화된 데이터의 범위는 front인 a[2]부터 rear전인 a[0]까지다.이게 무슨소리냐면 이렇게 기존에 a[0]에 들어있던 '1'이란 데이터는 다른 데이터 값 '6'이 들어가면서 활성화된 데이터 범위에서 제외된다.(그럼 이 데이터는 삭제되냐? 아니다.그리고 이 데이터의 삭제유무가 중요한건 아님)
근데 여기서 또 데이터 값 '7'을 넣으면 일어나는 현상이 있다 .
rear인 a[2]를 가리키면서 front와 같은곳을 가리킨다.
5.rear와 front가 같은곳을 가리키는 경우는 두 가지 상황에서 나타나게된다.
바로 큐의 모든 메모리가 꽉 찬 경우와 비어있는 경우다.
여기에선 문제점이 발생한다.
문제점
처음에 front와 rear을 a[0]으로 가리키도록하는데 이 말은 즉 컴퓨터가 데이터가 꽉 찼는지 아예 비어있는지 판단을 하기힘들다는것이다.
해결방법
프로그래머가 이 큐가 찼는지의 유무를 알기위한 하나의 장치를 추가적으로 해주면된다.바로 count변수(이름은 자유)라는 데이터의 갯수를 세주는 역할의 변수를 만들어주는것!!
데이터가 추가로 삽입돼서 rear가 증가하면 이 변수의값도 같이 증가하도록 count를 ++해준다.
반대로 데이터를 꺼낼때마다 front가 이동하게되는데 그때는 count가 --하게 한다.
이렇게하면 count변수의 값은 데이터의 저장 갯수인 front부터 rear 전까지의 데이터 갯수와 비례하게된다.
※ 큐 구현 코드의 구조체 부분 복습
Typedef Struct Queue
Queue;
Typedef -> 구조체를 대표하는 새로운 자료형을 Typedef로 정의한것
기존 데이터 유형에 대해서 새 이름을 만드는데 사용된다.
코드 가독성이 높아지고, 오류 가능성이 낮아진다.
Struct -> 구조체를 의미
Queue -> 구조체의 이름
Queue; -> 밑에 쓰인 Queue는 Struct Queue의 별칭이다.(변수가 아님)이 별칭을 가지고도 변수를 선언하거나 자료형을 함수 매개변수로 전달할 수 있다.
그리고 이렇게 쓸 수 있는 이유는 Typedef 덕분
typedef를 사용하면 struct를 안써주고 Queue만으로 Queue testfunc; 이렇게 변수를 생성할 수 있고
사용하지않으면 Struct Queue testfunc;를 써줘서 변수를 생성해줘야된다.
