개발새발

정보처리기사를 공부하려던 계기중 하나인 자료구조 파트!

중요하니까 적어두자

필기 제 2과목 소프트웨어 개발

데이터 입출력 구현 A

자료구조란?

자료의 표현, 연산을 의미한다

크게 선형구조 와 비선형 구조로 나뉘며,

세부적으로 선형 구조의 종류에는 리스트, 스택, 큐, 데큐 (데크)

비선형 구조의 종류에는 트리와 그래프가 있다

먼저 선형구조부터 살펴 보겠다

리스트 Linear List

리스트 안에서도 선형 리스트와 연결 리스트로 나뉜다

이미지 갤탭 이용해 삽입하기

스택 Stack

이미지 삽입 예정

한쪽으로 들어와 한쪽으로 나가는 구조이며

상단을 Top, 하단을 Bottom 이라한다

입력은 push, 출력은 pop 이라 명칭하며

입력은 ABCD, 출력은 DCBA 순서로 진행된다

LIFO, FILO 구조라고도 한다

입력 (삽입) 알고리즘

Top = Top + 1
if (Top>n) then overflow;
else 삽입

출력 (삽입삭제) 알고리즘

if (Top=0) then underflow;
else {삭제 Top = Top - 1
}

=> 산술식 표현, 함수, 인터럽트 복귀 주소에서 활용한다

큐 Queue

이미지 삽입 예정

오른쪽으로 들어와 왼쪽으로 나가는 구조이다

입력이 되는 오른쪽을 Rear

출력이 되는 왼쪽을 Front 라 한다

입력, 출력이 ABCD 동일순서로 진행된다

LILO, FIFO 구조라고도 한다

입력 (삽입) 알고리즘

r=r+1

출력 (삽입 삭제) 알고리즘

f=f+1

=> 작업 스케줄링, 버퍼관리에서 활용한다

데큐 (데크) Deque (Double-ended Queue)

이미지 삽입 예정

큐와 동일한 구조면서

양방향에서 출력과 입력이 들어올수 있는 구조이다

입력 제한 데크 스크롤 Scroll

한쪽에서만 입력이 가능하도록 한쪽 방향의 입력을 막는다 (출력을 양방향 가능하다)

출력 제한 데크 쉘프 Shelf

한쪽에서만 출력이 가능하도록 한쪽 방향의 출력을 막는다 (출력을 양방향 가능하다)