자료구조

● 자료구조

- by wiki

전산학에서 자료 구조(資料構造, 영어: data structure)는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다.

 

효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

 

 

● 자료구조를 선택하기 위한 요인

- 데이터양

- 데이터를 사용하는 방법과 횟수

- 데이터의 정적 혹은 동적인 특성

- 데이터 구조에 의해 요구되는 기억장치의 양

 

 

 

● 자료구조의 형태에 따른 분류

 

 

 

● 구현에 따라

- by wiki

• 배열 - 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
• 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조이다.
• 연결 리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성된있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
• 환형 연결 리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
• 이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
• 환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
• 해시 테이블 - 개체가 해시값에 따라 인덱싱된다.

 

 

● 형태에 따라

-by wiki

 

• 단순구조
• 정수
• 실수
• 문자열
• 문자
• 등의 기본자료형

 

• 선형 구조

• 스택 - 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
• 큐 - 스택과 반대로 큐 자료 구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
• 환형 큐 - 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.
• 덱 - 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

 

• 비선형 구조
• 그래프 - 정점과 정점을 잇는 간선으로 구성된다.
• 방향 그래프, 비방향 그래프 - 간선이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.
• 트리 - 뿌리 노드와, 뿌리 또는 다른 노드를 단 하나의 부모로 갖는 노드들로 이루어진 구조. 부모 자식 관계는 간선으로 표현된다. 비방향 그래프의 경우, 회로가 없고 연결된 그래프를 뜻한다. 방향 그래프의 경우 간선의 방향은 보통 부모를 가리키도록 구현된다.
• 이진 트리 - 자식 노드가 최대 두 개인 트리.
• 힙 - 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.

 

• 파일구조
• 순차파일
• 색인파일
• 직접파일

 

 

 

 

 

 

 

 

 

 

 

 

● 스택(Stack)

- 데이터를 건초나 짚더미와 같이 쌓아놓은 형태
- 데이터를 삽입시 스택 아래부터 쌓이며 최신 데이터는 스택의 가장 윗 부분에 위치한다.
- 데이터를 추출(제거)시 스택의 가장 윗 부분에서 꺼내므로 LIFO(Last-In, First-Out) 구조이다.
- 스택을 구현시 배열 기반 또는 링크드리스트 기반으로 구현이 가능하다.
- 배열 기반의 스택의 경우 스택의 크기가 정해져 있다.

스택은 LIFO구조라고 하며, 이는 후입선출 즉 들어온 데이터 순으로 쌓이되 데이터가 나올때는 마지막에 넣은 데이터 순으로 나온다는 특징이

있습니다. 다음과 같은 그림으로 설명할 수 있습니다. 

 

 

 

 

 

 

 

 

● 큐(Queue)
 - 전단(Front), 후단(Rear)를 가지고 있는 배열과 비슷한 자료구조.
 - FIFO(First In First Out) 선입선출 구조.
 - 전단은 큐의 가장 맨 앞을 가르키고 있으며 후단은 큐의 마지막요소 + 1 을 가리키고 있다.
 - 데이터 삽입시(Enqueue) 후단에 데이터가 삽입되며 데이터 제거시 전단의 데이터가 추출되고 전단의 index는 +1 이 된다.
 - 배열 기반의 큐는 사이즈의 한계가 있다.
 - 배열 기반의 큐는 제거연산을 수행할 수록 전단(Front)의 index가 뒤로 밀려나기 때문에 결국엔 후단 index까지 도달하게 되므로
   상당히 비효율적이다. 그래서 배열 기반 큐의 단점을 해소하기 위해 원형큐(CircularQueue)라는 개념이 나왔다.

 

- 간단히

먼저 들어온사람이 먼저 나간다.
은행에서 순서대로 번호표를 뽑게 하고 번호표 순서대로 일을 처리해주는 예
또는 버스정류장에서 먼저 온순서대로 탑승하는 예

 

 

 

큐는 한쪽 끝은 front로 정해서 삭제 연산만 수행하도록 하고 다른쪽 끝은 rear로 정하여 삽입 연산만 수행하도록 한다.

 

 

 

 

● 선형큐의 문제점

 

 

1차원 배열을 사용하여 큐를 구현하는것을 선형큐라 하는데 포화상태로 인한 문제점이 있다.

rear가 배열의 마지막 위치에 있기 때문에  큐에 자리가 있는데도 포화상태로 인식하고 삽입을 하지 않는다.

 

 

● 선형큐의 문제 해결방법

 

 

1. 저장된 원소를 배열의 앞부분으로 이동시켜서 위치를 조정해주는 방법
But 순차자료에서의 이동 작업은 연산을 복잡하게 하여 효율성을 떨어뜨린다. 

 

 

 

 

 

 

 

● 원형큐(CircularQueue)
 - 배열 기반의 큐가 원형으로 이루어진 상태.
 - 원형으로 이루어져 있기 때문에 큐가 가득 찼을때나 완전히 비어있을때 Front와 Rear의 index는 동일하므로
   Empty인지 Full인지 구분할 수 없다.
 - 그러므로 원형큐를 생성할때는 더미(Dummy) 공간을 생성하여 원래 용량(capacity)보다 +1 만큼 증가시켜 배열을 생성한다.
   예) 큐의 사이즈 : 9   =>  배열 사이즈 : 10
 - 'Front == Rear'는 비어있는 상태, 'Rear + 1 == Front' 는 가득찬 상태

 

 

1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하고 사용
공백 상태와 포화 상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다.

 

 

원형 큐 연산 과정

 

 

 

1. CreateQueue();                           2. enQueue(A);

3. enQueue(B);                           4. deQueue(A);

 

5. enQueue(C);                                                    6. enQueue(D);

 

 

 

 

 

Stack vs Queue