1106
1. 큐 (Queue)란?
먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식의 자료구조
큐는 순서대로 버스를 타는 것과 비슷합니다.
먼저 줄을 선 사람이 먼저 버스에 탑승하는 것처럼
큐에서는 가장 먼저 들어간 데이터가 가장 먼저 나옵니다.
먼저 집어넣은 데이터가 나중에 나오는 Stack과는 반대되는 개념이죠.
2. 큐의 구성 요소
put: 데이터를 넣는다get: 데이터를 꺼낸다(삭제한다)front(head): 데이터를 꺼낼 수 있는 위치(맨 첫번째 데이터의 위치)rear(tail): 데이터를 넣을 수 있는 위치(마지막 데이터 위치의 다음)overflow: 더 이상 데이터를 넣을 수 없는 상태underflow: 큐에 남아있는 데이터가 없는 상태
3. 큐의 기본 동작
put(insert)get(delete)
큐의 기본 동작으로는 put(insert)와 get(delete)이 있습니다.
put은 큐에 자료를 넣는 것을,
get은 큐에서 자료를 꺼내는 것을 의미합니다.
만약 overflow라면 put 동작이 안 되겠고,
underflow라면 get동작이 되지 않겠죠.
4. 큐의 종류
큐의 종류에는 크게 두 가지가 있는데, 선형 큐와 환형 큐가 있습니다.
4.1. 선형 큐
선형 큐: 막대 모양으로 된 큐
선형큐는 일방적인 방향이기 때문에 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있습니다.
4.2. 환형 큐
이러한 선형 큐의 단점을 보완한 것이 바로 환형 큐입니다.
큐에서 put get 동작이 계속 일어났을 때, front가 큐의 끝과 같아지는 순간이 찾아오는데, 이 때 앞의 빈 공간을 사용하기 위해 front와 큐의 맨 처음 공간을 연결시켜 마치 원형구조인 것처럼 동작하게 됩니다.
이렇게 공간이 남아있음에도 불구하고 overflow가 되는 상황을 방지할 수 있습니다.
5. 큐 vs 스택 비교
큐와 스택의 가장 큰 차이점은 후입선출, 선입선출이라고 할 수 있습니다.
구내식당에 갔을 때를 한 번 예로 들어보겠습니다.
당신이 만약 구내식당에 가본 적이 있다면 싱크대에 쌓여있는 접시 더미를 본 적이 있을 겁니다.
5.1. 스택(Stack) - LIFO
스택 먼저 볼까요?
더러운 접시를 스택에 추가하면 맨 위에 놓일 겁니다. 설거지를 시작하면 맨 위의 접시를 먼저 닦을수밖에 없을 겁니다. 이렇게 상단부터 차례대로 제거되며 맨 마지막에는 맨 첫 번째로 싱크대에 넣었던 접시를 닦게 되겠지요. 그래서 후입선출(LIFO)이라고 합니다.
5.2. 큐(Queue) - FIFO
그 다음으로는 큐를 보겠습니다.
구내식당에서 설거지를 하는 뒤쪽으로 들어가볼까요? 컨베이어 벨트가 더러운 접시들을 운반하고 있습니다. 이를 선입선출(FIFO)라고 합니다. 고객이 다 먹고 난 접시를 놓은 순서대로 컨베이어벨트가 싱크대로 접시들을 운반하니까 말입니다.
6. 큐 활용문제 풀어보기
Q1. 선형큐의 front와 큐의 끝이 동일해지는 경우를 무엇이라고 하나요?
Q2. 환형큐가 아무런 데이터가 없는 상태일 때 front와 rear의 상태는 동일한가요?
Q3. 환형큐의 최대 크기가 7이고, 현재 상태가 [, , B, C, D, E, F]일 때 이 상태를 무엇이라고 하나요?
Q4. 스택과 큐가 각각 후입선출인지 선입선출인지를 작성하세요.
