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

Slides:



Advertisements
Similar presentations
C언어 응용 제 6 주 연결 자료구조.
Advertisements

컴퓨터와 인터넷.
UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
제 5 장 stack and queue.
3 장 stack and queue.
T-tree 엄종진 강원대학교 컴퓨터과학과.
제14장 동적 메모리.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
Chapter 05. 연결 자료 구조.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
자료구조 실습 (03분반)
제3장 스택과 큐.
스택(stack) SANGJI University Kwangman Ko
제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식.
Chapter 4 스택, 큐, 데크.
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
제 5 장. 스택(Stack).
Chapter 06. 스택.
제3장 스택과 큐.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
Dynamic Memory and Linked List
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
C++ Espresso 제12장 템플릿.
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
보조저장장치 구조(Secondary Storage Structure)
제 4 장 스택과 큐 4.1 스택(stack) 4.2 스택의 활용 4.3 큐 4.4 데큐.
명령어 구조 컴퓨터 하드웨어의 구성 프로그램 명령어 프로그램 실행 동작.
Introduction To Data Structures Using C
자바 5.0 프로그래밍.
자기참조 구조체(1) 먼저 자신과 같은 형의 구조체를 포인트하는 포인터 멤버 필드를 갖는 구조체를 정의한다.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
4th HomeWork Guide (ver2.0)
메모리 관리 & 동적 할당.
Java의 정석 제 5 장 배 열 Java 정석 남궁성 강의 의
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
* 프로그램을 간단히 하기 위해 malloc 성공체크는 안 함
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
USN(Ubiquitous Sensor Network)
논리회로 설계 및 실험 5주차.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
C언어 응용 제7주 실습 해보기 제6장.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
문자열 컴퓨터시뮬레이션학과 2015년 봄학기 담당교수 : 이형원 E304호,
리스트(List)를 이용한 자료 관리 이점숙 /
제 3장 스택과 큐.
Canary value 스택 가드(Stack Guard).
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
알고리즘 알고리즘이란 무엇인가?.
데이터 동적 할당 Collection class.
자료구조론 8장 큐(queue).
소리 편집 안 재 형.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
Chapter 10 데이터 검색1.
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제 4 장 Record.
제 2장 연결리스트.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
개정판 누구나 즐기는 C언어 콘서트 제13장 동적 메모리 출처: pixabay.
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
C++ Espresso 제15장 STL 알고리즘.
7 생성자 함수.
제 4 장. 리스트(List).
Presentation transcript:

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

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

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개발자를 위한 자료구조

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

< 스택의 삽입(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개발자를 위한 자료구조

< 스택의 삭제(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개발자를 위한 자료구조

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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