도입
현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예로 큐와 스택, 데크가 있습니다. 이들은 일결로 늘어선 자료들을 표현하는 자료구조로, 여기에 자료를 넣고 꺼내는 연산을 지원합니다. 이때 자료는 특정한 순서로 넣고 특정한 순서로만 꺼낼 수 있습니다. 사실 이와 같은 연산들은 모두 배열이나 연결 리스트를 이용하면 쉽게 구현할 수 있는 것들입니다. 그럼에도 큐와 스택, 데크가 중요한 이유는 흔히 사용하게 되는 자료 구조의 형태에 이름을 붙였다는 데 있습니다.
큐와 스택, 데크
큐와 스택, 데크는 일렬로 늘어선 같은 형태의 자료들을 저장합니다. 이때 세 자료 구조들을 구분하는 것은 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가입니다.
- 큐에서는 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있습니다. 이 속성을 선입선출(FIFO)라고 부릅니다.
- 스택에서는 한쪽 끝에서만 자료를 넣고 뺄 수 있습니다. 이 속성을 후입선출(LIFO)라고 부릅니다.
- 데크는 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구조를 말합니다.
자료구조에 자료를 넣는 작업을 푸시 그리고 자료를 꺼내는 작업을 팝이라고 합니다. 이들 연산은 모두 상수 시간, 즉 에 이루어져야 합니다.
큐와 스택, 데크의 구현
연결 리스트를 통한 구현
이 세 가지 자료 구조를 구현하는 가장 간단한 방법은 연결 리스트를 사용하는 것입니다. 하지만 이 경우 노드의 할당과 삭제 그리고 포인터를 따라가는 데 드는 시간이 걸리기 때문에 연결 리스트가 가장 효율적인 구현은 아닙니다.
동적 배열을 이용한 구현
스택의 경우 한쪽 끝에서만 자료의 추가와 삭제가 일어나므로 동적 배열을 곧장 사용할 수 있지만 큐와 데크의 경우 간단하지 않습니다. 배열의 맨 앞에서 원소를 삭제하면 모든 원소를 한 칸씩 앞으로 이동해야 하기 때문에 의 시간이 걸리기 때문입니다. 따라서 동적 배열을 이용해 큐나 데크를 구현할 때는 첫 번째 원소와 마지막 원소의 위치를 두 변수 head와 tail에 유지하면서(실제로는 tail이 마지막 원소 다음 위치를 가리키게 합니다. 텅 빈 큐를 표현하기 위해서 입니다.), 맨 앞에서 원소를 꺼낼 때 뒤에 있는 원소들을 모두 앞으로 옮겨오는 대신 head를 다음 원소로 옮깁니다.
만약 tail이 배열의 끝에 도달한다면 처음으로 옮겨서 자료를 저장합니다. 이와 같은 배열의 구현을 환형 버퍼(circular buffer)라고 합니다.
자바에서의 구현
스택
자바에서 스택은 Stack클래스를 이용해 동적 배열에 자료들을 저장합니다. Stack클래스는 Vector클래스를 상속 받는데 Vector클래스의 내부를 보면 배열로 구현한 것을 알 수 있습니다.
큐
자바에서 큐는 ArrayDeque클래스로 동적 배열에 저장할 수도 있고 LinkedList클래스로 연결 리스트로 구현할 수도 있습니다.
ArrayDeque의 기본 생성자입니다. 배열을 할당하는 것을 알 수 있습니다.
데크
자바에서 데크는 ArrayDeque클래스로 동적 배열에 저장할 수도 있고 LinkedList클래스로 연결 리스트로 구현할 수도 있습니다.
동적 배열에서 푸시할 때 배열이 가득 찼을 때
큐나 데크를 동적 배열로 구현했을 때 푸시 연산을 수행할 때 만약 배열이 가득 찼다면 어떤 식으로 배열을 동적으로 할당하는지 궁금할 수 있습니다. 일단 ArrayDeque 클래스의 grow() 함수의 코드는 다음과 같습니다.
이 코드를 쉽게 그림으로 해석하면
화살표의 위치가 head라고 했을 때 새로 늘어난 용량 만큼 헤드가 뒤로 밀려나는 식으로 구현했습니다.
참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)
