o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

Transcription

1 스택 (stack) SANGJI University Kwangman Ko

2 o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

3 o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입 (push) 과삭제 (pop) 가발생 ~ top 의위치는동작에따라유동적으로변함 ~ top 의값이스택포인터 (stack pointer) 라고하는레지스터 (register) 에저장 ~ top 의반대편끝을 bottom - 3 -

4

5 o 삽입 (push), 삭제 (pop) 스택의연산 push(a) push(b) push(c) pop() C B B B A A A A 초기상태 - 5 -

6 o 삽입 (push) ~ 스택에새로운자료를삽입하는연산 ~ 항상 top에서발생. ~ 자료를추가하기전에 top 값을 1 증가시킨후자료를삽입 ~ 이미수용할수있는스택의공간이꽉차있으면오버플로우 (overflow) 가발생 - 6 -

7 o 삭제 (pop) ~ 스택에서자료를제거하는연산 ~ 항상 top에서발생. ~ top이가리키고있는자료를삭제한후 top 값을 1 감소 ~ top 값이 -1이라면스택은제거할자료가하나도없는공백 (empty) 상태 - 7 -

8 o is_empty(s) ~ 스택이공백상태인지검사 o is_full(s) ~ 스택이포화상태인지검사 o create() ~ 스택을생성 o peek(s) ~ 스택의 top에위치한자료의값을단순히읽어오는연산 ~ 해당자료를제거하거나 top 값을변경하지않음. c.f.) pop 연산은요소를스택에서완전히삭제하면서가져옴

9 스택의용도 o 입력과역순의출력이필요한경우 ~ 에디터에서되돌리기 (undo) 기능 ~ 함수호출에서복귀주소기억 1 20 int main() { int i=3; sub1(i);... } sub2 PC=200 b= int sub1(int a) { int j=5; sub2(j);... } sub1 PC=100 a=3 sub1 PC=150 a=3 j=5 sub1 PC=151 a=3 j=5 200 void sub2(int b) {... } main PC=1 main PC=20 i=3 main PC=20 i=3 main PC=20 i=3 main PC=21 i=3 시스템스택 시스템스택 시스템스택 시스템스택 시스템스택 - 9 -

10 배열을이용한스택구현 o 1 차원배열, stack[ ] ~ top 변수 : 스택에가장최근에입력되었던자료포인터 ~ stack[0] : 가장먼저들어온요소 ~ stack[top] : 가장최근에들어온요소 ~ 스택이공백상태, top = top top top 포화상태

11 is_empty, is_full 연산 is_empty(s) if top = -1 then return TRUE else return FALSE is_full(s) if top = (MAX_STACK_SIZE-1) then return TRUE else return FALSE top -1 top -1 공백상태포화상태

12 push 연산 push(s, x) if is_full(s) then error "overflow" else top top+1 stack[top] x top top

13 pop 연산 pop(s, x) if is_empty(s) then error "underflow" else e stack[top] top top-1 return e top top

14 연결리스트로스택구현 o 연결된스택 (linked stack) ~ 연결리스트를이용하여구현한스택 ~ 장점 : 크기가제한되지않음 ~ 단점 : 구현이복잡하고삽입이나삭제시간이오래걸린다 top N

15 연결된스택정의 typedef int element; typedef struct StackNode { element item; struct StackNode *link; } StackeNode; typedef struct { StackNode *top; } LinkedStackType;

16 연결된스택에서 push 연산 top C (2) (1) B temp D A NULL

17 void push(linkedstacktype *s, element item) { } StackNode *temp= (StackNode *)malloc(sizeof(stacknode)); if( temp == NULL ){ } else{ } fprintf(stderr, " 메모리할당에러 \n"); return; temp->item = item; temp->link = s->top; s->top = temp;

18 연결된스택에서 pop 연산 top temp C B A NULL

19 element pop(linkedstacktype *s) { } if( is_empty(s) ) { } else{ } fprintf(stderr, " 스택이비어있음 \n"); exit(1); StackNode *temp=s->top; int item = temp->item; s->top = s->top->link; free(temp); return item;

20 o 수식의표기방법 : 스택응용 : 수식의계산 ~ 전위 (prefix), 중위 (infix), 후위 (postfix) 중위표기법 전위표기법 후위표기법 2+3*4 +2*34 234*+ a*b+5 +5*ab ab*5+ (1+2) o 컴퓨터에서의수식계산순서 ~ 중위표기식-> 후위표기식-> 계산 ~ 2+3*4 -> 234*+ -> 14 ~ 모두스택을사용

21 o 방법 후위표기식의계산 ~ 왼쪽에서오른쪽으로스캔 ~ 피연산자, 스택에푸쉬 ~ 연산자, 피연산자를스택에서팝, 연산실행 ~ 연산결과를다시스택에푸쉬 o 예, 82/3-32*

22 토큰 스택 [0] [1] [2] [3] [4] [5] [6] / *

23 8 2 / / / 피연산자 -> 삽입피연산자 -> 삽입연산자 -> 8/2=4 삽입

24 8 2 / / / 피연산자 -> 삽입연산자 -> 4-1=1 삽입종료 -> 전체연산결과 =1-24 -

25 후위표기식계산알고리즘 스택 s 를생성하고초기화한다. for 항목 in 후위표기식 do if ( 항목이피연산자이면 ) push(s, item) if ( 항목이연산자 op 이면 ) then second pop(s) first pop(s) result first op second push(s, result) final_result pop(s);

26 eval(char exp[]) { int op1, op2, value, i=0; int len = strlen(exp); char ch; StackType s; init(&s); for( i=0; i<len; i++){ } ch = exp[i]; if( ch!= '+'&& ch!= '-' && ch!= '*' && ch!= '/' ){ } value = ch - '0'; push(&s, value); // 입력이피연산자이면 else{ // 연산자이면피연산자를스택에서제거 op2 = pop(&s); } op1 = pop(&s); switch(ch){ // 연산을수행하고스택에저장 case '+': push(&s,op1+op2); break; } return pop(&s); } case '-': push(&s,op1-op2); break; case '*': push(&s,op1*op2); break; case '/': push(&s,op1/op2); break;

27 중위표기식 -> 후위표기식 o 중위표기와후위표기 ~ 중위표기법과후위표기법의공통점은피연산자의순서는동일 ~ 연산자들의순서만다름 ( 우선순위순서 ) 연산자만스택에저장했다가출력 ~ 2+3*4 -> 234*+ o 알고리즘 ~ 피연산자를만나면그대로출력 ~ 연산자를만나면스택에저장했다가스택보다우선순위가낮은연산자가나오면그때출력 ~ 왼쪽괄호는우선순위가가장낮은연산자로취급 ~ 오른쪽괄호가나오면스택에서왼쪽괄호위에쌓여있는모든연산자를출력

28 ( a + b ) * c (

29 ( a + b ) * c a (

30 ( a + b ) * c + a (

31 ( a + b ) * c + a b (

32 ( a + b ) * c a b

33 ( a + b ) * c a b + *

34 ( a + b ) * c a b + c *

35 ( a + b ) * c a b + c *

36 infix_to_postfix(exp) 스택 s 를생성하고초기화 while (exp 에처리할문자가남아있으면 ) ch 다음에처리할문자 switch (ch) case 연산자 : while ( peek(s) 의우선순위 ch 의우선순위 ) do e pop(s) e 를출력 push(s, ch); break; case 왼쪽괄호 : push(s, ch); break; case 오른쪽괄호 : e pop(s); while( e 왼쪽괄호 ) do e 를출력 e pop(s) break; case 피연산자 : ch 를출력 break; while( not is_empty(s) ) do e pop(s) e 를출력

37 Chap. 6 : 큐 (queue) SANGJI University Kwangman Ko

38 o 특징 큐 (QUEUE) ~ 먼저들어온데이터가먼저나가는자료구조 ~ 선입선출 (FIFO: First-In First-Out) ~ 예, 매표소의대기열 Ticket Box 전단 (front) 후단 (rear)

39 o 직접적인응용 큐의응용 ~ 시뮬레이션의대기열 ( 공항에서의비행기들, 은행에서의대기열 ) ~ 통신에서의데이터패킷들의모델링에이용 ~ 프린터와컴퓨터사이의버퍼링 o 간접적인응용 ~ 스택과마찬가지로프로그래머의도구 ~ 많은알고리즘에서사용됨 생산자 버퍼 소비자 data QUEUE

40 o 선형큐 배열을이용한큐 ~ 배열을선형으로사용하여큐를구현 ~ 삽입을계속하기위해서는요소들을이동시켜야함 ~ 문제점이많아사용되지않음 [-1] [0] [1] [2] [3] [4] [5] front rear [-1] [0] [1] [2] [3] [4] [5] front rear

41 o 원형큐 ~ 배열을원형으로사용하여큐를구현 [3] [2] [1] [0] [MAX_SIZE-2] [MAX_SIZE-1]

42 o 큐 큐의구조 ~ 전단과후단을관리하기위한 2개의변수필요 ~ front: 첫번째요소하나앞의인덱스 ~ rear: 마지막요소의인덱스 rear B 5 1 A front

43 A 6 front 0 rear 7 rear 0 front 7 (a) 초기상태 (b) A 삽입

44 rear 3 4 rear B 5 2 B 5 1 A front 7 front 0 7 (c) B 삽입 (d) A 삭제

45 o 공백상태 : front == rear 공백상태, 포화상태 o 포화상태 : front % M==(rear+1) % M o 공백상태와포화상태를구별하기위하여하나의공간은항상비워둔다 B C D E 5 2 B C D E A G F 6 1 A H G F front rear front rear front rear (a) 공백상태 (b) 포화상태 (c) 오류상태

46 큐의연산 // 공백상태검출함수 int is_empty(queuetype *q) { } return (q->front == q->rear); // 포화상태검출함수 int is_full(queuetype *q) { } return ((q->rear+1)%max_queue_size == q->front);

47 // 삽입함수 void enqueue(queuetype *q, element item) { } if( is_full(q) ) error(" 큐가포화상태입니다 "); q->rear = (q->rear+1) % MAX_QUEUE_SIZE; q->queue[q->rear] = item; // 삭제함수 element dequeue(queuetype *q) { } if( is_empty(q) ) error(" 큐가공백상태입니다 "); q->front = (q->front+1) % MAX_QUEUE_SIZE; return q->queue[q->front];

48 연결된큐 o 연결된큐 (linked queue) ~ 연결리스트로구현된큐 ~ front 포인터 : 삭제 ~ rear 포인터 : 삽입 ~ front 는연결리스트의맨앞에있는요소를가리키며, rear 포인터는맨뒤에있는요소를가리킴. ~ 큐에요소가없는경우에는 front 와 rear 는 NULL. front rear A B NULL C D NULL

49 연결된큐에서의삽입 front rear temp A B C D NULL front rear A B C D NULL

50 연결된큐에서의삭제 front rear A B C D NULL temp front rear A B C D NULL

51 o 덱 (deque) 덱 (DEQUE) ~ Double-Ended QUEue ~ 큐의전단 (front) 와후단 (rear) 에서모두삽입과삭제가가능 add_front delete_front get_front add_rear delete_rear get_rear 전단 (front) 후단 (rear)

52 연산의종류 객체 : n개의 element형으로구성된요소들의순서있는모임 연산 : create() ::= 덱을생성. init(dq) ::= 덱을초기화. is_empty(dq) ::= 덱이공백상태인지를검사. is_full(dq) ::= 덱이포화상태인지를검사. add_front(dq, e) ::= 덱의앞에요소를추가. add_rear(dq, e) ::= 덱의뒤에요소를추가. delete_front(dq) ::= 덱의앞에있는요소를반환한다음삭제 delete_rear(dq) ::= 덱의뒤에있는요소를반환한다음삭제. get_front(q) ::= 덱의앞에서삭제하지않고앞에있는요소를반환. get_rear(q) ::= 덱의뒤에서삭제하지않고뒤에있는요소를반환

53 덱의연산 front A rear front C A B D rear front(dq, A) ddd_rear(dq, D) front rear front rear A B A B D ddd_rear(dq, B) delete_front(dq) front C A B rear front A B rear front(dq, C) delete_rear(dq)

54 덱의구현 o 이중연결리스트를이용한구현 ~ 양쪽끝에서삽입, 삭제가가능 typedef int element; // 요소의타입 typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; } DlistNode; // 노드의타입 typedef struct DequeType { DlistNode *head; DlistNode *tail; } DequeType; // 덱의타입

55 덱에서의삽입연산

56 void add_rear(dequetype *dq, element item) { DlistNode *new_node = create_node(dq->tail, item, NULL); } if( is_empty(dq)) dq->head = new_node; else dq->tail->rlink = new_node; dq->tail = new_node;

57 void add_front(dequetype *dq, element item) { DlistNode *new_node = create_node(null, item, dq->head); } if( is_empty(dq)) dq->tail = new_node; else dq->head->llink = new_node; dq->head = new_node;

58 덱에서의삭제연산

59 // 전단에서의삭제 element delete_front(dequetype *dq) { } element item; DlistNode *removed_node; if (is_empty(dq)) error(" 공백덱에서삭제 "); else { } removed_node = dq->head; // 삭제할노드 item = removed_node->data; // 데이터추출 dq->head = dq->head->rlink; // 헤드포인터변경 free(removed_node); if (dq->head == NULL) // 공백상태이면 dq->tail = NULL; else return item; // 공백상태가아니면 dq->head->llink=null; // 메모리공간반납