일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 확장 엘리먼트
- 포인터
- javascript prototype
- 연결 리스트
- jQuery
- javascript new
- 배열
- 생성자 new
- pattern
- access
- 스택
- Loose Index Scan
- javascript this
- 연동
- Index Full Scan
- Index Range Scan
- c언어 스택 배열
- 추상적 자료 구조
- npm Option
- Index Skip Scan
- 배열 스택
- C#
- 생성자
- 스택 배열
- javascript 생성자
- 이중 연결 리스트
- 큐 연결리스트
- new 사용법
- 자료구조
- 연결리스트
Archives
- Today
- Total
Open-Closed Principle
[자료구조]큐(Queue) - 리스트 본문
연결 리스트로 큐를 구현하면 동적 할당의 성질에 의해 메모리의 한계까지 큐의 크기를 늘릴 수도 있고, 또 큐가 아주 작을 때에도 메모리도 조금 밖에 차지하지 않는다. 단순 연결 리스트를 이용하여 큐를 구현하는 것은 약간의 무리가 있다.
큐를 구현하려면 앞 노드의 위치와 뒷 노드의 위치를 모두 알고 있어야 하므로 할 수 없이 이중 경결 리스트를 사용하여야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | #include <stdio.h> typedef struct _dnode{ int key; struct _dnode *prev; struct _dnode *next; } dnode; dnode *head, *tail; void init_queue(void){ // 생성 head = (dnode*)malloc(sizeof(dnode)); tail = (dnode*)malloc(sizeof(dnode)); // 연결 head->next = tail; head->prev = head; tail->next = tail; tail->prev = head; } void clear_queue(void){ dnode* temp_node; dnode* del_node; temp_node = head->next; while (temp_node != tail){ del_node = temp_node; temp_node = temp_node->next; free(del_node); } head->next = tail; tail->prev = head; } int put(int value){ dnode* temp; if ((temp = (dnode*)malloc(sizeof(dnode))) == NULL){ printf("\n out of memory"); return -1; } // 연결 tail->prev->next = temp; temp->prev = tail->prev; temp->next = tail; tail->prev = temp; // 값 너어주기 temp->key = value; return value; } int get(void){ dnode* temp; int value; temp = head->next; if (temp == tail){ printf("\n Queue underflow"); return -1; } value = temp->key; head->next = temp->next; temp->next->prev = head; free(temp); return value; } void print_queue(void){ dnode* temp; temp = head->next; printf("\n Queue contnes : Front ---- > Rear \n"); while (temp != tail){ printf("%-6d", temp->key); temp = temp->next; } } void main(void){ init_queue(); put(1); put(2); put(3); put(4); put(5); put(6); print_queue(); get(); print_queue(); get(); print_queue(); get(); } | cs |
'Programming > 알고리즘&자료구조' 카테고리의 다른 글
[자료구조]큐(Queue) - 배열 (0) | 2016.05.12 |
---|---|
[자료구조]스택(Stack) - 연결리스트 (0) | 2016.04.12 |
[자료구조]스택(Stack) - 배열 (0) | 2016.03.17 |
[자료구조]이중 연결 리스트(Doubly Linked List) (0) | 2016.02.17 |
[자료구조]단순 연결 리스트(Simple Linked List) (0) | 2016.02.15 |