Задача:
Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.
pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.
front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
size
Вывести количество элементов в деке.
clear
Очистить дек (удалить из него все элементы) и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Размер дека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.
Результат на C++
Результат на Java
Код на C++:
|
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 |
#include <iostream> #include <string> using namespace std; class Deque{ private: int *a = new int [100]; int size_; int front_; int back_; int capacity; void resize(int); public: Deque(): size_(0), front_(1), back_(0), capacity(100){} void push_back(int); void push_front(int); void pop_back(); void pop_front(); int size() const; int back() const; int front() const; void clear(); }; void Deque::resize(int newcapacity){ //Функция изменения размера. int* tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью int j = front_; //Присваиваем начальное значение счетчику. for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента. tmp[i] = a[j]; j = (j+1)%capacity; } tmp[size_ - 1] = a[back_]; //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива. delete []a; //Удаляем лишнюю память. a = tmp; //Присваиваем указателю на старый массив указатель на новый массив. capacity = newcapacity; //Меняем значение вместимости. front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции. back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов. } void Deque::push_back(int b){ if(size_ == capacity){ this -> resize(2*capacity); } back_ = (back_ + 1)%capacity; a[back_] = b; size_++; } void Deque::push_front(int b){ if(size_ == capacity){ this -> resize(2*capacity); } front_ = (front_ - 1 + capacity)%capacity; a[front_] = b; size_++; } void Deque::pop_back(){ back_ = (back_ - 1 + capacity)%capacity; size_--; } void Deque::pop_front(){ front_ = (front_ + 1)%capacity; size_--; } int Deque::size() const{ return size_; } int Deque::front() const{ return a[front_]; } int Deque::back() const{ return a[back_]; } void Deque::clear(){ back_ = 0; front_ = 1; size_ = 0; } int main() { Deque a; string s; int n; while(cin >> s){ if(s == "push_back"){ cin >> n; a.push_back(n); cout << "ok\n"; } else if(s == "push_front"){ cin >> n; a.push_front(n); cout << "ok\n"; } else if(s == "pop_back"){ if(a.size()){ cout << a.back() << endl; a.pop_back(); } else{ cout << "error\n"; } } else if(s == "pop_front"){ if(a.size()){ cout << a.front() << endl; a.pop_front(); } else{ cout << "error\n"; } } else if(s == "front"){ if(a.size()){ cout << a.front() << endl; } else{ cout << "error\n"; } } else if(s == "back"){ if(a.size()){ cout << a.back() << endl; } else{ cout << "error\n"; } } else if(s == "size"){ cout << a.size() << endl; } else if(s == "clear"){ cout << "ok\n"; a.clear(); } else if(s == "exit"){ cout << "bye\n"; return 0; } } return 0; } |
Код на Java:
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Deque{ private int[] a = new int [100]; private int size_; private int front_; private int back_; private int capacity; private void resize(int newcapacity){ //Функция изменения размера. int[] tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью int j = front_; //Присваиваем начальное значение счетчику. for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента. tmp[i] = a[j]; j = (j+1)%capacity; } tmp[size_ - 1] = a[back_]; //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива. a = tmp; //Присваиваем указателю на старый массив указатель на новый массив. capacity = newcapacity; //Меняем значение вместимости. front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции. back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов. } public Deque() { size_ = 0; front_ = 1; back_ = 0; capacity = 100; } public void push_back(int b){ if(size_ == capacity){ this.resize(2*capacity); } back_ = (back_ + 1)%capacity; a[back_] = b; size_++; } public void push_front(int b){ if(size_ == capacity){ this.resize(2*capacity); } front_ = (front_ - 1 + capacity)%capacity; a[front_] = b; size_++; } public void pop_back(){ back_ = (back_ - 1 + capacity)%capacity; size_--; } public void pop_front(){ front_ = (front_ + 1)%capacity; size_--; } public int size(){ return size_; } public int back(){ return a[back_]; } public int front(){ return a[front_]; } public void clear(){ back_ = 0; front_ = 1; size_ = 0; } }; public class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); Deque a = new Deque(); String s; String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"}; int n; am:while(true){ s = in.next(); if(s.equals(oper[0])){ n = in.nextInt(); a.push_back(n); out.println("ok"); } else if(s.equals(oper[1])){ n = in.nextInt(); a.push_front(n); out.println("ok"); } else if(s.equals(oper[2])){ if(a.size() != 0){ out.println(a.back()); a.pop_back(); } else{ out.println("error"); } } else if(s.equals(oper[3])){ if(a.size() != 0){ out.println(a.front()); a.pop_front(); } else{ out.println("error"); } } else if(s.equals(oper[4])){ if(a.size() != 0){ out.println(a.front()); } else{ out.println("error"); } } else if(s.equals(oper[5])){ if(a.size() != 0){ out.println(a.back()); } else{ out.println("error"); } } else if(s.equals(oper[6])){ out.println(a.size()); } else if(s.equals(oper[7])){ out.println("ok"); a.clear(); } else if(s.equals(oper[8])){ out.println("bye"); //System.exit(0); break am; } } out.flush(); } } |
Пояснение:
В этом варианте дек был реализован с помощью динамического массива. Так как добавление и удаление элементов происходит как с начала, так и с конца массива пришлось зациклить ввод и вывод данных. Каждый раз при добавлении (удалении) элемента мы вычисляли новую позицию для указателей по модулю вместимости массива.
Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.
Такая реализация является одной из самых простых. По сравнению с двусвязным списком, она приблизительно в три раза проигрывает в скорости выполнения. Но за счет того, что мы храним только один int на каждый элемент (вместо трех, которые были у списка), такая реализация использует заметно меньше памяти.
Зачтено.
Больное место реализаций с изменением размера массива — это стратегия наращивания. Редко точно известно как именно будет расти дека (очередь, стек) и на сколько или во сколько раз его увеличивать. Сделайте, пожалуйста, ссылку на аналогичную работу Игоря Вустянюка. Там используется более эффективная система списка массивов. Правда пока не циклических.
Игорь Евгеньевич прав — изменение размера структуры — это проблема. Вы увеличиваете вместимость — это хорошо, но нигде не происходит уменьшение вместимости — даже clear ее не уменьшает. Вообще-то по хорошему clear должен сбрасывать вместимость на первоначальную (если она больше первоначальной). И еще, первоначальная вместимость 100 у Вас магическое число.
Так что пока 10 баллов зачесть не могу — 7 баллов.