C로 배우는 자료구조 6장 연습문제

C로 배우는 자료구조 6장 연습문제 - 큐와 데크

문서 내 토픽

1. 큐(Queue)의 개념과 특성

큐는 FIFO(First In First Out) 선입선출 구조의 자료구조로, front에서는 삭제, rear에서는 삽입이 일어난다. 일상생활에서 줄 서기, 택시 정거장 등에서 찾을 수 있다. 선형 큐에서는 rear가 마지막 인덱스에 도달하면 포화 상태가 되는 문제가 발생하며, 이를 해결하기 위해 원형 큐를 사용한다. 원형 큐의 공백 상태는 front == rear이고, 포화 상태는 front == (rear + 1) mod n이다.
2. 원형 큐(Circular Queue)의 구현

원형 큐는 선형 큐의 포화 상태 문제를 해결하기 위해 배열의 끝과 처음을 연결한 구조이다. 삭제된 빈 공간을 재활용하여 메모리 효율성을 높인다. 원형 큐에서 연산을 수행할 때 모듈로(mod) 연산을 사용하여 인덱스를 순환시킨다. 포화 상태와 공백 상태를 구분하기 위해 하나의 공간을 항상 비워둔다.
3. 데크(Deque)의 개념과 연산

데크는 양 끝에서 삽입과 삭제가 모두 가능한 자료구조이다. 단순 연결 리스트로 구현할 때 first와 last 포인터를 사용하여 양 끝에 접근한다. 마지막 노드 삭제 시 전 노드의 링크를 NULL로 변경해야 하므로 O(n) 시간이 소요되어 O(1) 시간 내에 수행할 수 없다.
4. 스택과 큐의 비교

스택은 LIFO(Last In First Out) 후입선출 구조로 top에서만 삽입과 삭제가 일어난다. 큐는 FIFO 선입선출 구조로 front에서 삭제, rear에서 삽입이 일어난다. 두 자료구조는 데이터 접근 순서가 반대이며, 각각 다른 응용 분야에서 사용된다.

Easy AI와 토픽 톺아보기

1. 큐(Queue)의 개념과 특성

큐는 컴퓨터 과학에서 매우 중요한 선형 자료구조로, FIFO(First In First Out) 원칙을 따릅니다. 이러한 특성은 실제 생활의 대기열과 동일하여 직관적으로 이해하기 쉽습니다. 큐는 운영체제의 프로세스 스케줄링, 네트워크 패킷 처리, 프린터 작업 관리 등 다양한 실무 분야에서 활용됩니다. 큐의 기본 연산인 enqueue와 dequeue는 O(1)의 시간복잡도를 가져 효율적입니다. 다만 배열 기반 구현에서는 메모리 낭비 문제가 발생할 수 있어 원형 큐나 연결 리스트 기반 구현이 필요합니다. 큐의 개념을 정확히 이해하는 것은 더 복잡한 자료구조와 알고리즘을 학습하는 기초가 됩니다.
2. 원형 큐(Circular Queue)의 구현

원형 큐는 배열 기반 큐의 메모리 낭비 문제를 해결하는 효과적인 방법입니다. 배열의 끝과 처음을 연결하여 논리적으로 원형 구조를 만들므로, 이전에 사용했던 배열 공간을 재활용할 수 있습니다. 구현 시 front와 rear 포인터를 적절히 관리하여 원형 특성을 유지해야 하며, 모듈로 연산을 활용합니다. 원형 큐는 메모리 효율성이 우수하고 고정 크기의 버퍼가 필요한 임베디드 시스템이나 실시간 시스템에서 매우 유용합니다. 다만 구현 복잡도가 일반 큐보다 높고, 큐가 비어있는 상태와 가득 찬 상태를 구분하기 위한 추가 로직이 필요합니다. 이러한 특성을 이해하고 올바르게 구현하는 것이 중요합니다.
3. 데크(Deque)의 개념과 연산

데크는 Double Ended Queue의 약자로, 양쪽 끝에서 모두 삽입과 삭제가 가능한 자료구조입니다. 이는 스택과 큐의 장점을 결합한 형태로, 더 높은 유연성을 제공합니다. 데크의 연산으로는 앞뒤 양쪽에서의 addFirst, addLast, removeFirst, removeLast 등이 있으며, 모두 O(1)의 시간복잡도를 가집니다. 데크는 슬라이딩 윈도우 알고리즘, 팰린드롬 검사, 우선순위 큐 구현 등 다양한 응용 분야에서 활용됩니다. 연결 리스트나 동적 배열로 구현할 수 있으며, 각 구현 방식의 장단점을 고려하여 선택해야 합니다. 데크의 유연성은 강력하지만, 이로 인해 코드의 의도가 불명확해질 수 있으므로 신중한 사용이 필요합니다.
4. 스택과 큐의 비교

스택과 큐는 모두 선형 자료구조이지만 근본적으로 다른 특성을 가집니다. 스택은 LIFO(Last In First Out) 원칙으로 가장 최근에 추가된 요소가 먼저 제거되며, 큐는 FIFO 원칙으로 먼저 추가된 요소가 먼저 제거됩니다. 스택은 함수 호출 스택, 괄호 검사, 역폴란드 표기법 계산 등에 사용되고, 큐는 프로세스 스케줄링, BFS 알고리즘, 메시지 큐 등에 사용됩니다. 두 자료구조 모두 기본 연산이 O(1)의 시간복잡도를 가지므로 효율적입니다. 문제 해결 시 상황에 맞는 자료구조를 선택하는 것이 중요하며, 때로는 두 자료구조를 함께 사용하기도 합니다. 스택과 큐의 차이를 명확히 이해하는 것은 알고리즘 설계의 기초입니다.