2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행

Presentation on theme: "2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행"— Presentation transcript:

1 2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행
2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행 - TOP : 삽입, 삭제 작업이 수행되는 리스트의 끝 - BOTTOM : 다른 한쪽 끝 - push : TOP 위치로 새로운 노드를 삽입하는 동작 - pop : TOP으로부터 한 노드를 제거하는 동작 * Push-down list S/W개발자를 위한 자료구조

2 2.3 제한 조건을 가진 자료구조 1) 스택의 개념 S/W개발자를 위한 자료구조

3 2.3 제한 조건을 가진 자료구조 1) 스택의 개념 - Stack Pointer - FILO(First-In Last-Out)
2.3 제한 조건을 가진 자료구조 1) 스택의 개념 - Stack Pointer - FILO(First-In Last-Out) LIFO(Last-In First-Out) - 예 : 원통형 동전 케이스, 식기류 등 * subroutine의 복귀주소(return address) 저장, compiler, 산술식 계산 등 S/W개발자를 위한 자료구조

4 2.3 제한 조건을 가진 자료구조 2) 스택의 알고리즘 - 삽입 작업 : TOP ← TOP + 1
2.3 제한 조건을 가진 자료구조 2) 스택의 알고리즘 - 삽입 작업 : TOP ← TOP + 1 - 삭제 작업 : TOP ← TOP - 1 * 스택이 빈 상태(Empty;TOP=0) -> 제거작업 -> 부족현상 발생 * 스택이 포화상태(Full;TOP=n) -> 삽입작업 -> 과잉현상 발생 S/W개발자를 위한 자료구조

5 < 스택의 삽입(push) 작업 알고리즘>
2.3 제한 조건을 가진 자료구조 < 스택의 삽입(push) 작업 알고리즘>   // 스택에 하나의 원소를 삽입     void Stack::Push (const char& item)     {         // 만일 스택이 포화상태이면, 알고리즘을 종료한다.         if (top == MaxStackSize-1)         {             cerr << "Stack Overflow !!" << endl;             exit(1);          }          // 스택 포인터 top의 값을 증가시키고, 스택으로 원소를 복사해 온다.          top++;          stacklist[top] = item;      } S/W개발자를 위한 자료구조

6 < 스택의 삭제(delete) 작업 알고리즘>
2.3 제한 조건을 가진 자료구조 < 스택의 삭제(delete) 작업 알고리즘>     // 스택으로 부터 하나의 원소를 삭제     DataType Stack::Pop(void)     {        DataType temp;         // 만일 스택이 빈 상태이면, 알고리즘을 종료한다.         if (top == -1)         {             cerr << "Stack Underflow !!" << endl;             exit(1);          }          // top의 값을 temp로 옮기고, top의 값을 1만큼 감소한다.          temp = stacklist[top];          top--;          return temp;     } S/W개발자를 위한 자료구조

7 2.3 제한 조건을 가진 자료구조 3) 스택의 삽입과 제거 연산 예 : 스택 크기 = 5,
2.3 제한 조건을 가진 자료구조 3) 스택의 삽입과 제거 연산 예 : 스택 크기 = 5, A,B,C(삽입), C(제거), D,E(삽입), E(제거), F(삽입) S/W개발자를 위한 자료구조

8 2.3 제한 조건을 가진 자료구조 3) 스택의 삽입과 제거 연산 S/W개발자를 위한 자료구조

9 2.3 제한 조건을 가진 자료구조 3) 스택의 삽입과 제거 연산 S/W개발자를 위한 자료구조

10 2.3 제한 조건을 가진 자료구조 4) 스택의 과잉 상태 처리 (1) 하나의 저장 공간에 1개의 스택을 운영하는 경우
2.3 제한 조건을 가진 자료구조 4) 스택의 과잉 상태 처리 (1) 하나의 저장 공간에 1개의 스택을 운영하는 경우 - 가장 간단하고 일반적인 방법 - 과잉상태 : 할당된 저장공간 모두 사용한 상황에서 새로운 노드가 삽입되면 발생 - 해결방법 : 저장공간을 스택에게 다시 할당 * 사전에 삽입과 제거 작업 동향 분석 -> 저장공간의 적정량 부여 S/W개발자를 위한 자료구조

11 2.3 제한 조건을 가진 자료구조 4) 스택의 과잉 상태 처리 (2) 하나의 저장 공간에 2개의 스택을 운영하는 경우
2.3 제한 조건을 가진 자료구조 4) 스택의 과잉 상태 처리 (2) 하나의 저장 공간에 2개의 스택을 운영하는 경우 - 하나의 저장공간에 2개의 스택을 보관, 운영하는 방법 - 두 개의 스택 사이에 유용공간 설정하여 과잉현상 발생시 공용으로 사용하도록 설계 S/W개발자를 위한 자료구조

12 2.3 제한 조건을 가진 자료구조 - 과잉상태 : 두 스택의 TOP이 서로 만나면 발생 (TOP1 = TOP2)
2.3 제한 조건을 가진 자료구조 - 과잉상태 : 두 스택의 TOP이 서로 만나면 발생 (TOP1 = TOP2) - 해결방법 : 유용공간의 크기를 확장 * 장점 : 과잉상태 발생 확률이 줄어 듬 기억공간을 충분히 활용 * 단점 : 3개의 스택, 또는 그 이상의 스택 운영 못함 S/W개발자를 위한 자료구조

13 2.3 제한 조건을 가진 자료구조 (3) 하나의 저장 공간에 n개의 스택을 운영하는 경우 1. 영분배
2.3 제한 조건을 가진 자료구조 (3) 하나의 저장 공간에 n개의 스택을 운영하는 경우 1. 영분배 - 처음 모든 스택의 크기를 0으로 하는 방법 - 단점 : 인접 노드들의 빈번한 이동 발생 과잉상태 해결을 위한 재포장 작업 필요 * 재포장(Repacking) 작업 : 스택 포인터 값을 새로 위치할 곳을 지칭하도록 조정하여 저장공간 재분배하고, 스택 자료들을 옮겨서 재배치하는 작업 -> 과잉상태 해결을 위한 최소한 기억공간 할당(한 노드분) S/W개발자를 위한 자료구조

14 * 하나의 기억 공간에 4개의 스택을 운영하는 예 : 영분배
2.3 제한 조건을 가진 자료구조 * 하나의 기억 공간에 4개의 스택을 운영하는 예 : 영분배 S/W개발자를 위한 자료구조

15 2.3 제한 조건을 가진 자료구조 초기 상태 2. 첫 번째 작업(IA)후 상태 S/W개발자를 위한 자료구조

16 2.3 제한 조건을 가진 자료구조 3. 두 번째 작업(IA)후 상태 4. 세 번째 작업(ID)후 상태
2.3 제한 조건을 가진 자료구조 3. 두 번째 작업(IA)후 상태 4. 세 번째 작업(ID)후 상태 S/W개발자를 위한 자료구조

17 2.3 제한 조건을 가진 자료구조 5. 네 번째 작업(IC)후 상태 6. 다섯 번째 작업(DA)후 상태
2.3 제한 조건을 가진 자료구조 5. 네 번째 작업(IC)후 상태 6. 다섯 번째 작업(DA)후 상태 S/W개발자를 위한 자료구조

18 2.3 제한 조건을 가진 자료구조 7. 여섯 번째 작업(IB)후 상태 8. 일곱 번째 작업(IA)후 상태
2.3 제한 조건을 가진 자료구조 7. 여섯 번째 작업(IB)후 상태 8. 일곱 번째 작업(IA)후 상태 S/W개발자를 위한 자료구조

19 2.3 제한 조건을 가진 자료구조 10. 아홉 번째 작업(IB)후 상태 9. 여덟 번째 작업(IA)후 상태
2.3 제한 조건을 가진 자료구조 9. 여덟 번째 작업(IA)후 상태 10. 아홉 번째 작업(IB)후 상태 S/W개발자를 위한 자료구조

20 2.3 제한 조건을 가진 자료구조 11. 열 번째 작업(ID)후 상태 12. 열한 번째 작업(DB)후 상태
2.3 제한 조건을 가진 자료구조 11. 열 번째 작업(ID)후 상태 12. 열한 번째 작업(DB)후 상태 S/W개발자를 위한 자료구조

21 2.3 제한 조건을 가진 자료구조 13. 열 두 번째 작업(DA)후 상태 - 최종상태 S/W개발자를 위한 자료구조

22 2.3 제한 조건을 가진 자료구조 (3) 하나의 저장 공간에 n개의 스택을 운영하는 경우 2. 균등분배
2.3 제한 조건을 가진 자료구조 (3) 하나의 저장 공간에 n개의 스택을 운영하는 경우 2. 균등분배 - 모든 스택들에게 동일한 크기로 나누어서 분배하는 방법 - 각 스택의 특성 무시하고 분배 : 스택에 따라 남거나, 과잉상태가 자주 발생하는 문제점 S/W개발자를 위한 자료구조

23 2.3 제한 조건을 가진 자료구조 (3) 하나의 저장 공간에 n개의 스택을 운영하는 경우 3. 차등분배
2.3 제한 조건을 가진 자료구조 (3) 하나의 저장 공간에 n개의 스택을 운영하는 경우 3. 차등분배 - 스택들의 이용도 측정하여 그 비율로 분배하는 방법 - 기억공간을 효율적으로 활용 가능 : 스택의 이용도를 정확하게 추정하기 곤란함 S/W개발자를 위한 자료구조

24 2.3 제한 조건을 가진 자료구조 2. 큐(QUEUE) 1) 큐의 개념
2.3 제한 조건을 가진 자료구조 2. 큐(QUEUE) 1) 큐의 개념 - 한 쪽 끝에서 삽입작업, 다른 쪽 끝에서 삭제작업 수행 - REAR(Tail) : 삽입작업 수행되는 위치 포인터 - FRONT(Head) : 삭제작업 수행되는 위치 포인터 S/W개발자를 위한 자료구조

25 2.3 제한 조건을 가진 자료구조 2. 큐(QUEUE) 1) 큐의 개념 - 선입선출 방식
2.3 제한 조건을 가진 자료구조 2. 큐(QUEUE) 1) 큐의 개념 - 선입선출 방식 - FIFO(First-In First-Out) - 매표구 앞에 선 줄, 재고관리 등 * 일괄처리(Batch Processing), Printer 출력 버퍼, 작업 스케줄링(Job scheduling) 등 S/W개발자를 위한 자료구조

26 2.3 제한 조건을 가진 자료구조 2) 큐 알고리즘 - 삽입 작업 : REAR← REAR + 1
2.3 제한 조건을 가진 자료구조 2) 큐 알고리즘 - 삽입 작업 : REAR← REAR + 1 - 삭제 작업 : FRONT← FRONT + 1 * 과잉상태(Overflow), 부족현상(Underflow) 여부 점검! S/W개발자를 위한 자료구조

27 2.3 제한 조건을 가진 자료구조 3) 큐의 삽입과 제거 연산 예 : 큐 크기(n) = 4,
2.3 제한 조건을 가진 자료구조 3) 큐의 삽입과 제거 연산 예 : 큐 크기(n) = 4, A,B,C(삽입), A,B(제거), D(삽입), E(삽입) S/W개발자를 위한 자료구조

28 2.3 제한 조건을 가진 자료구조 3) 큐의 삽입과 제거 연산 S/W개발자를 위한 자료구조

29 2.3 제한 조건을 가진 자료구조 3) 큐의 삽입과 제거 연산 * 유용공간이 있어도 과잉상태가 발생되는 모순!!
2.3 제한 조건을 가진 자료구조 3) 큐의 삽입과 제거 연산 * 유용공간이 있어도 과잉상태가 발생되는 모순!! S/W개발자를 위한 자료구조

30 2.3 제한 조건을 가진 자료구조 4) 큐의 과잉상태 처리 1. 이동 큐(Moving Queue)
2.3 제한 조건을 가진 자료구조 4) 큐의 과잉상태 처리 1. 이동 큐(Moving Queue) - 기존에 삭제된 기억장소를 사용하는 방법 - 비어 있는 앞부분으로 뒷부분 노드를 이동시키고, 뒤에 남아 있는 공간에 새로운 노드 삽입 - 운영과정 : 1) 과잉상태 발생시, FRONT 포인터 검색하여 가용공간 존재여부 판단 2) 가용공간이 없으면, 과잉상태 -> 재포장 작업 수행 3) 가용공간이 있으면, 뒷부분 노드들을 앞으로 이동 4) 이동된 위치에 맞게 포인터 값을 수정 S/W개발자를 위한 자료구조

31 2.3 제한 조건을 가진 자료구조 1. 이동 큐(Moving Queue) - 장점 : 가용공간 모두 사용
2.3 제한 조건을 가진 자료구조 1. 이동 큐(Moving Queue) - 장점 : 가용공간 모두 사용 - 단점 : 이동 시간이 많이 소요 처리가 복잡 S/W개발자를 위한 자료구조

32 2.3 제한 조건을 가진 자료구조 2. 환형 큐(Circular Queue) - 이동 큐 방법의 빈번한 이동 문제 해결
2.3 제한 조건을 가진 자료구조 2. 환형 큐(Circular Queue) - 이동 큐 방법의 빈번한 이동 문제 해결 - 원형 상태로 생각하여 운영 : 마지막 노드 부분(색인번호 n) 다음에, 처음 노드(색인번호 1)가 위치하는 것으로 가정하고 운영 - 환형 리스트(Circular List) S/W개발자를 위한 자료구조

33 2.3 제한 조건을 가진 자료구조 2. 환형 큐(Circular Queue)
2.3 제한 조건을 가진 자료구조 2. 환형 큐(Circular Queue) 예 : 그림 2.27(g)에 연속해서 E(삽입), C,D,E(제거) 작업 S/W개발자를 위한 자료구조

34 2.3 제한 조건을 가진 자료구조 2. 환형 큐(Circular Queue)
2.3 제한 조건을 가진 자료구조 2. 환형 큐(Circular Queue) * F=R 상태 구별 모호 : 빈 상태? 한 개의 노드로 구성? S/W개발자를 위한 자료구조

35 2.3 제한 조건을 가진 자료구조 3. 변형된 환형 큐 - 환형 큐 문제 해결 방안 - 포인터 R : 최근에 입력된 노드 지칭
2.3 제한 조건을 가진 자료구조 3. 변형된 환형 큐 - 환형 큐 문제 해결 방안 - 포인터 R : 최근에 입력된 노드 지칭 포인터 F : 최근에 제거된 노드 지칭 * 한 노드분 사용 못함(최대 n-1개 노드 저장) - 빈 상태 : F = R S/W개발자를 위한 자료구조

36 2.3 제한 조건을 가진 자료구조 예 : 스택 크기(n) = 4,
2.3 제한 조건을 가진 자료구조 예 : 스택 크기(n) = 4, A,B,C(삽입), A,B(제거), D,E(삽입), C,D,E(제거) S/W개발자를 위한 자료구조

37 2.3 제한 조건을 가진 자료구조 3. 변형된 환형 큐 S/W개발자를 위한 자료구조

38 2.3 제한 조건을 가진 자료구조 3. 변형된 환형 큐 S/W개발자를 위한 자료구조

39 2.3 제한 조건을 가진 자료구조 3. 데크(DEQUE) 1) 데크의 개념 - DEQUE ; Double-Ended QUEue
2.3 제한 조건을 가진 자료구조 3. 데크(DEQUE) 1) 데크의 개념 - DEQUE ; Double-Ended QUEue - STACK + QUEUE - 리스트의 양쪽 끝에서 삽입, 삭제작업 수행 S/W개발자를 위한 자료구조

40 2.3 제한 조건을 가진 자료구조 * 데크의 삽입과 삭제 작업 예 : 중앙에서부터 노드 저장
2.3 제한 조건을 가진 자료구조 * 데크의 삽입과 삭제 작업 예 : 중앙에서부터 노드 저장 데크 크기(n) = 5, A,B,C,D(삽입), C(제거), E(삽입) S/W개발자를 위한 자료구조

41 2.3 제한 조건을 가진 자료구조 * 데크의 삽입과 삭제 작업 예 S/W개발자를 위한 자료구조

42 2.3 제한 조건을 가진 자료구조 2) 변형된 데크 1. 입력 제한 데크(Input Restricted Deque) : SCROLL S/W개발자를 위한 자료구조

43 2.3 제한 조건을 가진 자료구조 2) 변형된 데크 2. 출력 제한 데크(Output Restricted Deque) : SHELF S/W개발자를 위한 자료구조