|
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 |
#ifndef CDLLDEQUE_H #define CDLLDEQUE_H #pragma warning(disable:4290) #include "Node.h" #include "../Exception/StackException.h" /* Circular Doubly Linked List */ template class CDLLDeque { public: CDLLDeque(); void insertFirst(const Object& e); void insertLast(const Object& e); void removeLast(); void removeFirst(); Object first(); Object last(); bool isEmpty() const; unsigned int size() const; void toString(); private: Node<object width="300" height="150"> * header;Node<object> * trailer;unsigned int iSize;};#include "CDLLDeque.hpp"#endif |
|
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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
template <typename object="">CDLLDeque<object>::CDLLDeque(){iSize = 0;Node<object> * head = new Node<object>(0, 0, 0);Node<object> * tail = new Node<object>(0, 0, 0);</object></object></object></object></object></typename></object></object> header = head; trailer = tail; header->next = trailer; header->prev = trailer; // 순환형이므로 header의 앞은 처음에 trailer가 된다. trailer->next = header; trailer->prev = header; // 순환형이므로 trailer의 앞은 처음에 header가 된다. } template void CDLLDeque<object width="300" height="150">::insertFirst(const Object& e){Node<object> * oldFirst = header->next;Node<object> * temp = new Node<object>(e, header, oldFirst);</object></object></object></object> oldFirst->prev = temp; header->next = temp; trailer->next = temp; // 순환형이라 추가된 코드 if (iSize == 0) // 순환형이라 추가된 코드 { // 첫 번째 데이터가 들어가므로 모두 여기를 향한다 trailer->prev = temp; header->prev = temp; trailer->next = temp; } iSize++; } template void CDLLDeque<object width="300" height="150">::insertLast(const Object& e){Node<object> * oldLast = trailer->prev;Node<object> * temp = new Node<object>(e, oldLast, trailer);</object></object></object></object> oldLast->next = temp; trailer->prev = temp; header->prev = temp; // 순환형이라 추가된 코드 if (iSize == 0) // 순환형이라 추가된 코드 { // 첫 번째 데이터가 들어가므로 모두 여기를 향한다 header->next = temp; trailer->next = temp; header->prev = temp; } iSize++; } template void CDLLDeque<object width="300" height="150">::removeFirst(){if (!isEmpty()){Node<object> * old = header->next;Node<object> * newFirst = old->next;</object></object></object> newFirst->prev = header; header->next = newFirst; trailer->next = newFirst; // 순환형이라 추가된 코드 if (iSize == 1) // 순환형이라 추가된 코드 { // 내용물이 하나도 없으므로 trailer의 앞뒤는 header를 향한다 trailer->prev = header; trailer->next = header; header->prev = trailer; } iSize--; delete old; } else { throw StackEmptyException("Empty"); } } template void CDLLDeque<object width="300" height="150">::removeLast(){if (!isEmpty()){Node<object> * old = trailer->prev;Node<object> * newLast = old->prev;</object></object></object> newLast->next = trailer; trailer->prev = newLast; header->prev = newLast; // 순환형이라 추가된 코드 if (iSize == 1) // 순환형이라 추가된 코드 { // 내용물이 하나도 없으므로 header의 앞뒤는 trailer를 향한다 header->next = trailer; header->prev = trailer; trailer->next = header; } iSize--; delete old; } else { throw StackEmptyException("Empty"); } } template Object CDLLDeque<object width="300" height="150">::first(){if (isEmpty()){throw StackEmptyException("Empty");}else{Object out = header->next->data;</object> Node<object width="300" height="150"> * old = header->next;Node<object> * newFirst = old->next;</object></object> header->next = newFirst; newFirst->prev = header; trailer->next = newFirst; // 순환형이라 추가된 코드 if (iSize == 1) // 순환형이라 추가된 코드 { // 내용물이 하나도 없으므로 trailer의 앞뒤는 header를 향한다 trailer->prev = header; trailer->next = header; header->prev = trailer; } iSize--; return out; } } template Object CDLLDeque<object width="300" height="150">::last(){if (isEmpty()){throw StackEmptyException("Empty");}else{Object out = trailer->prev->data;</object> Node<object width="300" height="150"> * old = trailer->prev;Node<object> * newLast = old->prev;</object></object> trailer->prev = newLast; newLast->next = trailer; header->prev = newLast; // 순환형이라 추가된 코드 if (iSize == 1) // 순환형이라 추가된 코드 { // 내용물이 하나도 없으므로 header의 앞뒤는 trailer를 향한다 header->next = trailer; header->prev = trailer; trailer->next = header; } iSize--; return out; } } template bool CDLLDeque<object width="300" height="150">::isEmpty() const { return iSize == 0; }</object> template unsigned int CDLLDeque<object width="300" height="150">::size() const { return iSize; }</object> template void CDLLDeque<object width="300" height="150">::toString(){Node<object> * temp = header->next;for (unsigned int i = 0; i < iSize; i++) { if (temp->next != trailer){cout << temp->data << ", "; temp = temp->next;}else if (temp->next == trailer){cout << temp->data << endl;}}} |
|
1 2 3 4 5 6 7 8 9 |
#ifndef NODE_H #define NODE_H template class Node { public: Node<object width="300" height="150">::Node(const Object& input = Object(), Node* p = NULL, Node* n = NULL) : data(input), prev(p), next(n) {}Object data;Node * next;Node * prev;};</object> #endif |