Постановка задачи
Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.
pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.
front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
size
Вывести количество элементов в деке.
clear
Очистить дек (удалить из него все элементы) и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:
- pop_front,
- pop_back,
- front,
- back
всегда корректны.
Объяснение: Количество элементов во всех структурах данных не превышает [latex]10000[/latex], если это не указано особо.
Также условие задачи можно посмотреть здесь.
Входные данные:
Описаны в условии. См. также пример входных данных.
Выходные данные:
Описаны в условии. См. также пример выходных данных.
Тесты
| № | Входные данные | Выходные данные |
| 1 | push_back 3 push_front 14 size clear push_front 1 back push_back 2 front pop_back size pop_front size exit |
ok ok 2 ok ok 1 ok 1 2 1 1 0 bye |
| 2 | push_front 7 push_front 8 push_front 9 pop_back back push_front 11 size pop_back pop_back pop_back push_back 90 front exit |
ok ok ok 7 8 ok 3 8 9 11 ok 90 bye |
| 3 | push_back -5 push_back -20 push_back 2 pop_front push_front 7 size clear pop_back push_front 11 size exit |
ok ok ok -5 ok 3 ok -1 ok 1 bye |
Посмотреть работу программы на примере первого теста можно на сайте ideone.
Решение
|
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 |
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Deque { final int maxSize = 10000; int size; public int head, end; int[] data; public Deque() { data = new int[maxSize]; head = 0; end = 0; size = 0; } public void push_front(int e) { if (size == maxSize) { System.out.println("Deque is full."); return; } else if (size==0) { end = head; data[head] = e; size++; } else { head++; if (head>=maxSize) head = 0; data[head] = e; size++; } System.out.println("ok"); } public void push_back(int e) { if (size == maxSize) { System.out.println("Deque is full."); return; } else if (size==0) { head = end; data[end] = e; size++; } else { end--; if (end<0) end = maxSize-1; data[end] = e; size++; } System.out.println("ok"); } public void clear() { head = 0; end = 0; size = 0; System.out.println("ok"); } public int size() { return size; } public int back() { if (size!=0) return data[end]; else return -1; } public int front() { if (size!=0) return data[head]; else return -1; } public int pop_back() { if (size!=0) { int tmp = data[end]; end++; if (end>=maxSize) end = 0; size --; return tmp; } else return -1; } public int pop_front() { if (size!=0) { int tmp = data[head]; head--; if (head<0) head = maxSize - 1; size --; return tmp; } else return -1; } } public class task { static public void main (String[] args) throws IOException { Deque dq = new Deque(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str; while((str = br.readLine()) != null) { String[] inp = str.split(" "); if (inp[0].equals("push_front")) { dq.push_front(Integer.parseInt(inp[1])); } else if (inp[0].equals("push_back")) { dq.push_back(Integer.parseInt(inp[1])); } else if (inp[0].equals("pop_back")) { System.out.println(dq.pop_back()); } else if (inp[0].equals("pop_front")) { System.out.println(dq.pop_front()); } else if (inp[0].equals("front")) { System.out.println(dq.front()); } else if (inp[0].equals("back")) { System.out.println(dq.back()); } else if (inp[0].equals("size")) { System.out.println(dq.size()); } else if (inp[0].equals("clear")) { dq.clear(); } else if (inp[0].equals("exit")) { System.out.println("bye"); br.close(); return; } } } } |
Описание решения
Чтобы смоделировать работу дека, напишем соответствующий класс class Deque, который будет содержать следующие поля:
- int[] data — массив для хранения данных внутри дека;
- static final int maxSize = 10000 — статическое неизменное поле, содержащее максимальное количество элементов в деке (по условию задачи 10000);
- int size — текущее количество элементов в деке;
- int head, end — индексы первого (верхнего) и последнего (нижнего) элементов дека в массиве int[] data.
Так как дек — это структура, в которой элементы можно добавлять и удалять как в начало, так и в конец, то индексы первого и последнего элементов в массиве будут постоянно изменяться при добавлении/удалении в дек объектов. Поэтому крайне важно организовать модель так, чтобы при произвольном добавлении в начало и конец дека новых элементов, массив содержал эти элементы в правильном порядке, а в программе не возникало ошибки выхода за границы массива.
Это сделано следующим образом: изначально индексы первого и последнего элементов массива data равны 0, как и размер массива (это описывается в конструкторе класса Deque). При добавлении в начало дека нового элемента, индекс первого элемента int head будет смещаться на 1 вперед, пока не достигнет верхней границы массива (9999), затем начнет свой отсчет опять с нуля. При добавлении нового элемента в конец дека, смещаться будет индекс последнего элемента, причем вниз, пока не достигнет 0, затем продолжит с верхней границы массива. Такой подход дает возможность непрерывно добавлять и удалять в дек элементы, однако если количество элементов в деке станет максимальным ( if (size == maxSize)), добавить новый элемент уже не получится, для него нужно освободить место.
При запуске программы, сперва создается объект класса Deque dq = new Deque(), затем программа принимает входные данные while((str = br.readLine()) != null) и вызывает соответствующий метод класса Deque.
Описание методов класса:
- push_front и push_back — добавление в дек нового элемента. Если текущее количество элементов в деке равен максимально допустимому количеству элементов, добавления происходить не будет, а программа выдаст предупреждающее сообщение. Если дек не пустой, количество элементов увеличится на 1, а сам элемент будет размещен в массиве с соответствующим индексом head или end (в зависимости от того, куда добавляется элемент, в верх или в низ). Этот индекс, соответственно, увеличится или уменьшится на 1. Если количество элементов в деке равно 0, вставка произойдет точно так же, однако индексы head и end останутся прежними, указывая таким образом на один и тот же элемент. После успешной вставки на экран будет выведено сообщение «ok».
- pop_front и pop_back — если в деке есть хотя бы 1 элемент, функция возвратит из массива data элемент с индексом head или end (соответственно для каждого метода), при этом этот индекс «двигается» в обратную для себя сторону (индекс верхнего элемента уменьшается, индекс нижнего — увеличивается), а количество элементов в деке уменьшается на 1. Если же дек пуст, функция вернет значение -1.
- back и front — методы, аналогичные pop_front и pop_back, с тем отличием, что не будут изменять индексы head и end или количество элементов в деке, а просто возвратят нужные элементы.
- size — возвращает количество элементов в деке ( return size;).
- clear — приравнивает поля size, head и end к 0, имитируя удаление из дека всех элементов. Выводит на экран сообщение «ok».
- exit — выводит на экран сообщение «bye», после чего программа завершит работу.
Посмотреть решение задания можно на сайте e-olymp.