📝 Queue의 정의
먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out)구조로 저장하는 형식이다.
❗ 관련 용어
1) Enqueue : 큐 맨 뒤에 요소 추가
2) Dequeue : 큐 맨 앞의 요소 삭제
3) Peek : front에 위치한 데이터를 확인
4) front(head) : 큐의 맨 앞의 위치(인덱스)
5) rear(tail) : 큐의 맨 뒤의 위치(인덱스)
6) overflow : 큐가 꽉 차서 더이상 자료를 넣을 수 없는 경우
7) underflow : 큐가 비어 있어 자료를 꺼낼 수 없는 경우
🎯 Queue의 특징
- 삭제 연산이 수행되는 곳은 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)
- 스택과 다르게 Queue의 한쪽 끝에는 삽입 작업이 다른한쪽 끝에는 삭제 작업이 나뉘어서 진행된다.
- Queue는 리어에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며 프론트에서 이루어지는 삭제 연산을 Dequeue라고 부른다
✔ 사용 예시) 은행업무, 서비스 센터의 대기시간, 프로세스 관리 등
📉 Queue의 단점
- 큐(Queue)를 구현하고 사용할때 큐에서 데이터를 빼내는 deQueue()함수를 쓰게 되면 맨 앞에있던 값이 빠져나가게 되는데 이때 front가 한칸씩 뒤로 밀려나게 되면서 큐의 가용범위가 줄어들고 큐의 재사용 또한 불가능하게 된다.
- 큐의 재사용을 위해 front를 출력하고 front뒤의 인덱스를 하나씩 앞당기게 되면 불필요한 연산이 너무 많아진다.
🧬 Queue의 종류
1) 선형 : 막대 모양으로 된 큐
- 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 옮겨야한다는 단점이 있다.
2) 환형 : 원형으로 연결된 큐
- front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결된다.
- 선형 큐의
문제점을 보완한다.배열로 큐를 선언하고 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생하는 것
➕ 연결리스트로 구현한 큐 (링크드 큐)
링크드 큐는 연결 리스트를 사용한 것으로써, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징이다. 필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.
참고자료
- 자료구조-스택Stack과-큐Queue에-대해서-알아보자
- [알고리즘] 2.2.자료구조 : 큐(Queue) 이해하기
- 큐 (자료 구조)
- [자료구조] 큐(Queue) 란? 한번에 쉽고 간단하게 이해하기!
도라에몽 암기빵