큐

큐란 무엇인가

큐는 스택과 다르게 선입선출의 구조를 가졌습니다.(FIFO라고도 하죠)
쉽게 생각 해
줄서기라 할 수 있습니다.

먼저 들어온 사람이 먼저 나간다.
새로운 사람이 들어오면 뒤에 슨다.
와 비슷한 거 입니다.

front? rear?

큐에는 처음 과 끝을 나타내는 front와 rear라는 것이 있다.
front가 처음
rear이 끝을 알리는 역할을 한다.

생성 방법

• 배열로 생성
  배열로 생성하게 되면 front와 near가 인덱스로 써 배열에 접근한다.
  • 단점
    front가 늘어나며 지나온 갑에 접근이 불가능함
• 연결 리스트
  연결 리스트로 생성하게 되면 front와 near가 포인터로써 값의 주소를 가지고 있다
  • 장점
    크기에 구애받지 않는다
  • 단점
    구조체 바이트 패딩이 발생하여 큰 공간을 잡을 수 있다.

필요 함수

이름	입력	출력	설명
Enqueue	원소 e	NULL	맨 뒤에 원소를 넣는다
Dequeue	NULL	NULL	맨 앞의 원소를 삭제한다
Peek	NULL	원소 e	맨 앞의 원소를 가져온다

Enqueue

• 배열의 경우
  큐가 가득 찼는지 확인 한 뒤 near 한 칸 늘리고 near위치에 원소를 집어 넣는다
• 연결 리스트 경우
  기존 near가 지정하고 있는 원소가 삽입할 원소의 주소를 가지고 near가 가리키는 주소를 삽입할 원소의 주소로 바꾼다.

Dequeue

• 배열의 경우
  큐가 비었는지 확인 한 뒤 front 한 칸 늘려준다
• 연결 리스트 경우
  front의 노드가 가르키는 주소를 front로 바꾸고. 기존 front가 가르키던 노드를 삭제해준다.

Peek

front위치의 값을 가져와준다

특수한 큐

• 원형 큐
• 우선 순위 큐
• 데큐

그래서 얘는 어따씀

• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

---

혹시나 내용이 이상하거나 틀린 점이 있으면 댓글로 남겨주세요