Chapter 3. Linear Data Structure

1. Stack

Last In First Out

한쪽 끝에서 자료를 넣고, 빼는 자료구조이다.

 

Example

• RunTime Stack 함수 , 재귀 함수

• 방문기록

• ctrl + z 실행 취소

• 괄호 검사 , 수식 연산

• 미로찾기

• DFS

ADT Function

삽입 : Push 연산으로 Top에서만 이루어진다.

삭제 : Pop 연산으로 Top에서만 이루어진다.

탐색 : Top의 element를 return한다.

 

Door가 1개이며 이를 Top이라고 부른다.

삽입/삭제/탐색 연산 모두 O(1)에 수행 가능하다.

 

[그림 1] Stack 시각화

2. Queue

First In First Out

마지막에 들어 온것 보다 처음 들어온 것에 초점을 둔다. 즉, 처음 들어온 데이터가 먼저 나가는 구조이다.

 

Example

1. 우선순위 같은 작업 예약 시스템 - 인쇄 대기열, 멀티프로그래밍(시분할시스템)

2. 선입선출이 필요한 대기열 - 티켓 카운터

3. 조세퍼스

4. BFS

 

구현

[그림 2] 위 사진은 Array, 아래 사진은 Linked List로 Queue를 구현

ADT

삽입 : Rear에서 데이터를 삽입 한다.

삭제 : Front에서 데이터를 삭제 한다.

탐색 : Front에서 데이터를 return 한다.

 

Door가 2개이며 각각 Front, Rear이다.

 

배열/링크드리스트로 구현 했을때 위의 모든 연산에 대한 시간 복잡도는 O(1)이다.

 

배열로 구현시 메모리 손실을 방지하기 위해 환형 큐를 사용 하기도 한다.

예를들어 삽입/삭제 연산을 번갈아 계속 수행을 할 경우 마지막에 index 끝에서 Front와 Rear가 만나게 된다. 하지만 아무런 처리 없이 구현 했을 때 컴퓨터는 배열이 꽉찼다고 생각을 하지만, 이전 index들은 낭비되고 있다. 따라서 modulus(%)를 이용하여 낭비되는 index없이 모두 사용하게 만든것이 환형 큐다.

구현 -> 인덱스 접근시 %N을 사용하여 모든 인덱스가 0~N-1 사이에 있게 한다.

3. Vector

배열처럼 데이터를 index로 접근하며 공간을 동적으로 확장/축소 하는 ADT를 말한다. 물론 배열과 링크드 리스트로 구현이 가능하나 인덱스에 대한 연산이 많아 STL Vector는 배열로 구현돼있다.

 

배열과 달리 할당된 사이즈가 꽉차면 사이즈를 새로 할당한다. 예를들어 현재 n의 크기를 가지고 있고 n개 모두 꽉찰 경우 2n크기의 size로 재 할당 후 기존 원소들을 transfer한다.

배열은 데이터 갯수보다 배열 선언 갯수가 많을 때 메모리적으로 낭비가 생긴다. 따라서 벡터는 선언 size의 1/4만큼의 데이터갯수를 가지면 선언 size를 1/2로 줄인다.

 

위 방식은 이전 장에서 본 Array Doubling과 같은 맥락이다.

따라서 탐색은 O(1)이고,삽입, 삭제에 대해 Asymptotic Worst 분석은 O(n)이고, Amortized Worst 분석은 O(1)이다.

공간 복잡도는 O(N)에서 O(n)으로 근접할 수 있다.

 

장점

   1. 특정 index로 바로 접근 가능하다.

   2. 원소를 마지막에 삽입 할 때 빠르다.

   3. 캐싱 처리

 

단점

   1. 중간 삽입/삭제시 성능이 떨어진다.

   2. 동적이라 확장/축소가 편하나 확장시 비용이 크다. [단, 자주 일어나지 않는다.]

4. List

Doubled Linked List로 구현 한다. 이는 중간에 삽입/삭제가 자주 일어날 때 사용하는 목적이 존재한다. Index로 접근이 가능하나 성능이 좋지는 않다. 이때 Iterator로 index 접근한다.

 

장점

   1. 중간 삽입/제거가 빠름

   2. 데이터를 크기를 변경해도 Vector처럼 Transfer하는 Cost가 없다.

단점

   1. 원소의 인덱스로 직접 접근이 불가능하며 처음 혹은 끝에서부터 선형 탐색을 진행한다.

   2. 원소간 상호 연결 정보를 위해 추가적 메모리 비용 발생

   3. 캐싱 처리가 좋지 않다.

 

Example

데이터가 중간 삽입/삭제가 빈번하다면 리스트가 좋다. [탐색 Cost < Transfer Cost]

데이터의 크기를 모를 때 메모리적 관점에서 리스트가 좋다.

Index로 데이터를 접근하는 연산이 많다면 벡터가 좋다.

CPU 캐시 지역화를 고려한다면 벡터가 좋다.