[2019.04.03] 자료구조-Stack, Queue, Linked List 개념

자료구조는 크게 두 가지로 나뉜다.

• 선형구조 : 스택, 큐, 링크드 리스트 등
• 비선형 구조 : 트리, 그래프, 해시 테이블

# Stack

직접 그려본 Stack 저장공간과 방식

스택은 저장공간에 맨 처음 들어온 데이터가  맨 아래쪽에 놓이며, 그다음에 들어온 데이터가 차례대로 위로 쌓인다. 그리고 해당 저장공간에서 맨 위에 쌓여있는 데이터부터 하나씩 차례대로 꺼내 사용하게 된다. 현재 저장할 수 있는 곳을 가리키는 인덱스 변수인 top을 사용하여, 데이터가 들어오면 top이 가리키는 위치에 저장 후, top +1을 하여 다음 주소를 가리키게 한다.

맨 마지막에 들어온 데이터가 제일 처음으로 꺼내 사용 가능하기 때문에 Last in First out 방식이라 한다.

• 용도 : 함수를 호출하는 순서 저장, 인터럽트가 발생하여 복귀주소 저장, 컴파일러를 이용하여 언어 번역 시 사용.
• 특징 : 데이터 입출력이 빠름. 데이터 중간에 삽입, 삭제 불가능. 처음 스택 선언 시 미리 정해진 공간을 할당해주어야 함.

 

- 수도코드 작성

# Queue

직접 그려본 queue 저장공간과 방식

큐는 저장공간에 데이터를 넣으면 맨 앞 자리로 간다. 그다음 데이터가 들어오면 이전에 들어온 데이터 뒤쪽에 저장된다. 그렇게 데이터가 차례대로 들어온 순서대로 줄을 서듯이 뒤쪽으로 저장이 된다. 데이터를 꺼내 쓸 때는 맨 앞에 있는 데이터부터 차례대로 꺼내 쓰게 된다. 
들어오는 데이터는 Rear라는 변수가 가리키는 위치에 저장하게 한다. 데이터를 가져올 때는 Front라는 변수가 가리키는 데이터부터 빠지게 된다. 만약 Front, Rear이 저장공간의 마지막 인덱스에 위치하게 되면, 다시 첫번째 인덱스부터 시작하게 된다.

맨 처음에 들어온 데이터가 제일 처음으로 꺼내 사용하게 되므로 First in First out 방식이라 한다.

• 용도 : 업무 처리 대기 행렬에서 주로 사용
• 특징 : 입출력이 빠름. 중간에 데이터 삽입, 삭제 불가능. 처음 큐 선언 시 미리 공간을 할당해주어야 함.

 

- 수도코드 작성

# Linked List

링크드 리스트는 순서대로 연결되어 있는 리스트이다. 리스트로 연결되어 있는 각 노드마다 '실제 데이터 공간', '주소 데이터 공간'을 가지게 된다.

실제 데이터 공간에는 해당 노드에 실제로 들어갈 공간을 저장한다. 주소 데이터 공간에는, 자신이 아닌, 내 앞에 있는 노드의 주소를 저장한다.

주소 데이터 공간에 저장된 주소를 참조하여, 내 앞에 있는 노드를 찾아간다. 

• 용도 : 삽입, 삭제가 잦은 데이터 리스트에 사용
• 특징 : 중간에 데이터 삽입, 삭제 가능. 동적 할당으로 인해 메모리 공간 절약. 실제 공간, 주소 공간 필요. 접근속도가 느림.

 

- 수도코드 작성