[정처기 필기] 자료구조, 스택, 큐, 데크, 트리, 이진트리

자료 구조

• 선형 구조 : 리스트(선형/연결 리스트), 스택, 큐, 데크
• 비선형 구조 : 트리, 그래프

 

선형리스트(Linear List)

• 배열(Array)과 같이 연속되는 기억 장소에 저장되는 리스트이다.
• 가장 간단한 데이터 구조 중 하나로 데이터 항목을 추가/삭제하는 것이 불편하다.

 

연결 리스트(Linked List)

• 노드(Node)의 포인터 부분을 서로 연결시킨 리스트로 연속적인 기억 공간이 없어도 저장이 가능하다.
• 노드의 삽입/삭제가 용이하며 포인터를 위한 추가 공간이 필요하므로 기억 공간이 많이 소요된다.

 

스택(Stack)

• 리스트의 한쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 자료 규조이다.
• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 방식이다.

 

스택가드

메모리상에서 프로그램의 복귀 주소와 변수 사이에 특정 값을 저장해 두었다가 그 값이 변경되었을 경우 오버플로우 상태로 가정하여 프로그램 실행을 중단하는 기술이다.

 

스택의 응용 분야

• 인터럽트 처리, 수식의 계산, 0-주소 지정 방식
• 재귀호출, 후위 표현의 연산, 깊이 우선 탐색

 

큐(Queue)

• 자료 삽입 작업은 선령 리스트의 한쪽 끝에서, 삭제 작업은 다른 쪽 끝에서 수행되는 자료 구조이다.
• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In Fistr Out)방식이다.

 

큐의 응용 분야

운영체제의 작업 스케줄링 등에서 응용 된다.

 

데크(Deque)

• 자료의 삽입과 삭제가 리스트의 양쪽 끝에서 이루어지므로 두 개의 포인터를 사용하는 자료 구조이다.
• 스택과 큐를 복합한 형태이다.
• 입력 제한 데크를 Scroll, 출력 제한 데크를 Shelf라고 한다.

 

트리

그래프의 특수한 형태로써 노드(Node)와 가지(Branch)를 이용하여 사이클을 이루지 않도록 구성한 자료 구조이다.

 

이진트리

차수(Degree)가 2이하인 노드들로만 구성된 트리이다.

 

이진 트리의 운행법

• 전위(Preorder)운행 : Root → Left → Right
• 중위(Inorder)운행 : Left → Root → Right
• 후위(Postorder)운행 : Left → Right → Root

 

수식의 표기법

• 전위(Prefix) 표기법 : 연산자 → 피연산자 → 피연산자 ⇒ +AB
• 중위(Infix) 표기법 : 피연산자 → 연산자 → 피연산자 ⇒ A+B
• 후위(Postfix) 표기법 : 피연산자 → 피연산자 → 연산자 ⇒ AB+

예제

(AB)+(CD)

• 전위 표기 : 연산자 우선순위대로()로 묶어준다
  1. 괄호 앞으로 연산자를 이동한다. ⇒((AB)+(CD)) ⇒ +((AB)(CD))
  2. 괄호를 제거해준다 ⇒ +ABCD
• 후위 표기 : 연산자 우선위대로 ()로 묶어준다.
  1. 괄호 뒤로 연산자를 이동한다. ⇒ ((AB)(CD))+
  2. 괄호를 제거해준다 ⇒ ABCD+