큐와 스택, 데크
큐와 스택, 데크
큐와 스택, 데크는 일렬로 늘어선 같은 형태의 자료들을 저장합니다. 차이점은 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가입니다.
큐
한쪽 끝에서 자료를 넣고 반대쪽 끝에서 자료를 꺼낼 수 있습니다. 따라서 가장 먼저 들어간 자료를 가장 먼저 꺼내게 됩니다. 이러한 속성을
FIFO(First In First Out)이라고 부릅니다.
스택
한 쪽 끝에서만 자료를 넣고 뺄 수 있습니다. 따라서 가장 늦게 넣은 자료를 가장 먼저 꺼내게 됩니다. 이러한 속성을
LIFO(Last In First Out)이라고 부릅니다.
데크
데크는 양쪽 끝에서 자료들을 넣고 뺼 수 있는 자료 구조를 말합니다. 따라서 데크를 이용하면 스택과 큐를 모두 구현할 수 있습니다.
큐와 스택, 데크의 구현
연결리스트를 통한 구현
이 세 가지 자료 구조를 구현하는 가장 간단한 방법은 연결 리스트를 이용하는 것이다. 연결 리스트를 이용하면 양쪽 끝에서 추가와 삭제 모두 상수 시간에 할 수 있기 때문에, 모든 연산이 상수 시간이어야 한다는 요구 조건을 쉽게 충족할 수 있다. 물론 이 경우 노드의 할당과 삭제 그리고 포인터를 따라가는 데 드는 데 시간이 걸리기 떄문에 연결 리스트가 가장 효율적인 구현은 아니다.
동적 배열을 이용한 구현
스택의 경우 한쪽 끝에서만 자료의 추가와 삭제가 일어나므로 동적 배열을 곧장 사용할 수 있다.
스택과 큐의 활용
예제: 큐를 이용한 조세푸스 문제의 해법
예제: 스택을 이용한 울타리 자르기 문제의 해법
- 스위핑 알고리즘
- 다시읽기
- 15.11 참조
문제: 찍이 맞지 않는 괄호(BRACKETS2, 하)
문제: 외계 신호 분석(ITES, 중)
- 알고스팟 문제 링크
- 다시읽기
풀이: 외계 신호 분석
- 단순한 알고리즘
- 최적화된 알고리즘
- 온라인 알고리즘
- 온라인 알고리즘
오란인 알고리즘이란 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘을 말한다. 알고리즘 수행 중 새 입력을 받아 계산을 계속하기 때문에, 입력 전체가 메모리에 올라와 있지 않아고 계산을 시작 할 수 있습니다.
- 오프라인 알고리즘
오프라인 알고리즘이란 입력 전체를 이미 가지고 있다고 가정하고 동작하는 알고리즘을 말한다. 예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워넣는 방식으로 동작하므로, 처음에 모든 원소가 없더라도 시작할 수 있다. 반면 선택정렬은 남아있는 모든 원소 중에서 최소의 원소를 찾아서 맨 앞에 옮기는 방식으로 작동하므로 모든 원소를 알고 있어야만 동작을 시작할 수 있습니다. 따라서 삽입정렬은 온라인 알고리즘, 선택 정렬은 오프라인 알고리즘이라 할 수 있다.
