스택 다음에 배울 자료구조는 큐!
(이미지 출처: 위키백과)
1. 큐의 특징
- 큐와 스택의 공통점 : 삽입과 삭제의 위치가 제한적인 자료구조이다.
- 차이점 : 선입-선출 (FIFO). 가장 먼저 삽입된 원소는 가장 먼저 삭제된다.
2. 큐의 구현
- 선형큐
- 초기 공백 큐 생성 ( front와 rear을 모두 -1로 초기화)
- 삽입 (enQueue) : rear += 1을 한 후, 배열원소를 저장한다.
- 삭제 (deQueue) : front += 1을 하여 큐에 남아있게 될 첫번째 원소로 이동하고 값을 리턴한다.
- 공백상태 검사(isEmpty()) : front == rear 일 경우에 공백상태이다
- 포화상태 검사(isFull()) : rear ==n-1 (n:배열의 크기, n-1:마지막인덱스)
- 검색(Qpeek()) : front +=1 현재 front의 한자리 뒤에 있는 원소를 검색하여 반환한다.
- 원형큐💡선형큐의 문제점 : 잘못된 포화상태인식
- 선형큐를 사용하여 원소의 삽입과 삭제를 반복하면, 배열의 앞부분을 활용할 수 있는 공간이 있음에도 불구하고, rear=n-1 즉, 포화상태로 인식하여 더이상 삽입을 수행하지 않는다.
⇒ 해결방안 : 원형큐!
- 1차원 배열이지만, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용한다.
- 선형큐와 원형큐의 삽입, 삭제위치 비교
삽입 위치 삭제위치 선형큐 rear = rear + 1 front = front + 1 원형큐 rear = (rear + 1) % n front = (front + 1) % n
- 우선순위 큐
- FIFO 순서가 아니라, 우선순위가 높은 순서대로 먼저 나가게 된다.
- 배열 혹은 리스트를 사용해서 구현할 수 있다.
- 배열을 이용하여 구현할 때의 문제점 : 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생한다. → 이에 소요되는 시간이나 메모리 낭비가 크다.
3. 큐의 활용 : 버퍼(Buffer)
💡
데이터를 한 곳에서 다른 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는
메모리의 영역
⇒ 순서대로 입력/출력/전달 되어야 하므로 FIFO 방식의 자료구조인 큐가 활용된다.
ex) 키보드 버퍼
사용자 키보드 입력 → 키보드 입력 버퍼에 enter키 입력이 들어오면 → 프로그램이 실행된다.
Uploaded by N2T