| English | 의미 |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | 오버플로우 |
| underflow/ˌʌndəˈfləʊ/ | underflow: 하류 |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | circular array: 순환 배열 |
| free list/friː lɪst/ | free list: 빈 목록 |
메모리에 존재하는 stack은 없다
- 컴퓨터를 열고 stack을 찾아보십시오. 찾을 수 없습니다. 메모리는 번호가 매겨진 셀들의 거대한 배열일 뿐이며, 그것이 전부입니다.
- 모든 stack, queue, linked list은 해당 배열에 물건의 위치를 기억하는 두 세 개의 정수 변수를 더한 것입니다. push는 "숫자 하나를 더하고 저장"이며, dequeue는 "셀을 읽고 다른 숫자를 더함"입니다.
- 이 수업 전체가 책상 관리입니다: 어떤 포인터를, 어떤 검증 조건을, 경계에서 무엇을 할 것인가.
- 시험에서는 선언을 설명하고, 몇 가지 연산을 통해 포인터를 따라가며, 검증 조건이 있는 이유를 말해야 합니다.
배열 안의 stack
- 항목들을
Stack[1:MaxSize]에 저장하고, stack이 비어 있을 때는 정수 **Top**이 0입니다. - Push(x):
Top = MaxSize라면 스택이 가득하여 오버플로우이며, 그렇지 않으면Top ← Top + 1과Stack[Top] ← x을 수행합니다. - Pop():
Top = 0라면 스택이 비어 있어 언더플로우이며, 그렇지 않으면Stack[Top]을 반환하고Top ← Top − 1을 수행합니다.
배열은 움직이지 않으며, 오직 Top만 움직입니다
이미 가득 찬 스택에 항목을 푸시하면 스택 ______가 발생합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
오버플로우(Top=MaxSize일 때 푸시), 언더플로우(빈 스택에서 Pop, Top=0).
각 배열 기반 스택 조건에 의미를 매칭하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Top은 항목 수를 세며: 0=비어있음, MaxSize=가득참; 두 가지 오류ケース는 언더플로우와 오버플로우입니다.
worked example: stack 선언 및 초기화
- 최대 50개의 정수를 담을 수 있는 stack을 배열로 구현하기 위한 선언과 초기화를 설명하십시오. [5]
- 항목을 저장할 50개 요소의
INTEGER타입 배열,DECLARE Stack : ARRAY[1:50] OF INTEGER. - push가满了인지 테스트할 수 있도록 50로 설정된 상수 또는 변수
MaxSize. - stack의 최상단을 가리키는
INTEGER포인터,Top. 초기값 0으로 설정되어 stack이 비어 있음을 나타냅니다. pop은 underflow를 위해 이를 체크하고, push는 overflow를 위해 **MaxSize**과 비교합니다.
배열 기반 스택의 선언 및 초기화에 속하는 것을 선택하십시오. 모든 해당 사항을 선택하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
스택에는 하나의 포인터, Top이 필요합니다. front 포인터는 큐에 속합니다.
일반 배열 안의 queue
- 두 개의 포인터: 나가는 다음 항목용
Front, 빈 공간용Rear. Enqueue는 **Rear**에 저장하고 이동시킵니다. Dequeue는 **Front**에서 읽어내고 이동시킵니다. - 두 포인터는 항상 앞쪽으로만 움직이므로, 몇 번의 연산 후 배열 끝에 빠져나가고 시작 부분의 셀들은 비어 사용 불가 상태가 됩니다.
- 해결책은 포인터가wrap around하게 하는 것입니다.
원형 배열
- circular array는 포인터가 마지막 셀을 지나면 첫 번째 셀로 wraparound합니다: 1-based 인덱스를 사용하면,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x):满了이 아닌지 확인;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): 비어 있지 않은지 확인;Queue[Front]반환;Front ← (Front MOD MaxSize) + 1. - 별도의 count를 유지하십시오. queue가 완전히满하거나 완전히 비었을 때 두 포인터는 동일한 상대적 위치에 있으므로, 포인터만으로 두 상태를 구분할 수 없습니다.
마지막 셀 다음에 첫 번째 셀이 오
배열을 사용하여 ADT 구현
FIFO
큐는 FIFO(선입선출)입니다 — 뒤쪽에서 enqueue하고, 전면에서 dequeue합니다.
왜 큐에 원형 배열을 사용합니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
선형 큐는 Front가 tiếnwhile 시작 부분의 셀을 낭비합니다; MOD로 wrap하면 이를 재사용합니다.
원형 큐는 MOD를 사용하여 front/rear 포인터가 wrap되어 배열 시작 부분에서 해제된 셀을 재사용합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
(pointer MOD MaxSize) + 1는 인덱스를 첫 번째 셀로 되돌려주어, 선형 큐가 Front가 지나간 셀을 낭비하지 않게 합니다.
worked example: 포인터를 따라가기
MaxSize = 6을 사용하면:Rear = 5라면,(5 MOD 6) + 1 = 6가 되므로 다음 항목은 6번 셀에 들어갑니다.Rear = 6라면,(6 MOD 6) + 1 = 1가 됩니다: 포인터가 1번 셀로 다시 감니다.- 크기가 5인 배열(인덱스 0~4)에
Front = 3,Rear = 3및 하나의 항목이 저장된 원형 큐가 있습니다. 두 개의 항목을 추가한 후 두 개를 제거합니다. 0 기반 인덱스를 사용하므로 각 이동은(pointer + 1) MOD 5입니다. - 두 번 추가하면
Rear가 이동합니다: 3 → 4, 그 다음 4 → 0, (4 + 1) MOD 5 = 0이기 때문입니다. 두 번 제거하면Front가 이동합니다: 3 → 4 → 0. 하나의 항목이 인덱스 0에 남고, 큐는 배열 시작 부분에서 해방된 셀을 재사용했습니다.
원형 큐가 셀 1~6을 사용하고 Rear = 6일 때, Rear ← (Rear MOD 6) + 1 실행 후 다음 항목은 어디에 들어갑니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
6 MOD 6 = 0, 여기에 1을 더하면 1입니다. 포인터가 배열 시작부로 wrap됩니다.
worked example:Speech algorithm을 말로 설명하기
- 원형 큐에 항목을 추가하는 알고리즘을 설명하십시오. [4]
- 카운트가 크기와 같으면 큐가 가득 차 있다고 보고 정지합니다.
- 그렇지 않으면 리어 포인터에 1을 더합니다; 이제 마지막 인덱스를 초과하면 첫 번째 인덱스로 설정합니다.
- 리어 포인터에 항목을 저장하고 카운트에 1을 더합니다.
원형 큐에 항목을 추가하는 단계를 순서대로 나열하십시오.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
확인, 이동, wrap, 저장, 카운트. wrap이 바로 이 배열을 원형으로 만드는 것입니다.
배열 안의 연결 리스트
- 노드 레코드의 배열을 사용하여, 각
Next인덱스를 가집니다;-1은 끝을 표시합니다.Head인덱스는 첫 번째 노드를 표시하고,-1은 목록이 비어 있을 때 표시됩니다. - 사용되지 않는 슬롯은 데이터 목록이 사용된 것들을 사슬처럼 연결하듯,
FreeListHead에서부터 프리리스트로 사슬처럼 연결됩니다.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- 삽입:
FreeListHead의 슬롯을 가져와, 그 **Value**과 **Next**를 설정한 후, 이전 노드의Next또는 **Head**를 다시 연결합니다. 삭제: 노드를 unlink하고, 해당 슬롯을 프리리스트 앞부분으로 반환합니다.
두 개의 목록이 하나의 배열을 공유합니다: 데이터 목록과 프리리스트
배열 기반 연결リスト에서, 자유 리스트(free list)는:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
자유 리스트는 여분 슬롯을 연결하므로, 삽입 시 하나를 가져올 수 있고 삭제 시 하나를 반환할 수 있습니다. 이는 빈 슬롯들의 두 번째 연결리스트와 같습니다.
worked example: 배열에 저장된 목록에 삽입하기
Data과Pointer배열이 목록 1 → 3 → 4를 유지하며,Start = 1입니다; 인덱스 1에는D40, 인덱스 3에는D32, 인덱스 4에는 null 포인터가 있는D11이 있습니다. 프리리스트는 인덱스 2에서 시작하여 2 → 5로 계속됩니다.D6를D32과D11사이에 삽입하십시오.- 첫 번째 프리 노드인 인덱스 2를 가져와, **
FreeStart**을 해당 포인터인 5로 설정합니다. **D6**을 **Data[2]**에 저장합니다. - **
Pointer[2]**을 **Pointer[3]**이(value 4) 가지는 값으로 설정합니다. 그런 다음 **Pointer[3]**를 2로 설정합니다. - 이제 목록은 1 → 3 → 2 → 4이고 프리리스트는 5 → null입니다. 구현方式是: 데이터용 배열, 포인터용 병렬 배열(또는 레코드 필드), 시작 포인터, 그리고 프리리스트 포인터입니다.
작은 예제에서 D6가 삽입된 후, 자유 리스트는 인덱스 ____에서 시작합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
인덱스 2가 자유 리스트에서 사용되었으므로, FreeStart는 인덱스 2가 가리키던 곳으로 이동하며, 그것은 5였습니다.
리스트에 삽입할 때, 새 노드의 포인터를 설정하기 전에 이전 노드의 포인터를 변경해야 합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
먼저 새 노드의 포인터를 기존 다음 노드로 설정하십시오. 이전 노드를 먼저 재배선화하면 나머지 리스트의 주소가 사라집니다.
놓칠 수 있는 점
- 검사는 먼저: 풀 전이나 푸시/엔큐 전, 빈 전이나 팝/디큐 전.它们在을 설명하십시오;它们是 marks.
- 감기 공식은 인덱스에 의존합니다: 1 기반에서는
(Rear MOD MaxSize) + 1, 0 기반에서는(Rear + 1) MOD Size. 문제의 범위에 맞춰 선하십시오. - 카운트가 풀인 원형 큐와 빈 것을 구별해 줍니다. 포인터만으로는 불가능합니다.
- 이전 노드를 다시 연결하기 전에 새 노드의 **
Next**을 설정하고, 삭제된 노드의 슬롯을 프리리스트로 반환하지 않으면 배열이 접근 불가능한 셀로 천천히 채워질 것입니다.
이해했습니다
- 배열 내 스택:
Stack[1:MaxSize]와 0에서 시작하는Top포인터;Top = MaxSize는 오버플로우,Top = 0은 언더플로우 - 원형 큐:
Front과Rear이 **MOD**로 감기; 풀인지 빈지를 구분하는 별도의 카운트가 있음 - 배열 내 연결 리스트:
Next인덱스를 가진 노드 레코드,Head, 그리고 여분 슬롯을 사슬로 연결하는 프리리스트 - 모든 연산은 체크, 포인터 산술, 저장 또는 읽기의 순서이며, ADT의 행동은 저장 방식에 따라 변하지 않습니다