자료 구조 - 자료구조 개념과 선형구조 (1/2)

자료구조란?

프로그램에서 쉽게 사용될 수 있도록 구성된 데이터 간의 논리적인 관계이다.

 

자료구조의 개념

• 자료를 효율적으로 사용할 수 있도록 컴퓨터에 저장하는 방법이다.
• 처리되는 데이터는 구조를 어떻게 구성하느냐에 따라 성능에 많은 영향을 미친다.
• 데이터를 처리하는 입장에서 데이터 사이에 존재하는 관계이다.

 

효과적으로 설계된 자료구조는 효율적인 프로그래밍을 할 수 있도록 한다.

데이터의 추가, 삭제, 검색을 효율적으로 할 수 있는 적절한 데이터 구조를 사용하는게 중요하다.

 

형태에 따른 자료구조

단순 구조

기본 데이터 타입이다.

• 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의 값을 갖게 된다.

 

스택의 특징

• 위에서 말한대로 입출력이 같은 쪽에서 이뤄진다.
• 다르게 말하면 처음 들어온 데이터가 마지막에 나가게 되는 후입선출(LIFO : Last In First Out) 구조이다.
• 함수를 호출해 복귀할 때 사용한다. (DFS, 재귀함수에서 사용 됨)

 

큐(Queue)

큐의 자료구조

큐의 자료 구조

• 큐는 한쪽 방향으로 데이터가 삽입되고, 반대쪽으로 데이터가 삭제되는 구조이다.
• 가장 먼저 들어온 데이터가 가장 먼저 삭제되기 때문에 선입선출(FIFO : First In First Out)의 구조이다.
• 데이터를 입력하는 곳에는 입력 포인터가 가리키고 있다.
  • 데이터가 삽입될 때마다 1씩 증가하고, 큐 메모리 크기보다 큰 값을 갖게 되면 OverFlow 상태가 된다.
• 데이터를 출력하는 곳에는 삭제 포인터가 가리키고 있다.
  • 데이터가 삭제될 때마다 1씩 증가하고, 삽입 포인터와 크기가 같게 되면 큐의 메모리에 데이터가 비어있는 상태가 된다.

 

큐의 특징

• 먼저 입력된 데이터가 먼저 출력되는 메모리 사용 방법이다.
• 자료 구조에서도 말 한 것처럼 FIFO 구조이다. 실례로는 은행에서 번호표와 같은 구조이다.
• 프린터 스풀 , 입출력 버퍼에 적합한 자료 구조이다.
• 인터넷에서 동영상 스트리밍에서 사용하는 버퍼구조도 큐 구조를 가지고 있다.