[종만북] Queue, Stack, Deque / 큐와 스택, 데크

[종만북] Queue, Stack, Dequ / 큐와 스택, 데크

[종만북] Queue, Stack, Deque / 큐와 스택, 데크

 

큐와 스택, 데크

Queue 큐

• 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다.
• 가장 먼저 들어간 자료를 가장 먼저 꺼내게 된다.
• FIFO (First In First Out) 선입선출

 

Stack 스택

• 한쪽 끝에서만 자료를 넣고 뺄 수 있다.
• 가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다.
• LIFO (Last In First Out) 후입 선출
• 전산학 전반에 걸쳐 널리 사용된다.
• 함수 호출이 끝나고 이전 함수로 돌아갈 때, 이 함수 바로 이전의 함수로 돌아가야 하는데 컴퓨터는 내부적으로 스택(Stack)을 사용하여 함수들의 문백(context)를 관리한다.

 

Deque 데크

• 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구조
• 데크(Deque)를 이용하면 스택(Stack)과 큐(Queue)를 모두 구현할 수 있다.

 

Push / Pop

• 자료구조에 자료를 넣은 작업을 푸시(Push) 그리고 자료를 꺼내는 작업을 팝(POP)이라고 한다.
• 큐(Queue)와 스택(Stack)은 각각 넣고 빼는 방향에 따라 푸시와 팝 연산을 지원한다.
• 데크(Deque)는 앞과 뒤에서 모두 푸시와 팝 연산을 지원한다.
• 이들 연산은 모두 상수 시간, 즉 O(1)에 이루어져야 한다.

 

 

큐와 스택, 데크의 구현

연결 리스트(Linked List)를 통한 구현

• 세 가지 자료구조를 구현하는 가장 간단한 방법은 연결 리스트를 사용하는 방법이다.
• 연결 리스트를 이용하면 양쪽 끝에서 추가와 삭제를 모두 상수 시간에 달성 가능하다.
• 노드의 할당과 삭제 그리고 포인터를 따라가는데 드는 시간이 걸리기 때문에 가장 효율적인 구현은 아니다.

 

동적 배열을 이용한 구현

• 스택의 경우에는 한쪽 끝에서만 자료의 추가와 삭제가 일어나므로 동적배열을 사용하는데 비교적 간단하다.
• 큐와 데크의 경우에는 배열의 맨 앞에서 원소를 삭제하기 위해서 O(n)의 시간이 걸리므로 첫번째 원소와 마지막 원소의 위치를 head 와 tail 에 저장하여 사용하는 방법으로 구현한다.
  • 모든 연산을 상수 시간에 달성
  • 버려지는 공간이 많아진다는 문제 발생
• head 와 tail 을 사용시 낭비되는 공간이 많이 발생하는 문제는, tail 이 배열의 끝에 도달시 다시 처음으로 돌아와서 원소를 저장하는 방법으로 극복 가능
  • 환형 버퍼 (circular buffer)

환형 버퍼 (circular buffer)

 

표준 라이브러리의 구현

• 스택과 큐, 데크는 아주 기본적인 자료구조이기 때문에 거의 모든 언어의 표준 라이브러리에서 구현체를 제공
• 연결 리스트 (Linked List) 만 지원하더라도 스택이나 큐, 데크로 활용 할 수 있기 때문에 직접 구현할 이유는 없다.