Как пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и т.д.):
— хранить дек в циклическом буфере и расширять при переполнении (при таком подходе реже нужны расширения);
— хранить содержимое дека в массиве, начиная от его центра, и при переполнении расширять массив (например, создавать новый массив и копировать туда содержимое старого);
— хранить дек в виде многих малых массивов, добавляя новые массивы с того или другого конца при необходимости.
Здесь приведу свою реализацию третьим способом: малые деки хранятся в виде двусвязного списка и добавляются/удаляются в соответствующих ситуациях.; конструктор основного дека создаёт единственный малый дек, который заполняется от центра к краям.
Соответствующая задача на e-olimp: 6130 и зачтённое решение.
В этом блоге можно увидеть картинку, иллюстрирующую рассматриваемый метод, и краткое описание того, как можно снабдить дек индексированием, чтобы быстро получать доступ к элементу дека по его индексу (как в массиве).
О плюсах и минусах
Расширения нужно (в теории) производить чаще, чем при первом подходе, но зато не нужно полностью копировать содержимое дека при расширении.
Отмечу, что если хранить в узлах двусвязного списка не малые деки, а отдельные элементы, то тратится в три раза больше памяти, что должно быть чувствительно при необходимости хранить большое количество элементов в деке.
Основным преимуществом рассматриваемого подхода, по сравнению с двумя другими, я считаю как раз более эффективный расход памяти. Основной же недостаток, на мой взгляд, состоит в том, что при цепочке удалений-вставок, приводящей к постоянному переполнению/очищению одного из крайних малых деков, будут очень часто создаваться/удаляться малые деки, что может привести к бОльшим временным затратам, чем при реализации дека другими методами.
|
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 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 |
#include <iostream> #include <string> using namespace std; const int Max = 1000; // максимально допустимое число элементов в малом деке struct node { node* prev; node* next; int* dequeue; node(node* Pr, node* Ne) { prev = Pr; next = Ne; dequeue = new int[Max](); } void print() { for(int k = 0; k < Max; k++) cout << dequeue[k] << " "; cout << endl; } }; struct Dequeue { node* first; node* last; int f; // индекс первого свободного элемента в первой деке int l; // индекс последнего свободного элемента в последней деке int Size; Dequeue() { node* N = new node(nullptr, nullptr); first = N; last = N; f = Max/2 - 1; l = Max/2; Size = 0; } // Управление двусвязным списком void add_first () { // добавляет новый узел в начало списка node* N = new node(nullptr, first); first -> prev = N; first = N; f = Max - 1; } void add_last () { // добавляет новый узел в конец списка node* N = new node(last, nullptr); last -> next = N; last = N; l = 0; } void delete_first () { // удаляет первый узел списка node* N = first -> next; delete first; first = N; first -> prev = nullptr; f = 0; } void delete_last () { // удаляет последний узел списка node* N = last -> prev; delete last; last = N; last -> next = nullptr; l = Max - 1; } // Управление деком void push_front (int n) { (first -> dequeue)[f] = n; f--; Size++; if (f == -1) // если первый дек переполнен add_first(); // добавляем в начало списка новый дек } void push_back (int n) { (last -> dequeue)[l] = n; l++; Size++; if (l == Max) // если последний дек переполнен add_last(); // добавляем в конец списка новый дек } int pop_front () { Size--; if (f == Max - 1) delete_first(); else f++; return (first -> dequeue)[f]; } int pop_back () { Size--; if (l == 0) delete_last(); else l--; return (last -> dequeue)[l]; } int front () { if (f == Max - 1) return ((first -> next) -> dequeue)[0]; else return (first -> dequeue)[f+1]; } int back () { if (l == 0) return ((last -> prev) -> dequeue)[Max - 1]; else return (last -> dequeue)[l-1]; } int size() { return Size; } bool empty() {return (Size == 0);} void clear() { node* N = first; while (N) { node* M = N -> next; delete N->prev; delete N; N = M; } N = new node(nullptr, nullptr); first = N; last = N; Size = 0; f = Max/2 - 1; l = Max/2; } void print() { node* N = first; while (N) { N -> print(); N = N->next; } } }; int main() { Dequeue D; string comand; int x; while(cin >> comand) { if (comand == "push_front") { cin >> x; D.push_front(x); cout << "ok\n"; } if (comand == "push_back") { cin >> x; D.push_back(x); cout << "ok\n"; } if (comand == "pop_front") { if (D.empty()) cout << "error\n"; else cout << D.pop_front() << "\n"; } if (comand == "pop_back") { if (D.empty()) cout << "error\n"; else cout << D.pop_back() << "\n"; } if (comand == "front") { if (D.empty()) cout << "error\n"; else cout << D.front() << "\n"; } if (comand == "back") { if (D.empty()) cout << "error\n"; else cout << D.back() << "\n"; } if (comand == "size") { cout << D.size() << "\n"; } if (comand == "clear") { D.clear(); cout << "ok\n"; } if (comand == "exit") { cout << "bye\n"; return 0; } if (comand == "print") { D.print(); } } return 0; } |
Зачтено. Отлично работает. Молодец!
Но… есть замечание — массив печатается целиком, а не только заполненные элементы.
… и вопрос.
В этом примере использования
единичка ползет по массиву до конца, потом создается новый массив и удаляется старый. И так будет снова и снова. Правильно?
Т.е. с точки зрения эффективности лучше использовать циклические массивы в качестве элементарных дек списка. И это ничуть не сложнее, чем написано сейчас.
Замечание очень актуальное. Я отметил этот недостаток в последнем абзаце раздела «О плюсах и минусах». К сожалению, при реализации столкнулся с техническими проблемами, когда пробовал использовать циклические буферы, поэтому оставил такой вариант — он работал!
Печать я изначально использовал для промежуточных выводов на экран при добавлениях/удалениях: тогда нужно было выводить весь массив, а потом забыл подправить.