[c언어로 쉽게 풀어쓴 자료구조] 5장 큐

1. Queue?

큐(Queue)는 선형 자료 구조로, 데이터를 저장하고 검색하는 데 사용되는 중요한 자료구조

데이터를 저장할때 "선입선출" (FIFO, First-In-First-Out) 원칙을 따름

→먼저 큐에 추가된  데이터는 먼저 처리되고 제거 됨.

 

2. Queue의 구성요소

• 데이터 요소(Elements): 큐에 저장되는 실제 데이터 항목들로, 큐에 추가되거나 제거 됨
• 프런트(Front)와 리어(Rear): 큐의 시작과 끝 지점을 나타내는 두 포인터. 이들은 데이터의 추가 및 제거에 사용 됨
• 리어(Rear): 큐의 끝 지점을 가르키는 포인터. 큐에 추가 연산이 수행되면, 새로운 데이터가 리어에 추가 됨

[큐 용어]

• add(): 데이터를 추가하는 작업
• delete(): 데이터를 꺼내 사용하는 작업
• rear: 가장 최근에 추가한 데이터를 지시하는 포인터 또는 인덱스
• front: 사용할 데이터를 지시하는 포인터 또는 인덱스
• overflow: 끝까지 add()된 경우, rear == SIZE -1 일때 add() 시도하면 발생
• underflow: 더이상 꺼낼 수 없는 경우, front > rear 일 때, delete() 시도 하면 발생

 

3. Queue의 기본 동작

• Enqueue (데이터 추가): 큐의 리어에 데이터를 추가. 새로운 데이터가 큐의 가장 뒤에 추가 됨
• Dequeue (데이터 제거): 큐의 프런트에서 데이터를 제거하고 반환함. 가장 먼저 추가된 데이터가 가장 먼저 제거 됨
• Peek (데이터 확인): 큐의 프런트에서 데이터를 확인하지만 제거하지 않음 

 

4. Queue 종류

• 선형 큐 (Linear Queue): 데이터를 FIFO 순서로 처리하는 가장 기본적인 큐
• 환형 큐 (Circular Queue): 큐의 마지막 요소가 첫 요소와 연결된 큐로, 원형으로 순환
• 우선순위 큐 (Priority Queue): 각 데이터 요소에 우선순위를 할당하고 해당 우선순위에 따라 데이터를 처리하는 큐
• 데큐 (De Queue): 양쪽에서 삽입, 삭제가 가능한 구조

 

5. Queue VS Stack

• 큐(Queue): 데이터를 FIFO순서로 처리 (먼저 추가된 데이터가 먼저 제거)
• 스택(Stack): 데이터를 LIFO 순서로 처리 (가장 최근에 추가된 데이터가 가장 먼저 제거)

특성	큐 Queue	스택 Stack
처리방식	선입선출 (FIFO, First-in-First-Out)	후입선출 (LIFO, Last-In-First-Out)
데이터 추가	리어(Rear)에서 추가 (Enqueue)	탑(Top)에서 추가 (Push)
데이터 제거	프런트(Front)에서 제거(Dequeue)	탑(Top)에서 제거(Pop)
데이터 확인 (Peek)	프런트(Front)에서 확인(Peek)	탑(Top)에서 확인(Peek)
주요 용도	작업 대기열 관리, 너비 우선 탐색	함수 호출 및 재귀, 깊이 우선 탐색
구현 방식	연결 리스트 또는 배열 사용	연결 리스트 또는 배열 사용
예시	일반 큐, 우선순위 큐, 환형 큐	일반 스택

 

 

• 큐 초기화 : init(q)
• 비었나? : in_empty(q)
• 가득 찼나? : in_full(q)
• q에 끝에 e를 추가 : enqueue(q,e)
• q의 맨 앞에 있는 e를 제거하여 반환 : dequeue(q)
• q의 맨 앞에 있는 e를 읽어서 반환 : peek(q)

 

 

 

 

 

 

참고: 

https://velog.io/@mic050r/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Tree-Graph%EC%9D%B4%EB%9E%80

https://airforce836.tistory.com/entry/C%EC%96%B8%EC%96%B4%EB%A1%9C-%EC%89%BD%EA%B2%8C-%ED%92%80%EC%96%B4%EC%93%B4-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-5%EC%9E%A5-%ED%81%90-%EB%82%B4%EC%9A%A9-%EA%B0%84%EB%8B%A8-%EC%A0%95%EB%A6%AC