큐와 스택 그리고 데크

1. 자료 구조

 

현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예로 

 

큐와 스택, 데크가 있다.

 

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

 

이 때 자료는 특정한 순서로 넣고 특정한 순서로만 꺼낼 수 있다.

 

그러므로 이 세 자료 구조들을 구분하는 것 또한 어느 순서로 자료를 넣고 뺄 수 있는가 이다.

 

이들은 다른 알고리즘을 구현하는 도구로 유용하게 사용된다.

 

배열과 링크드 리스트로 쉽게 구현할 수 있다.

 

 

자료 구조에 자료를 넣는 작업을 푸시(push) 

자료 구조에 자료를 꺼내는 작업을 팝(pop)

이들 연산은 모두 O(1)이다.

2. 큐(queue) = FIFO

 

큐에서는 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다.

 

선입선출 속성을 가지고 있다.

 

3. 스택(stack) = LIFO

 

한쪽 끝에서만 자료를 넣고 뺄 수 있다.

 

가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다.

 

후입선출 속성을 가지고 있다.

 

스택은 전산학 전반에 걸쳐 널리 사용된다.

 

함수 호출이 끝나고 이전 함수로 들어갈때  이 함수 바로 이전의 함수로 돌아가야한다.

때문에 컴퓨터는 내부적으로 스택을 사용해 함수들의 문맥(context)을 관리한다.

 

4. 데크(dequeue)

 

양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구조

 

이것을 구현하면 스택과 큐 모두 구현하는 것과 같다.

 

5. 구현

 

연결 리스트를 통한 구현

 

연결 리스트를 이용하면 양쪽 끝에서의 추가와 삭제를 모두 상수 시간에 할 수 있기 때문에

모든 연산이 상수 시간이어야 한다는 요구 조건을 쉽게 충족시킬 수 있다.

이 경우 노드의 할당과 삭제, 그리고 포인터로 원소접근 하는데 시간이 걸리기 때문에 

효율적인 구현은 아니다.

 

동적 배열을 통한 구현

 

스택 - 바로 사용할 수 있다.

 

큐, 데크 - 맨 앞 원소의 삭제와 추가의 경우 시간이 O(n)이기 때문에 효율적이지 못하다.

             따라서 맨 앞 원소와 맨 뒤 원소를 가리키는 두 변수를 따로 생성하여 관리가 필요하다.

             head 와 tail에 마지막 원소를 위치를 기억한다.

             이로 인해 버려지는 공간을 없애기 위해 공간을 재활용한다.(모듈로 연산)

             이와 같은 재활용하는 배열을 환형 버퍼(circular buffer)라 부른다

 

	head				tail
	1	2	3	4

	tail		head
7			3	4	5	6

 

 

 

- 알고리즘 문제해결전략 625p