Решение:
Код для задачи на неограниченный стек:
|
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 |
#include <iostream> #include <string> using namespace std; struct Node{ Node * prev; int x; Node(){prev = nullptr; x = 0;} Node(Node * a, int b){prev = a; x = b;} }; struct stack{ private: Node * Head = nullptr; int Size = 0; public: int size(){ return Size; } void push(int p){ Node * NewHead = new Node(Head,p); Head = NewHead; Size++; } int back(){ if(Size){return Head->x;} else{return 0;} } int pop(){ if(Size){ int x = Head->x; Node * NewHead = Head->prev; delete Head; Head = NewHead; Size--; return x; }else{ return 0; } } void clear(){ while(Size > 0){ Node * NewHead = Head->prev; delete Head; Head = NewHead; Size--; } } }; int main() { stack myStack; while(true){ string s; cin >> s; if(s == "exit"){cout << "bye\n"; break;} else if(s == "push"){ int inp; cin >> inp; myStack.push(inp); cout << "ok\n"; }else if(s == "back"){ if(myStack.size()){ cout << myStack.back() << endl; }else{ cout << "error\n"; } }else if(s == "size"){ cout << myStack.size() << endl; }else if(s == "pop"){ if(myStack.size()){ cout << myStack.pop() << endl; }else{ cout << "error\n"; } }else if(s == "clear"){ cout << "ok\n"; myStack.clear(); } } return 0; } |
Код для задачи на неограниченную очередь:
|
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 |
#include <iostream> #include <string> using namespace std; struct Node{ Node * prev; int x; Node(){prev = nullptr; x = 0;} Node(Node * a, int b){prev = a; x = b;} }; struct queue{ private: Node * Front = nullptr; Node * Back = nullptr; int Size = 0; public: int size(){ return Size; } void push(int p){ if(Size == 0){ Node * NewNode = new Node(Back,p); Front = NewNode; Back = NewNode; }else{ Node * NewNode = new Node(nullptr, p); Back->prev = NewNode; Back = NewNode; } Size++; } int front(){ if(Size){return Front->x;} else{return 0;} } int pop(){ if(Size){ int x = Front->x; Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; return x; }else{ return 0; } } void clear(){ while(Size > 0){ Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; } Front = nullptr; Back = nullptr; } }; int main() { queue Q; while(true){ string s; cin >> s; if(s == "exit"){cout << "bye\n"; break;} else if(s == "push"){ int inp; cin >> inp; Q.push(inp); cout << "ok\n"; }else if(s == "front"){ if(Q.size()){ cout << Q.front() << endl; }else{ cout << "error\n"; } }else if(s == "size"){ cout << Q.size() << endl; }else if(s == "pop"){ if(Q.size()){ cout << Q.pop() << endl; }else{ cout << "error\n"; } }else if(s == "clear"){ cout << "ok\n"; Q.clear(); } } return 0; } |
Код для задачи на неограниченный дек:
|
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 |
#include <iostream> #include <string> using namespace std; struct Node{ Node * prev; Node * next; int x; Node(){prev = nullptr; next = nullptr; x = 0;} Node(Node * a, Node * b, int c){prev = a; next = b; x = c;} }; struct deque{ private: Node * Front = nullptr; Node * Back = nullptr; int Size = 0; public: int size(){ return Size; } void push_back(int p){ if(Size == 0){ Node * NewNode = new Node(Back,Front,p); Front = NewNode; Back = NewNode; }else{ Node * NewNode = new Node(nullptr, Back, p); Back->prev = NewNode; Back = NewNode; } Size++; } void push_front(int p){ if(Size == 0){ Node * NewNode = new Node(Back,Front,p); Front = NewNode; Back = NewNode; }else{ Node * NewNode = new Node(Front, nullptr, p); Front->next = NewNode; Front = NewNode; } Size++; } int back(){ if(Size){return Back->x;} else{return 0;} } int front(){ if(Size){return Front->x;} else{return 0;} } int pop_front(){ if(Size){ int x = Front->x; Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; return x; }else{ return 0; } } int pop_back(){ if(Size){ int x = Back->x; Node * NewNode = Back->next; delete Back; Back = NewNode; Size--; return x; }else{ return 0; } } void clear(){ while(Size > 0){ Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; } Front = nullptr; Back = nullptr; } }; int main() { deque D; while(true){ string s; cin >> s; if(s == "exit"){cout << "bye\n"; break;} else if(s == "push_back"){ int inp; cin >> inp; D.push_back(inp); cout << "ok\n"; }else if(s == "push_front"){ int inp; cin >> inp; D.push_front(inp); cout << "ok\n"; }else if(s == "front"){ if(D.size()){ cout << D.front() << endl; }else{ cout << "error\n"; } }else if(s == "back"){ if(D.size()){ cout << D.back() << endl; }else{ cout << "error\n"; } }else if(s == "size"){ cout << D.size() << endl; }else if(s == "pop_front"){ if(D.size()){ cout << D.pop_front() << endl; }else{ cout << "error\n"; } }else if(s == "pop_back"){ if(D.size()){ cout << D.pop_back() << endl; }else{ cout << "error\n"; } }else if(s == "clear"){ cout << "ok\n"; D.clear(); } } return 0; } |
Засчитанные решения на сайте e-olimp: Стек, Очередь и Дек.
Идея решения: Каждый элемент в структуре должен хранить информацию о предыдущем и последующем. Для этого была организована структура Node. Для дека и очереди она одинаково реализована, а для стека можно было хранить только предыдущий элемент. Во всех 3х задачах была реализована требуемая структура данных.
Однако в каждой задаче требовалось возможность использования всей оперативной памяти под структуру. В моем решении каждый элемент занимает втрое больше памяти (я подозреваю) чем обычный int, а значит всю оперативную память под числа я использовать не смогу. Тогда можно использовать заранее созданный массив достаточно большого размера, чтобы занять всю выделенную память в 256 мб. Но это не будет считаться «неограниченным» размером. А если использовать ту же структуру с Node, но вместо одного элемента хранить массив? Тогда информацию о следующем и предыдущем массиве нужно так-же хранить, как и с отдельными элементами. Вроде бы меньше памяти будет тратится на хранение дополнительной информации, НО никто не может точно сказать, какого размера массивы должны быть. Если они будут слишком маленькие — большой выгоды такой способ не принесет. Если они будут слишком большими, то есть шанс, что мы не покроем большой кусок памяти, что тоже не очень хорошо.
Можно использовать динамически массив, но чтобы увеличить вместимость, нужно сначала выделить память под новый массив, потом скопировать туда всю информацию и удалить старый массив. Очевидно, что когда мы создаем массив, занимающий более половины оперативной памяти, то, для того, чтобы «расширить» массив, памяти уже будет не хватать.
Поэтому я реализовал всё без массивов (хотя вариант с маленькими массивами имеет место быть).
Хорошо. Нужно
— добавить метки и рубрику,
— то, что Вы называете Node, называется «связный список»,
— почему для очереди список двунаправленный?
метки и рубрика добавлены. У очереди вышел двунаправленный список, так как во время написания очереди я уже думал над деком.
Ну, мало ли о чем думает юноша, во время написания очереди 🙂
Не нужно плодить избыточные сущности. Я хочу сказать, что программа с очередью вводи некоторые поля и связи, поддерживает их целостность, но никогда ими не пользуется за ненадобностью. Это не только непроизводительно расходует память, но и увеличивает вероятность ошибки в коде, которые не может быть протестирован.
А вдруг я буду думать о неправильных вещах и у меня плохо получится дек? 🙂
Избыточные сущности убрал, перетестировал код и поменял ссылку на засчитанное решение.
Зачтено