Data Structure - Queue, (자료 구조 - 큐)

안녕하세요.

공상 개발입니다.

 

자료구조는 알고리즘과 더불어 컴퓨터공학부에서 중요하다고 자주 언급되는 과목인 만큼,

어느 정도 시간을 투자해야 됩니다.

이번 시간에는 자료구조 단원 중 하나인 큐(Queue)에 대해 간단히 알아보겠습니다.

---

2. 큐의 이해

2.1 선형 큐 (Linear Queue)

2.2 원형 큐 (Circular Queue)

2.3 덱 (Deque)

---

 

2.1 선형 큐 (Linear Queue)

 

 

큐(Queue)는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조입니다.

 

큐 예시

 

위의 이미지를 예로 든다면, 가장 먼저 줄을 선 사람이 먼저 줄을 빠져나가게 됩니다.

이러한 구조를 선입 선출(FIFO : First-In First-Out) 구조라고 합니다.

 

 더 쉬운 이해를 위해 큐의 삽입과 삭제 연산을 보겠습니다.

 

enqueue 와  dequeue 과정

 

 

선형 큐의 동작은 그다지 어렵지 않습니다.

front와 rear를 인덱스 -1에 위치 -> enqueue 동작 시 rear 값 증가를

dequeue 동작 시 front 값 증가를 시켜 해당 데이터를 관리합니다.

 

이해를 돕기 위해 간단한 코드를 보며 큐에 대해 접근하겠습니다.

 

위의 예시를 구현시킨 코드입니다.

선형 큐 코드

 

한번 정독하시면 동작 원리에 대해 이해가 될 것이라 생각합니다.

아직은 크게 어려운 부분은 없습니다.

 

만약 큐를 처음 공부하신다면, 아래의 코드에서 살짝 생각을 하게 될 것입니다.

이해가 안 될 것이라 추측되는 코드

 

간단합니다.

if(i <= q->front) , front가 가리키는 값이 i의 값 보다 크거나 같을 때 데이터가 없다고 표시합니다.

위의 코드에서는 front 값이 증가할 경우는 삭제 연산이 일어난 경우입니다.

 

if(i > q->rear) , rear가 가리키는 값보다 i의 값이 클 때 데이터가 없다고 표시합니다.

위의 코드에서는 rear가 가리키는 인덱스가 마지막 데이터의 위치이기 때문입니다.

 

 

하지만 선형 큐에는 문제점이 존재합니다.

선형적으로 데이터를 관리하기 때문에 효율적이지 못합니다.

 

선형큐 문제점  # Front와 rear 값이 계속 증가 # 배열의 앞부분이 비어 있더라도 사용을 하지 못 함 # 매번 이동을 시키면 되는데 시간 + 복잡도 증가

 

---

 

2.2 원형 큐 (Circular Queue)

 

그래서 위의 선형 큐(Linear Queue)를 보완해 나온 것이 원형 큐(Circular Queue)입니다.

 

 

공백상태, 포화상태

 

공백상태 : front == rear 포화상태 : front == (rear+1) % M 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.

 

위의 3개의 이미지를 보고 이해가 되신 분과 이해가 안 되신 분이 나뉠 겁니다.

보통은 원형 큐를 처음에 보면 이해가 안 됩니다.

정상적입니다.

 

 

아래의 원형 큐 출력 함수를 위의 선형 큐 출력 함수와 비교한다면 이해가 됩니다.

한번 가봅시다.

 

원형 큐 코드

 

 

원형 큐 출력 함수 동작만 이해한다면 나머지는 자연스럽게 따라온다고 생각합니다.

근데 이해가 안 되실 것 같아서 아래에 로직을 적어놓았습니다.

원형 큐 출력 함수

 

로직

 

1. q-> front, q->rear 가 가리키는 값 출력

2. if(! is_empty(q)) // 원형 큐가 공백 상태가 아니라면,

3. i에 q->front가 가리키는 값을 대입하시오.

4. do while 문 // 무조건 한 번은 돌리고 조건과 일치하면 계속 반복하시오.

5. (front가 가리키는 인덱스 값 +1)을 MAX_QUEUE_SIZE 값과 나누었을 때 나머지 값을 i에 대입하시오.

// 예를 들어 front가 가리키는 인덱스는 삭제 연산이 진행된 것이니,

다음 인덱스부터 출력을 해야겠죠? 그 말입니다.

6. if( i == q-> rear) // front가 가리키는 값과 rear 값이 가리키는 값이 같으면 break;

7. while( i!= q-> front); // i에 대입된 값과 front 가 가리키는 값이 같지 않으면 참. -> 반복

 

 

선형 큐와

 

---

원형 큐가 이해가 되지 않으신 분들은 우선적으로 앞의 내용을 중점적으로 선택해 학습해 주세요.

2.3 덱 (Deque)

 

우리가 앞에서 선형 큐와 원형 큐를 살펴보았습니다.

맨 처음 큐는 선입 선출(FIFO : First-In First-Out) 구조라고 말했습니다.

 

그렇다면 뒤에서 삭제가 가능하고, 앞에서 추가가 가능하고,

원하는 rear가 가리키는 값을 바로 얻을 수는 없을까?

 

이러한 요구를 만족시키는 개념이 덱입니다.

한번 살펴보시죠.

 

덱(deque) (스택 + 큐) 덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 새롭게 추가된 연산 delete_rear, add_front, get_rear 이 3가지만 추가가 된 것이고 나머지 연산은 동일합니다.

 

ㅅ

 

 

 

 

사실 앞에서 큐와 스택의 개념을 정확히 숙지하셨다면, 덱은 어려울 게 없습니다. 보너스 느낌이죠.

기능 3가지가 추가됐다고 생각하시면 됩니다.

스택의 장점과 큐의 장점을 합친 것입니다.

 

TIP : 아래의 3가지 예제 코드들을 직접 구현하는 걸 추천합니다.

 

 

 

---

 

피드백

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, 말씀해 주시면 감사하겠습니다.

 

읽어주셔서 감사합니다.