Algorithms

Transcription

1 자료구조 & 알고리즘 스택과큐 (Stack and Queue) Seo, Doo-okok

2 목 차 스택의개념및구현 큐의개념및구현 2

3 스택 스택의개념및구현 스택의구현 스택의응용 큐의개념및구현 3

4 스택 (Stack) 스택의구조 후입선출 (LIFO, Last-In-First-Out) 삽입 PUSH 삭제 POP 입력 : A B C D D C B A Top 4

5 스택의구현 순차자료구조를이용한스택의구현 순차자료구조인 1차원배열을이용하여구현 스택크기 : 배열의크기 스택에저장된원소의순서 : 배열원소의첨자 변수 top : 스택에저장된마지막원소에대한첨자저장 공백상태 :top = -1 ( 초기값 ) 포화상태 : top = n - 1 [0] [1]... [n 1] n 번째원소첫번째원소두번째원소... n 번째원소 stack... 두번째원소 첫번째원소 스택의구현 장점 : 순차자료구조인 1차원배열을이용하여쉽게구현단점 : 정적배열을사용하므로스택의크기변경의어려움 5

6 스택의구현 (cont d) 연결자료구조를이용한스택의구현 단순연결리스트를이용하여구현 스택의원소 : 단순연결리스트의노드 스택원소의순서 : 노드의링크필드 ( 포인터 ) 로연결 push : 항상리스트의첫번째노드로삽입 pop : 항상리스트의마지막노드를삭제 변수 top : 단순연결리스트의마지막노드를가리키는포인터변수 초기상태 : top = NULL data link top n 번째원소 링크 n 번째원소 stack... 두번째원소 스택의구현 두번째원소 링크 첫번째원소 첫번째원소 링크 6

7 스택의구현 : 알고리즘 스택의구현 (cont d) 초기의빈스택생성알고리즘 stack_create() stack[n]; // 크기가 n 인 1 차원배열생성 top -1; end stack_create() 스택에최대로저장할수있는원소개수를배열크기로하여 1 차원배열을선언 저장된원소가없는빈스택이므로 top 을 -1 로초기화 7

8 스택의구현 (cont d) 스택의구현 : 알고리즘 (cont d) 스택의데이터삽입알고리즘 : PUSH push(s, data) if (top + 1 = n) then stack_isfull; else S(++top) data; end push() 스택의데이터삭제알고리즘 : POP pop(s) if (top = -1) then estack_isempty; else return S(top--); end pop() 8

9 스택의구현 (cont d) 스택의구현 : 알고리즘 (cont d) 스택의공백상태검사알고리즘 stack_isempty(s) if(top = -1) then return true; else return false; end stack_isempty() 스택의포화상태검사알고리즘 stack_isfull(s) if(top + 1 = n) then return true; else return false; end stack_isfull() 9

10 스택의구현 (cont d) 스택의구현 : 알고리즘 (cont d) 스택검색알고리즘 stack_peek(s) if (top = -1) then stack_isempty; else return S(top); end stack_peek() 스택에서 Stack[top] 에있는원소를검색하여반환하는연산 10

11 스택의구현 (cont d) 프로그램예제 : 순차자료구조를이용한스택의구현 Stack.h #ifndef STACK_SIZESIZE #define STACK_SIZE 10 #endif #ifndef ELEMENT #define ELEMENT typedef int element; #endif #ifndef STACK_H_ #define STACK_H_ typedef struct _stacktype element stack[stack_size]; int top; StackType; #endif StackType *stack_create(void); void stack_destroy(stacktype *); void push(stacktype *, element); element pop(stacktype *); void stack_ Output(StackType *); 11

12 스택의구현 (cont d) 프로그램예제 : 순차자료구조를이용한스택의구현 main.c (1/2) #include <stdio.h> #include <stdlib.h> #include Stack.h" int main() int num, data; StackType *s = stack_create(); while(1) system("cls"); ") printf("\n ### 스택구현 : 1차원배열 ### \n\n"); printf("1) 데이터삽입 : PUSH \n"); printf("2) 데이터삭제 : POP \n"); printf("3) 전체출력 \n"); printf("4) 프로그램종료 \n\n"); printf(" 메뉴선택 : "); scanf("%d", &num); fflush(stdin); 12

13 스택의구현 (cont d) 프로그램예제 : 순차자료구조를이용한스택의구현 main.c (2/2) switch(num) case 1 : printf("\n 삽입할데이터입력 : "); scanf("%d", &data); fflush(stdin); push(s, data); break; case 2 : printf(" 삭제된데이터 : %3d \n, pop(s) ); break; case 3 : stack_output(s); break; case 4 : printf(" 프로그램종료... \n"); return 0; default : printf(" 잘못선택하셨습니다. \n"); system("pause"); stack_destroy(s); return 0; 13

14 스택의구현 (cont d) 프로그램예제 : 순차자료구조를이용한스택의구현 stack.c (1/3) #include <stdio.h> #include <stdlib.h> #include "stack.h" StackType *stack_create(void) StackType *s = (StackType *)malloc(sizeof(stacktype)); if(s == NULL) printf(" 스택생성실패!!! \n"); return NULL; s->top = -1; void return s; stack_destroy(stacktype *s) free(s); return; 14

15 스택의구현 (cont d) 프로그램예제 : 순차자료구조를이용한스택의구현 stack.c (2/3) void push(stacktype *s, element data) if(s->top + 1 == STACK_SIZE) printf(" 스택이꽉찼네요!!! \n"); return; s->stack[++s->top] = data; return; element pop(stacktype p( *s) if (s->top == -1) printf(" 스택이비어있네요!!! \n"); return EOF; return s->stack[s->top--]; 15

16 스택의구현 (cont d) 프로그램예제 : 순차자료구조를이용한스택의구현 stack.c (3/3) void stack_output(stacktype t t(st kt *s) int i; printf("\n STACK [ "); for(i=0; i <= s->top; i++) printf("%3d", s->stack[i] ); printf(" ]\n"); return; 16

17 스택의다양한응용 역순문자열 백스페이스키 진법의변환 수식의괄호검사 수식의후위표기법변환 스택의응용 후위표기법을이용한수식연산 시스템스택 (System Stack) 함수의호출과복귀순서를스택의 LIFO 구조를응용하여관리 17

18 후위표기법변환 : 알고리즘 스택의응용 (cont d) infix_to_postfix(exp) while (true) do ( 3 * 5 ) ( 6 / 2 ) symbol getsymbol(exp); ( 변환 ) 3 5 * 6 2 / - case symbol = operand : print(symbol); symbol = operator : while (op(stack[top]) >= op(symbol)) do print(pop(stack)); push(stack, symbol); symbol = ( : push(stack, symbol); symbol = ")" : while (stack[top] ( ) do print(pop(stack)); pop(stack); p( symbol = NULL : return; end infix_to_postfix() 18

19 스택의응용 (cont d) 후위표기식의연산 : 알고리즘 evalpostfix(exp) while (true) do symbol getsymbol(exp); case end evalpostfix() symbol = operand :push(stack, symbol); symbol = operator : operand2 pop(stack)); operand1 pop(stack)); 3 5 * 6 2 / - : ( 결과 ) 12 res operand1 op(symbol) operand2; push(stack, res); symbol = NULL : return; 19

20 큐 스택의개념및구현 큐의개념및구현 큐의구현 큐의응용 20

21 큐 (Queue) 큐의구조 선입선출 (FIFO, First-In First-Out) 리스트의한쪽끝에서삽입작업이이루어지고반대쪽끝에서삭제작업이이루어져서삽입된순서대로삭제되는구조 Front Rear A B C D 입력 : A B C D 21

22 큐의구현 : 순차자료구조 선형큐 (Linear Queue) 연속된삽입, 삭제에의한오른쪽이동 Front Rear Remove Remove Add Final

23 큐의구현 : 순차자료구조 (cont d) 선형큐구현 : 알고리즘 초기공백선형큐생성알고리즘 queue_create() Q[n]; // 크기가 n 인 1 차원배열생성 front -1; rear -1; end queue_create() 큐에최대로저장할수있는원소개수를배열의크기로하는 1 차원배열을선언 저장된원소가없는공백큐이므로 front 와 rear 는 -1 로초기화 23

24 큐의구현 : 순차자료구조 (cont d) 선형큐구현 : 알고리즘 (cont d) 선형큐의삽입알고리즘 : enqueue enqueue(q, data) if (Q->rear + 1 = n) then queue_isfull; else Q[++rear] data; end enqueue() 선형큐의삭제알고리즘 : dequeue dequeue(q) if (Q->front = Q->rear) then queue_isempty; else return Q[++front]; end dequeue() 24

25 큐의구현 : 순차자료구조 (cont d) 선형큐구현 : 알고리즘 (cont d) 선형큐의공백검사알고리즘 queue_isempty(q) if(q->front = Q->rear) then return true; else return false; end queue_isempty() 선형큐의포화상태검사알고리즘 queue_isfull(q) if(q->rear + 1 = n) then return true; else return false; end queue_isfull() 25

26 큐의구현 : 순차자료구조 (cont d) 선형큐구현 : 알고리즘 (cont d) 선형큐검색알고리즘 queue_peek() if(q->front = Q->rear) then queue_isfull; else end queue_peek() return Q[front + 1]; 큐에서검색은원소중에서가장먼저들어와있는원소, 즉 Q[front+1] 에있는원소를검색하여반환하는연산이다. 26

27 큐의구현 : 순차자료구조 (cont d) 프로그램예제 : 순차자료구조로구현한큐 Queue.h #ifndef QUEUE_SIZE #define QUEUE_SIZE 10 #endif #ifndef ELEMENT #define ELEMENT typedef int element; #endif #ifndef QUEUE_H #define QUEUE_H typedef struct _queuetype element queue[queue_size]; int front, rear; QueueType; QueueType *queue_create(); void queue_destroy(queuetype *); void enqueue(queuetype *Q, element item); element dequeue(queuetype *Q); void queue_print(queuetype *Q); #endif 27

28 큐의구현 : 순차자료구조 (cont d) 프로그램예제 : 순차자료구조로구현한큐 main.c (1/2) #include <stdio.h> #include <stdlib.h> #include "Queue.h" int main() int QueueType num, data; *q = queue_create(); while(1) system("cls"); printf("\n ### 큐구현 : 1차원배열 ### \n\n"); printf("1) 데이터삽입 : enqueue \n"); printf("2) 데이터삭제 : dequeue \n"); printf("3) 전체출력 \n"); printf("4) 프로그램종료 \n\n"); printf(" 메뉴선택 : "); scanf("%d", &num); 28

29 큐의구현 : 순차자료구조 (cont d) 프로그램예제 : 순차자료구조로구현한큐 main.c (2/2) switch(num) case 1 : printf("\n 삽입할데이터입력 : "); scanf("%d", &data); fflush(stdin); enqueue(q, data); break; case 2 : printf(" 삭제된데이터 : %3d \n", dequeue(q) ); break; case 3 : queue_print(q); break; case 4 : printf(" 프로그램종료... \n"); return 0; default : printf(" 잘못선택하셨습니다. \n"); fflush(stdin); system("pause"); queue_destroy(q); return 0; 29

30 큐의구현 : 순차자료구조 (cont d) 프로그램예제 : 순차자료구조로구현한큐 Queue.c (1/3) #include <stdio.h> #include <stdlib.h> #include "Queue.h" QueueType *queue_create() QueueType *Q; Q = (QueueType *)malloc(sizeof(queuetype)); if(q == NULL) printf( Queue 생성실패!!! \n ); return NULL; Q->front = -1; Q->rear = -1; void return Q; queue_destroy(queuetype *Q) free(q); 30

31 큐의구현 : 순차자료구조 (cont d) 프로그램예제 : 순차자료구조로구현한큐 Queue.c (2/3) void enqueue(queuetype *Q, element item) if(q->rear + 1 >= QUEUE_SIZE) return; rn Q->queue[++Q->rear] = item; return; element dequeue(queuetype *Q) if(q->front == Q->rear) return -1; return Q->queue[++Q->front]; Q 31

32 큐의구현 : 순차자료구조 (cont d) 프로그램예제 : 순차자료구조로구현한큐 Queue.c (3/3) void queue_print(queuetype *Q) int i; printf("\n Queue : ["); for(i = Q->front+1; i <= Q->rear; i++) printf("%3d", Q->queue[i]); printf(" ] \n"); return; 32

33 큐의구현 : 순차자료구조 (cont d) 선형큐 (cont d) 선형큐의잘못된포화상태인식 큐에서삽입과삭제를반복하면서아래와같은상태일경우, 앞부분에빈자리가있지만 rear = n - 1 상태이므로포화상태로인식하고더이상의삽입을수행하지 않는다. Front Rear Final Rear + 1 == Queue_SIZE 33

34 큐의구현 : 순차자료구조 (cont d) 선형큐 (cont d) 선형큐의잘못된포화상태인식의해결방법 #1 저장된원소들을배열의앞부분으로이동 순차자료에서의이동작업은연산이복잡하여효율성이떨어짐 Front Rear Final Front Rear

35 큐의구현 : 순차자료구조 (cont d) 원형큐 (Circular Queue) 선형큐의잘못된포화상태인식의해결방법 # (Rear + 1) % Queue_SIZE Final Front Rear Add Front Rear

36 큐의구현 : 순차자료구조 (cont d) 원형큐 (cont d) 문제점 빈큐와꽉찬큐의판정불가 : Front = Rear + 1 별도의 Count 변수유지 Front Rear Front Rear Front Rear Front Rear 3 3 Remove Add

37 연결큐 (Linked Queue) 큐의구현 : 연결자료구조 순자자료구조로구현한큐의문제점 크기가제한되어큐의길이를마음대로사용할수없다. 원소가없을때에도항상그크기를유지하고있어야하므로메모리낭비 연결큐의구조 데이터필드와링크필드를가진노드로구성 첫번째노드를가리키는front 포인터 마지막노드를가리키는 rear 포인터 연결큐의초기상태 ( 공백큐 ) : front와 rear를널 (NULL) 포인터로설정 1000 번지 2000 번지 3000 번지 4000 번지 NULL front rear 37

38 큐의구현 : 연결자료구조 (cont d) 덱 (Deque, Double-ended Queue) 큐의양쪽끝에서삽입과삭제가모두발생할수있는큐 스택과큐의성질을모두가지고있는자료구조 Front Rear A B C D 38

39 큐의구현 : 연결자료구조 (cont d) 덱의구현 이중연결리스트구조를이용한덱의구현 Llink data Rlink Llink data Rlink Llink data Rlink NULL NULL front rear 39

40 큐의응용 큐의다양한응용 회문 (Palindromes) 앞에서읽거나뒤에서읽으나똑같은단어나문장 예 : 기러기, 토마토, 소주만병만주소등 운영체제의작업큐 프로세스스케줄링큐 (Process Scheduling Queue) 프린터버퍼큐 (Printer Buffer Queue) 시뮬레이션 (Simulation) 에서의큐잉시스템 모의실험 큐잉이론 (Queueing Theory) 이벤트발생시기 시간구동시뮬레이션 (Time-Driven Simulation) 사건구동시뮬레이션 (Event-Driven Simulation) 40

41 참고문헌 [1] 이지영, C 로배우는쉬운자료구조, 한빛미디어, [2] 주우석, CᆞC++ 로배우는자료구조론, 한빛미디어, [3] 천인국, C C 언어로쉽게풀어쓴자료구조, 생능출판사, [4] 이재규, C 로배우는알고리즘 : 개념과기본알고리즘, 도서출판세화, [5] 문병로, 쉽게배우는알고리즘 : 관계중심의사고법, 한빛미디어, [6] 카사이아사오, 진명조역, C 언어로배우는알고리즘입문, 한빛미디어, [7] Kyle Loudon, 허욱역, Algorithms with C : C 로구현한알고리즘, 한빛미디어, 2006 [8] Wikipedia, 이강의자료는저작권법에따라보호받는저작물이므로무단전제와무단복제를금지하며, 내용의전부또는일부를이용하려면반드시저작권자의서면동의를받아야합니다. Copyright Clickseo.com. All rights reserved. 41