스택은 다음과 같이 데이터를 차곡차곡 집어넣어(Push) 맨 위의 데이터부터 Pop을 하는 자료구조이다.
키보드에서 입력된 스트로크를 저장한다거나, Ctrl+Z명령어를 통해 우리가 실행한 명령들을 Undo하기 위해 기억해놓는것 정도를 예시로 들 수 있다.
Queue의 경우,
이러한 형태를 띈다. 줄서기, 혹은 선입선출이라고 생각하면 된다.
자료를 추가할때는 Enqueue로 Back부분에 한칸씩 추가해주고, 자료를 빼줄때는 Dequeue로 빼주면서 다음 데이터가 Front가 되는것이다. 그러나 컴퓨터의 메모리에서 데이터를 추가할때마다 계속 Back을 한칸씩 밀면 엄청나게 긴 배열이 생겨 메모리가 낭비되거나, 배열의 끝에 막혀버릴 수도 있다.
그래서 이 큐를 개선시킨것이 원형 큐이다.
그림에서 원형 큐에 14를 넣고, 22를 넣게되면 Rear가 하나 증가한다. 데이터를 넣을때마다 rear를 하나씩 증가시킨다.
5번째 그림을 보면 처음으로 데이터를 빼는 Dequeue를 실행한다. 처음에 입력한 14가 빠지면서, Front를 하나 회전시켜주는것이다. 이런식으로
이 그림의 Front와 Back을 이어버렸다고 생각하면 된다.
원형 큐를 다 채워버리면 어떻게 될까?
문제는 하나씩 데이터를 빼게되면
이러한 형태가 되는데, 큐가 꽉 찼는지의 여부를 F와R이 한칸만 차이가 난다는 데에서 확인을 하기 때문에, 이 큐가 꽉찬건지 빈건지 알수가 없게된다.
그래서 보통 큐에 공백을 주고 그 여부로 빈건지 꽉찬건지 구분을한다. 이게 무슨말이냐면
맨 처음 비었을때 F(front)와 R(rear)이 같은곳을 가리키고있는걸 이해하고 인큐의 과정에서 리어가 움직이는걸 지켜보자.
우리는 위에서 4칸이 있는 큐에 데이터를 4개씩 꽉꽉 채워 사용했는데, 그게 아니라 3칸만 쓰고 한칸을 공백란으로 둔 상태가 꽉 찬 상황이라고 설정하면, '아, F와R이 같은위치에있으면 큐가 빈것이고, F가R보다 한칸뒤에 있으면 큐가 꽉 찬것이구나' 라고 이해할 수 있다.
'알고리즘' 카테고리의 다른 글
| [JavaScript] N-Queen 문제 (백준9663, 프로그래머스) (2) | 2023.10.02 |
|---|---|
| Heap (0) | 2021.10.28 |
| Stack예제- 후위 계산법 (Postfix) (0) | 2021.09.30 |