자료구조: CHAP 5 스택 2017. 5. 4 순천향대학교 컴퓨터공학과 하 상 호.

Slides:



Advertisements
Similar presentations
Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
Advertisements

1 08 배열. 한국대학교 객체지향연구소 2 C 로 배우는 프로그래밍 기초 2 nd Edition 배열  동일한 자료유형의 여러 변수를 일괄 선언  연속적인 항목들이 동일한 크기로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는.
스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).
이진 나무 구조 강윤섭 2008년 5월 23일.
제 5 장 stack and queue.
2장. 프로그램의 기본 구성. 2장. 프로그램의 기본 구성 2-1"Hello, World!" 들여다 보기 /* Hello.c */ #include int main(void) { printf("Hello, World! \n"); return 0;
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
4장 스택.
7 스택.
스택(stack) SANGJI University Kwangman Ko
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
제 5 장. 스택(Stack).
Chapter 06. 스택.
제3장 스택과 큐.
Heesang kim PL/SQL 3 Heesang kim.
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
C++ Espresso 제12장 템플릿.
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 7 트리(1) 순천향대학교 컴퓨터공학과 하 상 호.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
Chapter 07. 기본 함수 익히기.
2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행
제 4 장 스택과 큐 4.1 스택(stack) 4.2 스택의 활용 4.3 큐 4.4 데큐.
11장. 1차원 배열.
Introduction To Data Structures Using C
C#.
CHAP 10:그래프 (2) 순천향대학교 하상호.
JA A V W. 03.
자바 5.0 프로그래밍.
어서와 C언어는 처음이지 제14장.
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
4th HomeWork Guide (ver2.0)
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
연산자 (Operator).
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
2장. 변수와 타입.
제 3 강.
C언어 응용 제7주 실습 해보기 제6장.
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
8주차: Strings, Arrays and Pointers
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
계산기.
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
알고리즘 알고리즘이란 무엇인가?.
알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 하 상 호.
에어 PHP 입문.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
7주차: Functions and Arrays
생체 신호의 실시간 디지털 처리 7조 홍윤호( )-1등
Chapter 10 데이터 검색1.
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
Summary of Pointers and Arrays
3장 (2) 구문과 의미론 순천향대학교 컴퓨터공학과 하상호.
김선균 컴퓨터 프로그래밍 기초 - 12th : 문자열 - 김선균
어서와 C언어는 처음이지 제21장.
컴퓨터는 어떻게 덧셈, 뺄셈을 할까? 2011년 10월 5일 정동욱.
C++ Espresso 제15장 STL 알고리즘.
6 객체.
Prof. Kyungshik Lim Kyungpook National University
Presentation transcript:

자료구조: CHAP 5 스택 2017. 5. 4 순천향대학교 컴퓨터공학과 하 상 호

스택이란? 스택(stack): 쌓아놓은 더미

스택의 특징 삽입, 삭제가 한 쪽 끝에서만 이루지도록 제한 후입선출(LIFO:Last-In First-Out): 가장 최근에 들어온 데이터가 가장 먼저 나감. C A B D

스택의 구조 요소(element) 스택 상단(top) C B A 스택 하단(bottom)

스택의 ADT 객체: 0개 이상의 원소를 가진 유한 순서 리스트 연산: s: 스택, item: 원소 create_stack() ::= 빈 스택 생성 is_empty(s) ::= if (s가 비어 있으면) then return true else return false is_full(s) ::= if (s가 꽉 차있으면) then return true push(s, item) ::= s의 상단에 item을 삽입 pop(s) ::= if (is_empty(s)) then return error else s의 상단의 항목을 삭제하여 반환 peek(s) ::= if (is_empty(s)) then return error else s의 상단의 항목을 반환 delete(s) ::= if (is_empty(s)) then return error else s의 상단의 항목을 삭제

스택의 ADT 스택 사용 프로그램 // 스택 정의 procedure main() create_stack(); // 스택 생성 // 스택에 값 저장 push(1); push(2); push(3); // print stack while (!is_empty() ) do print( pop() ); repeat end main

스택의 연산 삽입(push), 삭제(pop) 초기상태 push(A) push(B) push(C) pop() A B C

스택의 용도 입력 순서와 역순의 출력이 필요한 경우 함수 호출 편집기에서 undo 기능

스택 표현 배열 리스트 4 9 3 top 2 top 9 7 1 7 3 3 NULL 리스트 배열

스택 구현: 배열 1차원 배열로 표현 스택 크기 원소의 타입 element stack[n]; int top; 스택 상단 표시 4 4 4 top 3 3 3 2 2 top 2 1 1 1 -1 top -1 -1 공백상태 포화상태

스택 구현 배열 create_stack() { element stack[n]; // 인덱스 범위: 0 ~ n-1 top <- -1; } is_empty(stack) if (top < 0)then true else return false; is_full(stack) is(top >= n-1) then return true; 4 3 2 top 9 1 7 3 배열

스택 구현: 배열 4 3 2 1 top 4 3 2 top 1 push(stack, item) { 2 1 4 3 top push(stack, item) { if (is_full(stack)) then stack_full(); else { top <- top + 1; stack[top] <- item; } pop(stack) if (is_empty(stack)) then stack_empty(); item <- stack[top]; top <- top – 1; return item; 2 1 4 3 top

스택 구현: 리스트 리스트 create_stack() { top <- null; } is_empty(stack) if (top = null )then return true else return false; push(stack, item) // item 포함 노드의 생성 및 최상단에 위치 pop(stack) // 최상단 노드의 데이터 반환 9 top 7 3 NULL 리스트

C: 스택 타입 정의 프로그램에서 여러 개의 스택 사용시 편리 스택 연산 표현 (C 코드) void init(stack_type *s) int is_empty(stack_type s) int is_full(stack_type s) void push(stack_type *s, element item) element pop(stack_type *s) define MAX_STACK_SIZE 100 typedef int element ; typedef struct { element stack[MAX_STACK_SIZE]; int top; } stack_type;

스택 응용 괄호 검사 수식 계산 미로 탐색

스택 응용: 괄호 검사 수학 수식은 소괄호, 중괄호, 대괄호를 사용하여 표현 다음 수식에서 괄호의 쌍이 올바른가?  

스택 응용: 괄호 검사 수학 수식에서 괄호 검사 조건 예제: 다음 수식에서 괄호가 올바르게 사용되었는가? 왼쪽 괄호의 개수와 오른쪽 괄호의 개수는 동일 같은 유형의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나온다. 괄호 사이에는 포함관계만 존재한다. 예제: 다음 수식에서 괄호가 올바르게 사용되었는가? 주어진 수식으로부터 괄호를 어떻게 검사하는가? { a[(i+1)] = 0; } if ((i==0) && (j == 0) a[(i+1]) = 0;

스택 응용: 괄호 검사 스택을 이용한 수식 괄호 검사 알고리즘 개요 왼쪽 괄호가 나오면 스택에 삽입 오른쪽 괄호가 나오면 스택으로부터 원소를 삭제하여 반환된 괄호와 동일한 유형인지를 검사. 수식 끝에 도달하였고 스택이 비어 있으면, 수식 괄호는 올바르게 사용된 경우임 스택에 삽입 스택에서 꺼내어 비교 { a[(i+1)] = 0; } if ((i==0) && (j == 0) a[(i+1]) = 0;

스택 응용: 괄호 검사 다음 수식을 스택을 이용하여 괄호 검사하라. { a[(i+1)] = 0; }

스택 응용: 괄호 검사 다음 수식을 스택을 이용하여 괄호 검사하라. if ((i==0) && (j == 0)

스택 응용: 괄호 검사 (1) 알고리즘 paren_test(exp: array [1..SIZE] of characters) // 수식에 괄호‘(‘만을 포함한다고 가정 // 수식 괄호가 올바르면 true, 그렇지 않으면 false 반환 // 스택 s를 가정 { while (exp의 끝에 도달하지 않았으면) do symbol <- get_symbol(); // exp의 다음번째 문자 repeat // 스택이 비어 있는지 유무 고려 }

스택 응용: 괄호 검사 (2) 알고리즘 paren_test(exp: array [1..SIZE] of characters) // 수식에 괄호가 ‘(‘, ‘]’, ‘}’을 포함한다고 가정 // 수식 괄호가 올바르면 true, 그렇지 않으면 false 반환 // 스택 s가 정의되어 있다고 가정 { while (exp의 끝에 도달하지 않았으면) do symbol <- get_symbol(); // exp의 다음번째 문자 case symbol = ‘(‘ or ‘[‘ or ‘{‘: symbol = ‘)’: symbol = ‘]’: symbol = ‘}’: end case repeat if is_empty(stack) then return true; else return false; end if } 알고리즘

폴랜드 논리학자 Jan Lucasiewicz이 고안하여 폴리쉬 표기법(polish notation)이라고도 함 스택 응용: 수식 계산 폴랜드 논리학자 Jan Lucasiewicz이 고안하여 폴리쉬 표기법(polish notation)이라고도 함 수식 표기법 다음 수식의 후위식 표기법(postfix notation)은? A+B*C-D/E +*ab5 ++127

수식 계산 후위 표기식의 이점은? 연산 순서가 간단 괄호가 필요없다 => 컴퓨터는 중위식을 후위식으로 변환하여 수식 계산 중위식을 후위식으로 어떻게 변환하는가? 후위식을 어떻게 평가하는가?

후위 식 평가 다음 후위 식을 평가하라. (Hint 스택 이용) 8 2 / 3 – 3 2 * +

후위 식 평가 1 2 3 8 / - 4 피연산자-> 삽입 연산자-> 8/2=4 삽입 연산자-> 4-1=1 삽입 1 2 3 8 / - 4 피연산자-> 삽입 연산자-> 8/2=4 삽입 연산자-> 4-1=1 삽입 종료->전체 연산 결과=1

후위 식 평가 알고리즘 eval_postfix(exp: array [1..size] of characters) // 후위식 exp를 평가하여 그 결과를 반환 // 스택 생성 및 초기화 while (exp의 끝에 도달하지 않았으면) do token <- get_token(exp); case { token = operand: token = operator: endcase repeat return pop(stack)); // 결과값 반환 end eval_postfix 수치가 두자리 이상이면?

후위 표기식 변환 방법 1 (수동변환) 후위 표기식을 연산자 기준(우선순위 반영)으로 완전히 괄호로 묶는다. 각 연산자를 묶고 있는 괄호의 오른쪽 괄호 밖으로 연산자를 이동 괄호를 모두 제거한다. 예제: A + B * C – D / E 수식을 한번 읽어가면서 변환 가능한가?

후위 표기식 변환 방법 2 (스택을 이용한 자동변환) 식을 읽어가면서 피연산자는 바로 출력 연산자는 스택에 넣어두고, 적절한 시기에 스택에서 꺼내어 출력 예제: A + B * C A * B + C (A+B) * C A + B * C – D / E A * (B + C) / D 연산자를 언제 출력하는가? 괄호는 어떻게 처리하는가?

후위 표기식 변환 연산자를 언제 스택에 넣고, 꺼내는가? 수식에서 읽어들인 연산자와 스택 상단의 연산자간의 우선순위를 비교하는 것이 필요 수식상의 연산자 우선순위(PIE), 스택상의 연산자 우선순위(PIS) If (PIE <= PIS) then 스택 상단의 연산자를 꺼내어 출력하고, 이 과정을 반복 (다시 스택 상단의 연산자의 비교) else 수식상의 연산자를 스택 상단에 저장 예제: A + B * C – D / E

후위 표기식 변환 괄호는 연산자처럼 취급: A * (B + C) / D 왼쪽 괄호 오른쪽 괄호는? 연산자 PIS PIE 수식상의 왼쪽 괄호는 무조건 스택에 저장 (우선순위를 가장 높게) 스택 탑이 왼쪽 괄호일 때 수식상의 연산자는 무조건 스택에 저장 (우선순위를 가장 낮게) 오른쪽 괄호는? 해당 왼쪽 괄호가 스택에서 꺼내질 때까지 스택상의 연산자를 출력 대응되는 왼쪽 괄호는 단순히 제거 연산자 PIS PIE *, / 2 +, - 1 ( 3

후위 표기식 변환 예제: 다음 식을 스택을 이용하여 후위식으로 변환하라. (a+b) *c a*(b+c)/d

후위식 변환 알고리즘 postfix(exp) while (exp의 끝이 아니면) do token <- get_token(exp); //토큰은 연산자, 피연산자 또는 괄호 case token = operand: print(token); token = operator: token = “)”: endcase repeat while (스택이 빌 때까지) do print(pop(stack)); end postfix

문제 다음 식을 후위 표기법으로 변환하라: 변환 과정시 스택의 상태를 보여라. 여러분은 스택에 항목의 삽입, 삭제시 그 상태를 보여야 한다. 5 * [(10+2) % 2] 위에서 변환된 후위 표기법을 평가하라. 평가 과정시 스택의 상태를 보여라. 여러분은 스택에 항목의 삽입, 삭제시 그 상태를 보여야 한다.

예제: 후위 표기식 변환 예제: 다음 식을 스택을 이용하여 후위식으로 변환하라. 5 * (10+2) % 2 a / b – c + d * e – a * c 2 * { 3 + [(1+2)*4] – 5}

스택 응용: 미로 탐색 하나의 입구에서 출발하여 여러 갈림길을 거쳐서 하나 밖에 없는 출구까지의 경로를 찾는 문제 입구 미로를 어떻게 표현할 것인가? 어떻게 경로를 찾아가게 할 것인가? 입구

미로 탐색 해결 방법(시행착오방법) 하나의 경로를 선택하여 시도하고, 안되면 다른 경로를 시도 => 가능한 다른 경로를 어딘가에 저장하는 것이 필요 => 경로가 막혔을 경우에 어떤 다른 경로를 취할 것인가? 한번 시도된 경로는 다시 시도하면 안되게 => 시도된 경로를 표시해 둔다

미로 탐색 해결 스택을 이용 현재 가능한 다른 모든 경로들을 스택에 저장해 두고, 길이 막힌 경우에 스택으로부터 다른 경로를 가져와서 재시도

미로 표현 2차원 배열로 표현 벽은 1로 표현 1: 막혀있는 벽 0: 이동 가능 위치 M*n의 미로 => (m+2)*(n+2)의 미로로 표현 입구: maze[1,1], 출구: maze[m, n] 1 m x 입구 출구

미로 탐색 알고리즘 이동 가능 위치 이미 방문된 위치 표기 현재위치 X: (i, j) 북: (i-1, j), 동(I, j+1), 남(i+1, j), 서(i, j-1) 이미 방문된 위치 표기 Maze[]의 해당 위치의 원소 값을 ‘.’으로 변경 또는 별도의 mark[] 배열을 사용 N E W X S

미로 탐색 알고리즘 Maze_path() stack_type s; int maze[m+2, n+2]; // 스택 s, 미로 maze 초기화 // 입구를 현재 위치로 설정 while (현재 위치가 출구가 아니면) do 현재 위치를 방문한 것으로 표시; if (현재 위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고, 이동 가능하면) then 그러한 위치들을 모두 스택에 저장 endif if (스택이 비어 있으면) then print(“실패”); else 스택에서 한 위치를 꺼내어 현재 위치로 만든다 repeat print(“성공”); end maze_path