자료구조란?
프로그램에서 쉽게 사용될 수 있도록 구성된 데이터 간의 논리적인 관계이다.
자료구조의 개념
- 자료를 효율적으로 사용할 수 있도록 컴퓨터에 저장하는 방법이다.
- 처리되는 데이터는 구조를 어떻게 구성하느냐에 따라 성능에 많은 영향을 미친다.
- 데이터를 처리하는 입장에서 데이터 사이에 존재하는 관계이다.
효과적으로 설계된 자료구조는 효율적인 프로그래밍을 할 수 있도록 한다.
데이터의 추가, 삭제, 검색을 효율적으로 할 수 있는 적절한 데이터 구조를 사용하는게 중요하다.
형태에 따른 자료구조
단순 구조
기본 데이터 타입이다.
- int : 정수형
- float : 실수형
- double : 실수형
- char : 문자형
등 기본적 자료형이 있다.
선형 구조 (Liner)
말 그대로 선의 형태의 구조이다.
다음과 같은 특징이 있다.
- 데이터를 저장시키는 데 있어서 데이터와 데이터를 1:1 대응 구조로 관계를 맺어 저장시키는 형태의 구조이다.
- 선형 구조는 크게 순차 구조와, 연결 구조로 나눌 수 있다.
- 순차 구조 : 조회가 빠르며 삽입과 제거가 빈번하게 발생하면 성능이 저하된다.
- 연결 구조 : 데이터의 삽입, 삭제가 용이한 방법이다.
- 스택(Stack), 큐(Queue), 데크(Deque), 선형 리스트(Linear List = 연속 리스트, 배열), 연결 리스트(Linked List)가 있다.
- 선형리스트 종류
- 배열을 이용하는 연속 리스트(Continous List)
- 포인터를 이용하는 연결 리스트(Linked List)
- 선형리스트 종류
스택 (Stack)
스택은 영어를 그대로 풀어서 읽은 것 처럼 데이터를 쌓는 자료구조이다.
스택의 구조
- 스택은 그림을 보듯이 바닥부터 데이터를 차곡차곡 쌓아가는 구조이다.
- 데이터를 저장하는 기억 장치가 한쪽으로만 입출력이 일어난다.
= 바닥이 막혀있기 때문에 넣은 곳으로 데이터를 뺀다. - 데이터가 저장될 때 입력된 데이터의 위치를 Stack의 Pointer (Top)가 가리키고 있다.
- Stack 포인터는 데이터가 입력될 때마다 1씩 증가하며, Stack의 크기보다 큰 값을 갖게되면,
OverFlow(말 그대로 넘쳐흘러서 담을 수 없음)가 발생한다. - Stack 포인터는 출력 될 때는 1씩 감소하며, 저장된 데이터가 없을 경우에는 0의 값을 갖게 된다.
- Stack 포인터는 데이터가 입력될 때마다 1씩 증가하며, Stack의 크기보다 큰 값을 갖게되면,
스택의 특징
- 위에서 말한대로 입출력이 같은 쪽에서 이뤄진다.
- 다르게 말하면 처음 들어온 데이터가 마지막에 나가게 되는 후입선출(LIFO : Last In First Out) 구조이다.
- 함수를 호출해 복귀할 때 사용한다. (DFS, 재귀함수에서 사용 됨)
큐(Queue)
큐의 자료 구조
- 큐는 한쪽 방향으로 데이터가 삽입되고, 반대쪽으로 데이터가 삭제되는 구조이다.
- 가장 먼저 들어온 데이터가 가장 먼저 삭제되기 때문에 선입선출(FIFO : First In First Out)의 구조이다.
- 데이터를 입력하는 곳에는 입력 포인터가 가리키고 있다.
- 데이터가 삽입될 때마다 1씩 증가하고, 큐 메모리 크기보다 큰 값을 갖게 되면 OverFlow 상태가 된다.
- 데이터를 출력하는 곳에는 삭제 포인터가 가리키고 있다.
- 데이터가 삭제될 때마다 1씩 증가하고, 삽입 포인터와 크기가 같게 되면 큐의 메모리에 데이터가 비어있는 상태가 된다.
큐의 특징
- 먼저 입력된 데이터가 먼저 출력되는 메모리 사용 방법이다.
- 자료 구조에서도 말 한 것처럼 FIFO 구조이다. 실례로는 은행에서 번호표와 같은 구조이다.
- 프린터 스풀 , 입출력 버퍼에 적합한 자료 구조이다.
- 인터넷에서 동영상 스트리밍에서 사용하는 버퍼구조도 큐 구조를 가지고 있다.
'자격증 > 정보처리기사' 카테고리의 다른 글
자료구조 - 이진 트리 순회 (1) | 2023.05.08 |
---|---|
자료구조 - 비선형구조 : 트리, 그래프 (1) | 2023.04.30 |
자료구조 - 선형구조(2/2) 덱, 선형 리스트, 연결 리스트 (0) | 2023.04.21 |
정보처리기사-소프트웨어의 분류와 특성 (0) | 2022.03.18 |