추상 데이터 타입 — 스택(stack), 큐(queue), 연결リスト(linked list)

뒤로 가기 버튼과 프린터 대기열

• 방문한 모든 페이지는 스택에 쌓입니다. 뒤로 가기 버튼은 최상단 요소를 제거합니다. 가장 최근에离开한 페이지가 먼저 되돌아옵니다.
• 복도 끝에 있는 프린터는 도착 순서대로 작업을 처리합니다. 처음 보낸 문서는 처음 출력되며, 뒤에 온 작은 문서들조차也不例外합니다.
• 두 가지 구조, 서로 반대되는 규칙, 그리고 break 전까지 두 가지 모두를 사용합니다. 어느 하나도 저장 방식을 명시하지 않으며, 각 연산이 무엇을 하는 것만 설명합니다.
• 이것이 추상 데이터형(ADT) 입니다. 이 수업은 교육 과정에서 언급하는 세 가지 ADT, 각 ADT의 연산, 그리고 특정 상황에 대한 justification 방법을 다룹니다.

ADT란 무엇인가

• 추상 데이터형(ADT)은 데이터의 집합과 해당 데이터에 대한 연산의 집합을 말합니다. 이 한 문장이 1점 정의입니다.
• 연산이 무엇을 하는지에 의해 정의되며, 데이터가 어떻게 저장되는지에 따라 결정되지 않습니다. 구현 방식은 숨겨져 있으므로 변경되어도 사용 코드는 영향을 받지 않습니다.
• 스택, 큐, 연결 리스트, 이진 트리, 배열은 모두 ADT입니다.

스택

• 스택은 항목이 같은 끝, 즉 최상단(top) 에 추가되고 제거되는 목록입니다. 따라서最後に 추가된 항목이最初に 제거됩니다: LIFO(후입선출).
• 연산: push는 최상단에 추가, pop은 최상단에서 제거, peek는 최상단을 확인하며, 비었는지/차 있는지 테스트합니다.
• 활용: Undo 기록, 뒤로 가기 버튼, 함수 호출의 반환 주소, 괄호 매칭, 백트래킹.

모든 연산은 최상단에서 이루어집니다

worked example: 스택 추적

큐

• 큐는 항목이 뒤쪽(rear) 에 추가되고 앞쪽(front) 에서 제거되는 목록입니다. 따라서最初に 추가된 항목이最初に 제거됩니다: FIFO(선입선출).
• 연산: enqueue는 뒤쪽에 추가, dequeue는 앞에서 제거하며, 비었는지/차 있는지 테스트합니다.
• 활용: 인쇄 스풀링, 키보드 버퍼, 스케줄링, 상점의 고객, 너비 우선 탐색(BFS).

뒤에서 연결하고, 앞에서 나갑니다

풀이 예제: 큐에 추가하고 제거하는 방법 설명

연결 리스트

• 연결 리스트는 각 노드(node) 가 데이터 항목과 다음 노드를 가리키는 포인터(pointer) 를 보유하며, 첫 번째 노드를 가리키는 시작 포인터가 있는 목록입니다. 마지막 노드의 포인터는 NULL와 같은 sentinel입니다
• 연산: 삽입, 삭제, 검색 및 트러버서, 헤드에서 시작하여 포인터를 따라 모든 노드를 순서대로 방문합니다.
• 배열에 비해 장점: 삽입이나 삭제가 저렴하며, 포인터만 재연결하면 됩니다. 필요할 때 목록이 확장됩니다. 단점: 무작위 접근이 불가능하며, 열 번째 노드에 도달하려면 아홉 개의 포인터를 따라가야 합니다.

값과 화살표가 반복됨

worked example: 순서에 맞춰 노드 추가하기

선택 근거 제시

• 도착한 순서대로 처리해야 하는 항목들(인쇄 작업, 키 입력, 고객 등): queue, 선입선출(LIFO/FIFO) 원칙 때문입니다.
• 가장 최근 항목을 먼저 처리해야 함(undo, 복귀, 중첩 호출 등): stack, 후입선출(LIFO) 원칙 때문입니다.
• 정렬된 집합의 중간에 자주 삽입하거나 삭제되며 크기가 불분명함: linked list, 포인터만 변경되어 이동이 없기 때문입니다.
• 구조물 이름, 규칙 명칭을 제시하고, 해당 규칙을 상황에 연결하십시오.

ADT와 구현의 차이

• ADT는 동적 특성입니다: push와 pop, enqueue와 dequeue, 삽입 및 트러버싱 등.
• 구현은 저장 방식입니다: 이 과정에서는 배열과 몇 개의 포인터 변수를 사용합니다(다음 수업).
• ADT 관련 질문은 연산과 규칙을 묻고, 구현 관련 질문은 배열, 포인터 및 검증 조건을 묻습니다.

놓칠 수 있는 점

이해했습니다