[자료구조] 자료구조의 정리

자료 구조는 현실세계에 존재하는 데이터를 효율적으로 저장할 수 있는 구조화 표현의 개념이라고 할 수 있다. 그럼 왜 자료 구조를 알아야 하는것일까?

컴퓨터에는 메모리,CPU, 스토리지가 존재하는데 데이터가 중구난방으로 존재하게 되면 CPU가 메모리나 스토리지에 저장되어있는 데이터를 찾는데 오랜시간이 소비되게 된다. 이 말은 즉, 프로그램의 속도를 저하시키게 된다. 데이터가 자료구조의 개념에 기반하여 저장되어있다면 CPU가 자료를 찾는데 드는 시간은 짧아지고 효율적이 사용이 될 것이다.

자료 구조의 분류는 단순구조, 선형구조, 비선형구조, 파일구조로 나뉘어져 있다.

단순 구조

프로그래밍시 변수도 크기가 커지면 여러공간에 변수를 나눠서 저장하게 된다. 변수의 데이터 타입에 따라 구조도 바뀌게 된다

선형 구조

자료가 저장 관계가 1:1인 경우이다. 쉽게 말해 자료가 한줄로 똑바로 서있다고 생각하면 된다.

비선형 구조

자료의 저장 관계가 1:N인 경우이다. 복잡하지만 효율적인 자료구조이다.

파일 구조

서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조 이다.

가장 많이 접하고 사용되는 선형구조와 비선형 구조에 대해서 알아보자.

---

선형구조

선형구조에서 가장많이 쓰이는 용어는 FIFO 와 LIFO 이다.

FILFO(First In First Out) : 가장 먼저들어온 데이터가 가장 먼저 출력된다.
LIFO(Last In First Out) : 가장 나중에 들어온 데이터가 가장 먼저 출력된다.

스택(Stack) 구조

스택은 Push()와 Pop()기능 으로 이루어져있는 자료구조이다. Push()를 하면 스택안에 자료 순차적으로 쌓이게 되고 가장 최근에 들어온 자료는 Top이 되어진다. Pop()을 하면 가장 최근에 들어온 자료가 방출되게 된다. 즉 Top인 자료가 방출되고 그 밑에 있는 자료가 Top이 된다. 스택(Stack)은 FILO이다

ex)괄호 검사, 역순 문자열 만들기, 후위 표기법으로 변환...

큐(Queue) 구조

큐도 Push()와 Pop()기능이 있다. Push는 삽입, Pop은 삭제 기능이다. 큐는 한쪽 끝(rear) 에서는 삽입연산만 이루어지고 다른 한쪽 끝(front) 에서는 삭제연산만 이루어지는 유한 순서 리스트이다.

보통 데이터가 입력된 순서대로 처리해야 하는 경우에 많이 사용된다. ex)은행 번호표, 콜센터, BFS...

먼저 삽입된 Item이 먼저 삭제가 이루어지는 FIFO구조이다.

덱(Deque) 구조

큐와 구조가 비슷하지만 덱은 앞뒤 모두에서 Push와 Pop기능이 가능하다.

---

비선형 구조

비선형 자료구조는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다. 1:N의 관계를 가지고, 계층적 구조를 나타내기에 적당하다.

트리(Tree) 구조

트리(Tree)구조는 노드(Node)와 간성(Branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프 형태 이다. 부모와 자식간의 계층 구조가 명확하다.

그래프(Graph) 구조

노드와 간선으로 이루어져있는 사이클 형태의 그래프이다.

---

사실 자료구조는 개념을 외우는것보다 각 자료구조의 개념을 이해하고 그림으로 그려보는것이 중요하다. 자료구조의 특성상 데이터의 Push와 Pop이 많고 순서가 자주 바뀌게 되어 그림으로 그리면서 이해하는 것이 무엇보다 중요하다. 위 글을 읽으면서 각 자료구조가 어떻게 작동하고 어떻게 생겼는지 그림을 한번씩만 그려보아도 이해하는데 큰 도움이 될것이다.