05. 큐란?

01. 큐란?

영어 queue는 줄을 의미하는 단어이다.

가장 먼저 들어온 것이 가장 먼저 나가는 큐방식으로 넣고 빼는 자료구조를 큐라고 한다.

선입선출, FIFO(First-in-First-Out) 방식이라고 부리기도 한다.

LIFO 형식인 스택과 비교하면서 공부하는 것이 좋다.

 

• front: 큐의 맨 앞에 있는 원소, 제일 먼저 큐에 들어온 원소
• tail: 큐의 맨 뒤에 있는 원소, 제일 나중에 큐에 들어온 원소

큐에서 삽이할 때는 삽입할 원소를 알려주어야하지만 삭제할 때는 단순히 삭제하면 된다.

스택에서 삭제는 무조건 최근에 들어간 원소를 대상으로 하기 때문이다.

 

다음은 필요한 작업들의 명시한 큐의 추상 데이터 타입이다.

작업들 중 앞의 3개는 큐의 핵심 작업이고, 뒤에 2개는 거의 모든 자료에 공통으로 들어가는 작업이다.

• 맨 끝에 원소를 추가한다.
• 맨 앞에 원소를 삭제하면서 알려준다.
• 맨 앞의 원소를 알려준다
• 큐가 비어있는지 확인한다
• 큐를 깨끗이 비운다

 

02. 배열을 이용한 큐

배열을 이용한 큐의 경우, 큐의 최대 크기를 예상할 수 없을 때 운영하다가 더 큰 배열을 할당받아 옮기는 작업을 해주어야 하는 불편함이 있다. 그럼에도 불구하고 배열 기반의 큐는 간명함과 효율성이 뛰어나다.

배열을 이용하는 큐는 원형으로 모델링 하는 것이 효율적이다.

 

작업1: 원소 삽입

 

 

작업2: 원소 삭제

무조건 가장 먼저 들어 온 원소를 대상으로 함

 

 

 

03. 연결 리스트를 이용한 큐

단반향, 원형 연결 리스트 사용

레퍼런스  tail이 리스트의 마지막 노드를 가리키고 원형이므로 이를 통해 리스트의 첫번째 노드(front)에 접근할 수 있다.

연결리스트로 큐를 구현할 시에는 큐의 마지막 노드를 가리키는 래퍼런스 tail을 null로 해두어야 한다.

 

작업1: 원소 삽입

큐 맨 뒤 즉 tail 노드 뒤에 원소 하나를 삽입하고 레퍼런스 tai이 삽입된 새 노드를 가리키도록 바꾸어준다.

새노드는 리스트의 첫 번째 노드로 연결 시킨다.

newNode.next ← tail.next tail.next ← newNode tail ← newNode

만약 큐가 비어있다면 tail이 null인 상태라 tail.next란 표현은 쓸 수 없다.

newNode.next ← newNode

tail ← newNode

이렇게 생각해주어야 한다.

 

작업2: 원소 삭제

큐엣 원소를 삭제할 떄는 무조건 맨 앞에 있는 원소를 삭제한다.

원형 리스트의 경우 front 노드(삭제 이전 맨 앞의 노드)를 가리키고 있던 tail  노드의 링크를 front 노드의 다음 노드(현재 맨 앞에 있는 노드)를 가르키도록 바꾼다. 이렇게 되면 front노드가 삭제된다.

 

 

04. 다른 클래스를 재사용한 큐

LinkedList 클래스 상속

이미 구현된 LinkedList를 상속받아 큐의 기본 구조를 쉽게 만들 수 있으며, 상속받은 메서드를 활용해 큐의 여러 기능을 구현할 수 있다.

 

코드 예시:

• enqueue()는 LinkedList의 append() 메서드를 사용하여 큐의 끝에 요소를 삽입
• dequeue()는 remove(0)을 통해 큐의 맨 앞 요소를 삭제
• front()는 get(0)으로 큐의 맨 앞 요소를 반환
• dequeueAll()은 clear() 메서드를 사용하여 큐를 비움

ADT 리스트 사용

ADT(Abstract Data Type) 리스트를 사용하여 큐를 구현할 수 있다.
여기서는 ListInterface<E>를 사용하여 큐를 구현하는 클래스 ListQueue<E>를 만든다.
list라는 필드가 큐에 저장된 요소들을 관리하며, ADT의 리스트 인터페이스를 통해 큐를 조작한다.

 

 

05. 큐 응용: 좌우동형 문자열 체크

좌우동형 문자열이란 앞에서 부터 읽으나 뒤에서부터 읽으나 같은 문자열을 말한다.

 

큐와 스택을 사용한 좌우대칭 문자열 검사 방법:

• 문자열의 각 문자를 스택과 큐에 동시에 저장 (스택에 저장하는 연산은 push(), 큐에 저장하는 연산은 enqueue()).
• 그 다음, 저장된 문자들을 하나씩 꺼내면서(스택에서는 pop(), 큐에서는 dequeue()) 비교합니다.
• 스택과 큐에서 꺼낸 문자가 동일하면 계속 진행하고, 다르면 그 즉시 멈춥니다.
• 큐와 스택이 모두 비어지면 좌우대칭 문자열로 판정되며, 그렇지 않으면 좌우대칭 문자열이 아닙니다.