제3장 스택과 큐.

Presentation on theme: "제3장 스택과 큐."— Presentation transcript:

1 제3장 스택과 큐

2 2.3 다항식 추상 데이터 타입 순서리스트의 표현( 메모리 표현) i. 순차 사상 (sequential mapping)
- 물리적 인접성 (arrays) ii.  비순차 사상(non-sequential mapping) - 비연속적 기억장소 위치 - 리스트 : pointers(links)를 가지는 노드 집합

3 3.1 스택 추상 데이터 타입 스택(Stack) : 가장 마지막에 입력된 데이터가 가장 먼저 출력되는 후입선출 자료구조
LIFO(Last-in-First-out) 후입선출 : 한 끝에서 모든 삽입과 삭제가 일어나는 구현원리 응용) Subroutine or recursive call

4 3.1 스택 추상 데이터 타입 데이터의 입력순서 A,B,C,D,E 데이터의 출력순서 E,D,C,B,A 초기상태 A입력
삭제 top E top D D C C top B B B top A A A A top

5 structure Stack objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 stack∈ Stack, item∈ element, max_stack_size∈ positive integer Stack CreateS(max_stack_size) ::= 최대 크기가 max_stack_size인 공백 스택을 생성 Boolean IsFull(stack, max_stack_size) ::= if (stack의 원소수 == max_stack_size) return TRUE else return FALSE Stack Add(stack, item) ::= if (IsFull(stack)) stack_full else stack의 톱에 item을 삽입하고 return Boolean IsEmpty(stack) ::= if (stack == CreateS(max_stack_size)) return TRUE Element Delete(stack) ::= if (IsEmpty(stack)) return else 스택 톱의 item을 제거해서 반환

6 3.1 스택 추상 데이터 타입 top Stack CreateS(max_stack_size) ::=
#define MAX_STACK_SIZE 100 /*최대스택크기*/ typedef struct { int key; /* 다른 필드 */ } element; element stack[MAX_STACK_SIZE]; int top = -1; Boolean IsEmpty(Stack) ::= top < 0; Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE-1; MAX_STACK_SIZE top

7 3.1 스택 추상 데이터 타입 스택의 삽입 연산 void add(int *top, element item) {
/* 전역 stack에 item을 삽입 */ if (*top >= MAX_STACK_SIZE-1) { stack_full(); return; } stack[++*top] = item; top A

8 3.1 스택 추상 데이터 타입 스택의 삭제 연산 element delete(int *top) {
/* stack의 최상위 원소를 반환 */ if (*top == -1) return stack_empty(); /* 오류 key를 반환 */ return stack[(*top)--]; } top D C B A

9 3.2 큐 추상 데이터 타입 Queue : 가장 먼저 입력된 데이터가 가장 먼저 출력되는 선입선출 자료구조
FIFO(First-in-First-out) 선입선출리스트 : 한쪽 끝에서 데이터가 입력되고 그 반대쪽 끝에서 출력이 일어나는 구현원리 응용) Job scheduling

10 3.2 큐 추상 데이터 타입 데이터의 입력순서 A,B,C,D,E 데이터의 출력순서 A,B,C,D,E 초기상태 A입력 B입력 …
삭제 E rear E rear D D C C B rear B B A rear A A A front rear front front front front

11 structure Queue objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 queue∈Queue, item∈element, max_queue_size∈positive integer Queue CreateQ(max_queue_size) ::= 최대 크기가 max_queue_size인 공백 큐를 생성 Boolean IsFullQ(queue, max_queue_size ) ::= if (queue의 원소수 == max_queue_size) return TRUE else return FALSE Queue AddQ(queue, item) ::= if (IsFull(queue)) queue_full else queue의 뒤에 item을 삽입하고 이 queue를 반환 Boolean IsEmptyQ(queue) ::= if (queue == CreateQ(max_queue_size)) return TRUE Element DeleteQ(queue) ::= if (IsEmpty(queue)) return else queue의 앞에 있는 item을 제거해서 반환

12 3.2 큐 추상 데이터 타입 Queue CreateQ(max_queue_size) ::=
#define MAX_QUEUE_SIZE 100 /* 큐의 최대크기 */ typedef struct { int key; /* 다른 필드 */ } element; element queue[MAX_QUEUE_SIZE]; int rear = -1; int front = -1; Boolean IsEmptyQ(queue) ::= front == rear Boolean IsFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1 rear front

13 3.2 큐 추상 데이터 타입 큐의 삽입연산 void addq(int *rear, element item) {
/* queue에 item을 삽입 */ if (*rear == MAX_QUEUE_SIZE-1) queue_full(); return; } queue[++*rear] = item; A rear front

14 3.2 큐 추상 데이터 타입 큐의 삭제연산 element deleteq(int *front, int rear) {
/* queue의 앞에서 원소를 삭제 */ if (*front == rear) return queue_empty(); /* 에러 key를 반환 */ return queue[++*front]; } E rear D C B A front

15 2.3 다항식 추상 데이터 타입 순서리스트의 표현( 메모리 표현) i. 순차 사상 (sequential mapping)
- 물리적 인접성 (arrays) ii.  비순차 사상(non-sequential mapping) - 비연속적 기억장소 위치 - 리스트 : pointers(links)를 가지는 노드 집합

16 제4장 리스트

17 리스트의 개요 배열 구조 : 삽입/삭제가 비효율적 리스트 구조 : 포인터 개념을 이용하여 삽입/삭제 연산을 효율적으로 수행
리스트의 구성 : data field & link data field : 실제 자료가 저장 link field : 다음 노드에 대한 포인터가 저장 data data data data link link link link

18 배열 Int a[7] 3,4 삽입 a[0] 1 a[0] 1 a[0] 1 a[1] 2 a[1] 2 a[1] 2 a[2] 5
6 a[3] a[3] 4 a[4] a[4] 5 a[4] 5 a[5] a[5] 6 a[5] 6 a[6] a[6] a[6]

19 리스트 3추가 1 1 1 4 4 4 2 2 2 3 3

20 4.1 포인터 주소를 저장하기위한 공간 선언 : 객체형 * 변수명; 객체사용 예제 : int * ptr; int a;
선언시 “*변수명” 의 의미 => 주소저장공간 객체사용 & : 주소연산자 * : 역참조(간접지시) 연산자 예제 ptr = &a; ptr = a; *ptr = a;

21 4.1 포인터 int *a1; int a2 = 10; a1 = &a2 *a1 = a2; printf(“%d %d %d %d”,

22 4.1 포인터 int *a1; int a2 = 10; a1 = &a2 *a1 = a2; printf(“%d %d %d %d”,
1002 a2 10

23 4.1 포인터 포인터 사용시 주의할점 포인터는 항상 어떤 대상을 가리키고 있어야 함
어떤 대상도 가리키고 있지 않는 포인터는 항상 NULL로 초기화 ‘\n;

24 4.1 포인터 동적기억장소 할당 => malloc 할당된 메모리 해제 => free free(pi);
int i, *pi; float f, *pf; pi = (int *) malloc(sizeof(int)); pf = (float *) malloc(sizeof(float)); *pi = 1024; *pf = 3.14; 할당된 메모리 해제 => free free(pi); free(pf);

25 4.2 단순연결리스트 연결리스트 : 화살표로 표시된 링크를 가진 노드들의 순열 ptr bat cat sat vat \n

26 4.2 단순연결리스트 연결리스트의 특징 노드들은 순차적 위치에 존재하지 않는다 노드들의 위치는 실행시마다 바뀔수 있다 bat
vat 연결리스트의 특징 노드들은 순차적 위치에 존재하지 않는다 노드들의 위치는 실행시마다 바뀔수 있다 cat sat ptr bat cat sat vat \n

27 4.2 단순연결리스트 linked list의 활용 스택 / 큐 : 배열구조에 비해서 동적인 상황을 구성 다항식 문제의 해결
트리 및 그래프 구조의 표현 동적인 해싱 구조의 생성 메모리 세그멘테이션의 관리

28 4.2 단순연결리스트 연결 리스트 구성을 위한 기능 노드의 구조 정의 : struct 노드 생성 방법 : malloc
노드 삭제 방법 : free

29 4.2 단순연결리스트 예제 [at로 끝나는 단어 리스트]
typedef struct list_node *list_pointer; typedef struct list_node { char data[4]; list_pointer link; }; list_pointer ptr = NULL;

30 4.2 단순연결리스트 공백 리스트 생성 공백 리스트 검사 list_pointer ptr = NULL;
#define IS_EMPTY(ptr) (!(ptr))

31 새 노드 생성 노드 필드에 값 지정 구조 멤버(structure member) 연산자 : ‘->’
ptr bat \n 새 노드 생성 ptr = (list_pointer) malloc(sizeof(list_node)); 노드 필드에 값 지정 구조 멤버(structure member) 연산자 : ‘->’ e->name ≡ (*e).name strcpy(ptr->data,"bat"); ptr->link = NULL;

32 4.2 단순연결리스트 예제 : 2-노드 연결 리스트 ptr 10 20 \n

33 typedef struct list_node *list_pointer; typedef struct list_node {
ptr 10 20 \n typedef struct list_node *list_pointer; typedef struct list_node { int data; list_pointer link; }; list_pointer ptr = NULL;

34 list_pointer create2() { /* 두개의 노드를 가진 연결 리스트의 생성 */
ptr 10 20 \n list_pointer create2() { /* 두개의 노드를 가진 연결 리스트의 생성 */ list_pointer first, second; first = (list_pointer) malloc (sizeof(list_node)); second = (list_pointer) malloc (sizeof(list_node)); second->link = NULL; second->data = 20; first->data = 10; first->link = second; return first; }

35 4.2 단순연결리스트 예제 [리스트 삽입] 함수 호출 : insert(&ptr, node);
#define IS_FULL(ptr) (!(ptr)) ptr 10 20 \n 15

36 void insert(list_pointer *ptr, list_pointer node)
{ list_pointer temp; temp = (list_pointer) malloc (sizeof(list_node)); if (IS_FULL(temp)){ fprintf(stderr, “The memory is full\n”); exit(1); } temp->data = 15; if (*ptr) { temp->link = node->link; node->link = temp; else { temp->link = NULL; *ptr = temp; node ptr 10 20 \n 15 temp ptr 20 \n

37 ptr 10 15 20 \n trail node 예제 : 리스트의 삭제 void deleteq(list_pointer *ptr, list_pointer trail, list_pointer node) { /노드삭제, trail은 삭제될 node의 선행노드이며 ptr은 리스트의 시작 */ if (trail) trail->link = node->link; else *ptr=(*ptr)->link; free(node); }

38 void print_list(list_pointer ptr) { printf(“The list contains : “);
10 15 20 \n 예제 : 리스트의 출력 void print_list(list_pointer ptr) { printf(“The list contains : “); for ( ; ptr; ptr=ptr->link) printf(“%4d”, ptr->data); printf(“\n”); }

39 4.2 단순연결리스트 연습문제 : 리스트에 포함된 노드의 수 int list_length(list_pointer ptr) {
int len =0; while (ptr) { len++; ptr = ptr ->link; } return len; ptr 10 15 20 \n

40 연습문제 : 자료의 탐색 list-pointer list_search(list_pointer ptr, char *data) {
10 15 20 \n 연습문제 : 자료의 탐색 list-pointer list_search(list_pointer ptr, char *data) { while(ptr) { if (!strcmp(ptr->data, data)) return ptr else ptr = ptr->link; } return NULL;

41 4.3 동적연결 스택과 큐 \n front rear 10 10 15 20 \n top

42 4.3 동적연결 스택과 큐 스택과 큐에 대한 함수 작성 isFull isEmpty Add Delete

43 4.3 동적연결 스택과 큐 스택 #define MAX_STACKS 10 /*스택의 최대 원소수 */
typedef struct { int key; /*기타필드*/ }element; typedef struct stack *stack_pointer; typedef struct stack { element item; stack_pointer link; }; Stack_pointer top; Stack_pointer mtop[MAX_STACKS]; top mtop[0] mtop[1] mtop[2] mtop[3] mtop[4]

44 4.3 동적연결 스택과 큐 스택의 초기 조건 top[i]=NULL, 0≤i<MAX_STACKS 경계 조건
i번째 스택이 공백이면, top[i]=NULL 메모리가 가득차면, IS_FULL(temp)

45 4.3 동적연결 스택과 큐 add(&top[stack_no],item); item=delete(&top[stack_no]);

46 4.3 동적연결 스택과 큐 void add(stack_pointer *top, element item) {
/*스택의 톱에 원소를 삽입*/ stack_pointer temp=(stack_pointer) malloc(sizeof(stack)); if (IS_FULL(temp)){ fprintf(stderr,”The memory is full\n”); exit(1); } temp->item = item; temp->link = *top; *top = temp; \n top

47 4.3 동적연결 스택과 큐 element delete(stack_pointer *top) { /*스택으로부터 원소를 삭제*/
stack_pointer temp = *top; element item; if (IS_EMPTY(temp)){ fprintf(stderr,”The stack is empty\n”); exit(1); } item = temp->item; *top = temp->link; free(temp); return item; \n top

48 4.3 동적연결 스택과 큐 큐 #define MAX_QUEUES 10 /*큐의 최대원소수*/
typedef struct queue *queue_pointer; typedef struct queue{ element item; queue_pointer link; } queue_pointer front,rear; queue_pointer m_front[MAX_QUEUES],m_rear[MAX_QUEUES];

49 4.3 동적연결 스택과 큐 초기조건 front[i]=NULL, 0<=i<MAX_QUEUES 경계조건
i번째 큐가 공백이면, front[i]=NULL 메모리가 가득차기만하면, IS_FULL(temp);

50 4.3 동적연결 스택과 큐 addq(&front,&rear,item); item=deleteq(&front);

51 front rear 10 10 15 20 \n void addq(queue_pointer *front, queue_pointer *rear, element item) { /*큐의 rear에 원소를 삽입*/ queue_pointer temp = (queue_pointer) malloc(sizeof (queue)); if(IS_FULL(temp)){ fprintf(stderr,”The memory is full\n”); exit(1); } temp->item = item; temp->link = NULL; if (*front) *rear->link = temp; else *front = temp; *rear = temp;

52 front rear 10 10 15 20 \n element deleteq(queue_pointer *front) { /*큐에서 원소를 삭제*/ queue_pointer temp = *front; element item; if (IS_EMPTY(*front)){ fprintf(stderr,”The queue is empty\n”); exit(1); } item = temp->item; *front = temp->link; free(temp); return item;

53 과제물 리스트를 이용한 동적 스택구현 리스트를 이용한 동적 큐 구현