스택과 큐의 개념 및 연산 방법

문서 내 토픽

1. 스택(Stack)

스택은 후입선출(LIFO) 원칙에 따르는 선형 자료구조로, 가장 마지막에 삽입된 데이터가 먼저 삭제된다. 기본 연산으로는 push(삽입), pop(삭제), peek(확인)이 있으며, 배열이나 연결리스트로 구현 가능하다. 함수 호출 관리, 실행 취소 기능, 웹 브라우저 뒤로 가기 등에 활용된다. 스택이 비어있을 때 pop을 시도하면 언더플로우, 가득 찬 상태에서 push를 시도하면 오버플로우가 발생한다.
2. 큐(Queue)

큐는 선입선출(FIFO) 원칙을 따르는 선형 자료구조로, 먼저 삽입된 데이터가 먼저 삭제된다. 기본 연산으로는 enqueue(뒤쪽 삽입), dequeue(앞쪽 삭제), peek(확인)이 있다. front는 데이터가 나갈 위치, rear는 들어갈 위치를 가리킨다. 작업 스케줄링, 인쇄 대기열, 너비 우선 탐색(BFS) 등에 활용되며, 요청된 순서대로 작업을 처리할 수 있다.
3. 선형 큐(Linear Queue)

배열을 사용하여 구현한 기본 큐 형태로, front와 rear가 한 방향으로만 증가한다. 삭제 후 앞쪽에 빈 공간이 생겨도 재사용되지 않으며, rear가 배열 끝에 도달하면 더 이상 삽입이 불가능해진다. 공간 활용 효율이 낮아지는 단점이 있어, 이를 해결하기 위해 원형 큐가 개발되었다.
4. 원형 큐(Circular Queue)

배열의 끝과 처음이 연결된 것처럼 인덱스가 순환하는 큐 구현 방식이다. 나머지 연산(mod)을 사용하여 rear = (rear + 1) mod capacity, front = (front + 1) mod capacity로 관리한다. 삭제로 생긴 빈 공간을 즉시 재활용할 수 있어 공간 낭비를 줄이고, 항상 최대 용량까지 활용 가능하다.

Easy AI와 토픽 톺아보기

1. 스택(Stack)

스택은 컴퓨터 과학의 기본적이면서도 매우 중요한 자료구조입니다. LIFO(Last In First Out) 원칙에 따라 동작하는 스택은 함수 호출 스택, 괄호 검증, 역폴란드 표기법 계산 등 다양한 실제 응용에서 필수적입니다. 구현이 간단하고 시간복잡도가 O(1)로 효율적이라는 장점이 있습니다. 다만 고정 크기로 구현할 경우 오버플로우 문제가 발생할 수 있으므로, 동적 배열이나 연결 리스트를 활용한 구현이 권장됩니다. 스택의 개념을 정확히 이해하는 것은 더 복잡한 알고리즘과 자료구조를 학습하는 데 있어 기초가 됩니다.
2. 큐(Queue)

큐는 스택과 함께 가장 기본적인 자료구조로, FIFO(First In First Out) 원칙을 따릅니다. 실생활의 대기열 개념을 그대로 반영하고 있어 직관적으로 이해하기 쉽습니다. 프린터 작업 관리, 프로세스 스케줄링, 너비 우선 탐색(BFS) 등 광범위한 응용 분야가 있습니다. 그러나 선형 큐의 경우 dequeue 연산 후 앞부분의 공간이 낭비되는 문제가 있어, 이를 해결하기 위해 원형 큐나 동적 배열 기반의 구현이 필요합니다. 큐의 효율적인 구현과 활용은 시스템 설계와 알고리즘 최적화에 중요한 역할을 합니다.
3. 선형 큐(Linear Queue)

선형 큐는 배열을 이용한 가장 단순한 큐 구현 방식입니다. front와 rear 포인터를 사용하여 enqueue와 dequeue 연산을 수행하며, 구현이 직관적이고 이해하기 쉬운 장점이 있습니다. 초기 학습 단계에서 큐의 개념을 파악하는 데 매우 유용합니다. 그러나 dequeue 연산 후 배열의 앞부분 공간이 재사용되지 않아 메모리 낭비가 발생하는 심각한 단점이 있습니다. 이러한 문제로 인해 실제 응용에서는 거의 사용되지 않으며, 원형 큐나 동적 배열 기반의 개선된 구현으로 대체되는 것이 일반적입니다.
4. 원형 큐(Circular Queue)

원형 큐는 선형 큐의 메모리 낭비 문제를 해결하기 위해 고안된 효율적인 자료구조입니다. 배열의 끝과 처음을 연결하여 순환 구조를 만들어, 선형 큐에서 발생하는 공간 낭비를 완전히 제거합니다. 모듈로 연산을 활용하여 포인터를 관리하므로 배열의 모든 공간을 효율적으로 활용할 수 있습니다. 다만 구현이 선형 큐보다 복잡하고, 큐가 비어있는 상태와 가득 찬 상태를 구분하기 위해 추가 로직이 필요합니다. 실제 시스템에서 버퍼 관리, 메시지 큐, 멀티미디어 스트리밍 등에 널리 사용되는 실용적이고 효율적인 자료구조입니다.

주제 연관 토픽을 확인해 보세요!

주제 연관 리포트도 확인해 보세요!