1. 도입
: 현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예인 큐와 스택, 데크이다.
: 일렬로 늘어선 자료들을 표현하는 자료 구조로 여기에 자료를 넣고 꺼내는 연산을 지원한다. 이때 자료는 특젇 순서로 넣고 특정 순서로만 꺼낼 수 있다.
: 배열이나 연결 리스트로 쉽게 구현이 가능함에도 중요한 이유는 자료 구조의 형태에 이름을 붙여 소통의 원활을 이끌어냈기 덕분이다.
•
큐(queue)
: 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다.
: 가장 먼저 들어간 자료를 가장 먼저 꺼내게 되며 이를 선입선출이라고도 부른다.
: 놀이공원이나 음식점에서 선 줄, 할 일의 목록 등을 큐로 표현할 수 있다.
•
스택(stack)
: 한쪽 끝에서만 자료를 넣고 뺄 수 있다.
: 가장 먼저 들어간 자료가 가장 나중에 나오게 되며 이를 후입선출이라고도 부른다.
: 전산학 전반에 걸쳐 사용되는데, 함수 호출이 끝나고 이전 함수로 돌아가야할 때, 내부적으로 스택을 이용해 문맥을 관리한다.
•
데크(dequeue)
: 양쪽 끝에서 자료를 넣고 뺄 수 있는 자료 구조로 데크를 이용하면 스택, 큐 둘 다 구현할 수 있다.
: 자료구조에 자료를 넣는 작업을 푸시(push) 그리고 자료를 꺼내는 작업을 팝(pop)이라고 하며, 큐와 스택은 각각 넣고 빼는 방향에 따라 푸시와 팝 연산을 그리고 데크는 앞과 뒤 모두 푸시와 팝 연산을 지원하며 이들 연산은 모두 상수 시간(O(1))에 이루어져야 한다.
2. 큐와 스택, 데크의 구현
•
연결 리스트를 통한 구현
: 가장 간단한 방법으로 연결 리스트를 사용하면 양쪽 끝에서의 추가와 삭제를 모두 상수 시간에 할 수 있으므로 연산에 대한 요구사항을 쉽게 충족시킬 수 있다.
: 물론 이 경우 노드의 할당과 삭제 그리고 포인터 변경에 대한 연산의 시간 소요로 연결 리스트가 가장 효율적인 연산은 아님.
•
동적 배열을 이용한 구현
: 동적 배열을 이용해서 이들 자료 구조를 구현할 수도 있다.
: 스택의 경우 한쪽 끝에서만 자료의 추가와 삭제가 일어나므로 동적 배열을 그저 가져다 사용하기만 하면 된다.
: 하지만 큐와 데크의 경우 그렇게 간단하지 않은데, 원소를 뒤에서 추가하거나 삭제하기는 쉽지만 배열의 맨 앞에서 원소를 삭제하기 위해 O(n)의 시간이 걸리기 때문이다.
: 따라서 동적 배열을 이용해 큐와 데크를 구현할 경우, 첫 번째 원소와 마지막 원소의 위치를 두 변수 head와 tail에 유지하면서 맨 앞에서 원소를 꺼낼 때 뒤에 있는 원소들을 모두 앞으로 옮겨오는 대신 head를 다음 원소로 옮기는 연산을 수행한다.
: 이와 같은 방식은 모든 연산을 상수 시간에 한다는 목적(시간복잡도 측면?)에서는 부합하지만 낭비되는 공간(공간복잡도 측면..)이 너무 많다는 문제가 있다.
: 이와 같은 문제를 해결하기 위해 tail이 배열 size에 도달할 경우, 0으로 초기화되어 해당 부분부터 다시 저장을 수행하도록 할 수 있다.
: 동적 배열의 처음과 끝을 붙여 원형으로 만들었다고 생각할 수도 있기 때문에 이와 같은 배열의 구현을 대개 환형 버퍼라고 부른다.
•
표준 라이브러리의 구현
: 스택과 큐, 데크는 아주 기본적인 자료 구조이기 때문에 거의 모든 언어의 표준 라이브러리에서 구현체를 제공한다.
: 사실 연결 리스트만 지원하더라도 이것을 스택이나 큐, 데크처럼 사용할 수 있기 때문에 이들을 직접 구현할 이유는 전혀 없다.
