[Algorithm] 19. 큐와 스택, 데크

도입

현실 세계의 규칙을 추상화하는 추상화 자료 구조의 예로 큐와 스택, 데크가 있다.

이 자료구조는 일렬로 늘어선 자료들을 대표하는 자료구조다.

또한, 여기에 자료를 넣고 꺼내는 연산을 지원한다.

배열이나 연결리스트를 사용을 해도 되지만 이러한 사용하는 이유는 무엇일까?

자료 구조의 형태에 이름을 붙여서 개발자 간의 의사소통을 원활하게 하기 위해서다.

큐와 스택, 데크

큐(queue)

• 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다.
• 이 속성을 선입선출(FIFO)라고 한다.
• 큐의 예시로는 놀이공원이나 음식점에서 선 줄과 할일의 목록 등이 있다.

스택(stack)

• 한쪽 끝에서만 자료를 넣고 뺄 수 있다.
• 이 속성을 후입선출(LIFO)라고 한다.
• 컴퓨터 내부적으로 스택을 이용하여 함수들의 문맥을 관리한다.

데크(dequeue)

• 양쪽 끝에서 자료를 넣고 뺄 수 있다.
• 데크를 이용하면 스택과 큐를 모두 구현할 수 있다.

지료구조에 자료를 넣는 작업을 푸시(push)라고 한다.

자료를 꺼내는 작업을 팝(pop)이라고 한다.

큐와 스택은 자료를 넣고 빼는 방향에 따라 푸시와 팝 연산을 지원한다.

데크는 앞과 뒤에서 모두 푸시와 팝 연산을 지원한다.

이 두 연산 모두 상수시간, O(1)에 이루어져야 한다.

큐와 스택, 데크의 구현

연결 리스트를 통한 구현

• 큐와 스택, 데크를 구현하는 가장 쉬운 방법은 연결 리스트를 이용하는 것이다.
• 연결 리스트는 양쪽 끝에서 추가와 삭제를 상수 시간 안에 해결해준다.
• 하지만, 노드의 할당과 삭제, 포인터를 추적하는데 시간이 걸리므로 효율적인 구현이 아니다.

동적 배열을 이용한 구현

• 스택의 경우는 한쪽 끝에서 자료의 추가와 삭제가 이루어지므로, 동적 배열을 사용하기 쉽다.

• 큐와 데크의 경우 배열의 맨 앞에서 원소를 삭제하려면 O(n) 시간이 걸린다.

• 첫 번째 원소와 마지막 원소의 위치를 두 변수 head, tail 에 유지해야 한다.

맨 앞에 있는 원소를 가져올 때, 뒤에 있는 원소를 모두 앞으로 옮기지 말고, head를 다음 원소로 옮긴다.

하지만, 이와 같은 방식은 모든 연산을 상수시간에 지원할 수 있지만, 버려지는 공간이 너무 많다는 문제가 있다.

이 문제를 해결하기 위해 앞의 버려지는 공간을 재활용하고, 더 이상 원소를 삽입할 수 없을 때 동적 배열을 재할당하는 것이다.

이와 같은 배열 구현을 환형 버퍼(circular buffer) 라고 한다.

변수 tail 이 배열 끝에 도달하자 처음으로 다시 돌아와서 원소를 저정한다.

마치 동적 배열의 처음과 끝을 이어붙여 원형을 만들었다.