자료 구조 - Chapter 07

큐(Queue)

큐

큐는 선입선출 자료구조의 일종이다.

영어로 FIFO(First - In - First - Out) 구조의 자료구조이다.

 

큐의 ADT정의

• Enqueue : 큐에서 데이터를 넣는 연산
• Dequeue : 큐에서 데이터를 꺼내는 연산

예제 : 배열로 큐 구현(queue)

큐의 과정에서 머리(앞 부분)을 참조하여 dequeue 연산을 진행하고 꼬리(뒷 부분)을 참조하여 enqueue연산을 

진행한다.

 

또한 기본적인 큐 구현에 있어서 front포인터와 rear포인터를 사용하여 구현하고, 자료 이동 없이

편리하게 사용하기 위해 원형 큐 (circular queue)를 사용한다.

• 원형 큐가 텅 빈 상태 : F와 R이 동일한 위치
• 원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다.

배열로 원형 큐 구현

CircularQueue.c

0.00MB

CircularQueue.h

0.00MB

ex7-1 circularQueue.c

0.00MB

예제 : 연결리스트로 큐 구현(queue)

 

연결 리스트로 큐 구현

ex7-2 LinkedQueue.c

0.00MB

ListBaseQueue.c

0.00MB

ListBaseQueue.h

0.00MB

덱(Deque)

덱

deque는 double-ended queue를 줄여서 표현한 것이다.

양방향으로 넣고 뺄 수 있다는 사실에 초점이 맞춰져서 지어진 이름

 

예제 : 데크 구현하기

데크 구현하기

Deque.c

0.00MB

Deque.h

0.00MB

ex7-3 Deque.c

0.00MB