자료구조

 

자료 구조 : 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과

저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법등을 연구 분석 

 

선형 구조 : 배열, 선형 리스트, 스택, 큐, 데크

비선형 구조 : 트리, 그래프

 

암기법 [선홍빛스테이크 데크(선형리스트, 스택, 큐, 데크)]

트리, 그래프 제외하면 선형구조임

 

선형 리스트(Linear List)

 

일정한 순서에 의해 나열된 자료 구조

 

• 연속 리스트(Contiguous List) : 연속 되는 기억 장소에 데이터가 차례대로 저장되는 자료 구조 

 

• 연결 리스트(Linked List) : 연속적이지 않는 기억공간에도 저장할 수 있음

 

스택(Stack)

 

리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조

 

후입선출(LIFO : Last In First Out) 방식

 

스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로(Overflow)

더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)

 

 

연산 : 재귀 호출, 후위(Postfix) 표기법, 서브루틴 호출, 인터럽트 처리, 깊이 우선 탐색 등

 

큐(Queue)

 

순서 리스트의 뒤에서 노드가 삽입되고 앞에서 노드가 제거된다

 

선입선출(FIFO : First In First Out) 

 

 

 

데크(Double Ended Queue, 스택과 큐를 합침)

 

선형리스트의 양쪽 끝에서 삽입과 삭제가 모두 가능하다.