03_queue

Size: px

Start display at page:

Download "03_queue"

정균 여
6 years ago
Views:

1 Queue Data Structures and Algorithms

2 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2

3 큐의이해와 ADT 정의 Data Structures and Algorithms 3

4 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in, First-out) 구조 의자료구조 먼저들어간것이먼저나오는구조 큐의기본연산 Enqueue: 큐에데이터를넣는연산 Dequeu: 큐에서데이터를꺼내는연산 Data Structures and Algorithms 4

5 큐의 ADT 정의 배열또는연결리스트기반큐 enqueue 연산 dequeue 연산 peek 연산 Data Structures and Algorithms 5

6 큐의배열기반구현 Data Structures and Algorithms 6

7 큐의동작 enqueue 연산 큐의꼬리 (R) 을한칸이동후새데이터저장 dequeue 연산 큐의머리 (F) 가가리키는데이터반환후 F 를한칸이동 Data Structures and Algorithms 7

8 배열기반큐의문제점 Dequeue 동작으로배열이비더라도인덱스이상증가불가 데이터추가를위해 R 을인덱스 0 위치로이동해야함 Data Structures and Algorithms 8

9 원형큐 배열의머리와끝을연결한구조 Data Structures and Algorithms 9

10 원형큐의단순한연산 R 이이동한다음에데이터저장 F 가가리키는데이터반환후 F 이동 Data Structures and Algorithms 10

11 원형큐의단순한연산의문제점 full empty Data Structures and Algorithms 11

12 원형큐의문제점해결 초기화 : F 와 R 이같은위치를가리킴 R 이 F 를가리키려고하면 Full Data Structures and Algorithms 12

13 원형큐의구현 : 헤더파일 #define QUE_LEN 100 typedef int Data; typedef struct _cqueue int front; int rear; Data quearr[que_len]; } CQueue; quearr typedef CQueue Queue; void QueueInit(Queue * pq); int QIsEmpty(Queue * pq); void Enqueue(Queue * pq, Data data); Data Dequeue(Queue * pq); Data QPeek(Queue * pq); Data Structures and Algorithms 13

14 원형큐의구현 : Helper Function 큐의연산에의해서 F(front) 와 R(rear) 이이동할때이동해야할위치를알려주는함수 int NextPosIdx(int pos) if(pos == QUE_LEN-1) return 0; else return pos+1; } Data Structures and Algorithms 14

15 원형큐의구현 : 함수정의 1 void QueueInit(Queue * pq) pq->front = 0; pq->rear = 0; } int QIsEmpty(Queue * pq) if(pq->front == pq->rear) return TRUE; else return FALSE; } Data Structures and Algorithms 15

16 원형큐의구현 : 함수정의 2 void Enqueue(Queue * pq, Data data) // rear 이동후데이터저장 if(nextposidx(pq->rear) == pq->front) printf("queue Memory Error!"); exit(-1); } } pq->rear = NextPosIdx(pq->rear); pq->quearr[pq->rear] = data; Data Dequeue(Queue * pq) if(qisempty(pq)) printf("queue Memory Error!"); exit(-1); } // front 이동후데이터반환 pq->front = NextPosIdx(pq->front); return pq->quearr[pq->front]; } Data Structures and Algorithms 16

17 큐의연결리스트기반구현 Data Structures and Algorithms 17

18 연결리스트기반큐의헤더파일 연결리스트기반스택의응용 typedef int Data; typedef struct _node Data data; struct _node * next; } Node; void QueueInit(Queue * pq); int QIsEmpty(Queue * pq); void Enqueue(Queue * pq, Data data); Data Dequeue(Queue * pq); Data QPeek(Queue * pq); typedef struct _lqueue Node * front; Node * rear; } LQueue; typedef LQueue Queue; Data Structures and Algorithms 18

19 연결리스트기반큐의구현 : 초기화 void QueueInit(Queue * pq) pq->front = NULL; pq->rear = NULL; } int. QIsEmpty(Queue * pq) if(pq->front == NULL) return TRUE; else return FALSE; } Data Structures and Algorithms 19

if(qisempty(pq)) pq->front = newnode; pq->rear = newnode; } else pq->rear->next =

20 연결리스트기반큐의구현 : enqueue void Enqueue(Queue * pq, Data data) Node * newnode = (Node*)malloc(sizeof(Node)); newnode->next = NULL; newnode->data = data; } if(qisempty(pq)) pq->front = newnode; pq->rear = newnode; } else pq->rear->next = newnode; pq->rear = newnode; } F 와 R 변경 R 만변경 enqueue enqueue Data Structures and Algorithms 20

21 연결리스트기반큐의구현 : dequeue F 가다음노드를가리킴, 이전노드삭제 F 가다음노드를가리킴, 이전노드삭제 R 은 no-operation Data Structures and Algorithms 21

"); exit(-1); } enqueue delnode = pq->front; retdata = delnode->data; // F

22 연결리스트기반큐의구현 : dequeue 정의 Data Dequeue(Queue * pq) Node * delnode; Data retdata; if(qisempty(pq)) printf("queue Memory Error!"); exit(-1); } enqueue delnode = pq->front; retdata = delnode->data; // F 가다음노드를가리킴 pq->front = pq->front->next; } free(delnode); // 노드삭제 return retdata; Data Structures and Algorithms 22

23 큐의활용 Data Structures and Algorithms 23

24 주제 점심시간 1 시간동안에고객이 15 초당 1 명씩주문 종류별햄버거를만드는데걸리는시간 치즈버거 -12 초 불고기버거 -15 초 더블버거 -24 초 시뮬레이션 : 대기의길이를결정하는데필요한정보확보 시뮬레이션을통해서추출된정보의형태! 수용인원이 30 명인공간안정적으로고객을수용할확률 50% 수용인원이 50 명인공간안정적으로고객을수용할확률 70% 수용인원이 100 명인공간안정적으로고객을수용할확률 90% 수용인원이 200 명인공간안정적으로고객을수용할확률 100% Data Structures and Algorithms 24

25 시뮬레이션예제 점심시간은 1 시간이고그동안고객은 15 초에 1 명씩주문 한명의고객은하나의버거만을주문 주문하는메뉴에는가중치없음 모든고객은무작위로메뉴선택 햄버거를만드는사람은 1 명이다. 그리고동시에둘이상의버거가만들지않음 주문한메뉴를받을다음고객은대기실에서나와서대기 실행결과 1 실행결과 2 Data Structures and Algorithms 25

26 덱 (Deque) 의이해와구현 Data Structures and Algorithms 26

27 덱 (Deque, double ended queue) 덱은양방향으로 enqueue 와 dequeue 가되는자료구조 스택과큐의특성을모두갖음 덱을스택과큐로활용 덱의 4 가지연산 앞으로넣기 앞에서빼기 뒤에서빼기 뒤에서넣기 Data Structures and Algorithms 27

28 덱의 ADT Data Structures and Algorithms 28

29 덱의구현 : 헤더파일정의 Dequeu.h typedef int Data; typedef struct _node // 양방향리스트 Data data; struct _node * next; struct _node * prev; } Node; typedef struct _dldeque // 앞뒤연산 Node * head; Node * tail; } DLDeque; typedef DLDeque Deque; void DequeInit(Deque * pdeq); int DQIsEmpty(Deque * pdeq); void DQAddFirst(Deque * pdeq, Data data); void DQAddLast(Deque * pdeq, Data data); Data DQRemoveFirst(Deque * pdeq); Data DQRemoveLast(Deque * pdeq); Data DQGetFirst(Deque * pdeq); Data DQGetLast(Deque * pdeq); Data Structures and Algorithms 29

30 덱의구현 : 함수의정의 양방향연결리스트의구조 이전에구현한양방향연결리스트의구조 Data Structures and Algorithms 30

슬라이드 1

슬라이드 1 CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element