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

[종만북] 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) 만 지원하더라도 스택이나 큐, 데크로 활용 할 수 있기 때문에 직접 구현할 이유는 없다.

반응형

from http://leeiopd.tistory.com/406 by ccl(A) rewrite - 2021-11-30 10:01:25