Задача
Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
- push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
- pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
- front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
- size — Программа должна вывести количество элементов в очереди.
- clear — Программа должна очистить очередь и вывести ok.
- exit — Программа должна вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.
Данную задачу также можно найти здесь.
Входные данные
Описаны в условии. Смотрите также тесты, расположенные ниже.
Выходные данные
Описаны в условии. Смотрите также тесты, расположенные ниже.
Тесты
| № | Входные данные | Выходные данные |
| 1 | push 123 size push -5 pop exit |
ok 1 ok 123 bye |
| 2 | push 1 push 2 front push 42 pop exit |
ok ok 1 ok 1 bye |
| 3 | push 1 push 2 pop pop size exit |
ok ok 1 2 0 bye |
Код
|
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 |
#include <iostream> #include <string> using namespace std; struct queue{ int storage[100000]; int start; int finish; queue(){ start = 0; finish = 0; } void push(int n){ storage[finish] = n; finish++; } int pop(){ int a = storage[start]; start++; return a; } int front(){ return storage[start]; } int size(){ return finish - start; } string clear(){ finish = 0; start = 0; return "ok"; } string exit(){ return "bye"; } }; int main() { string a; queue x; while(cin >> a){ if(a == "push"){ int n; cin >> n; x.push(n); cout << "ok" << endl; } if(a == "pop"){ cout << x.pop() << endl; } if(a == "front"){ cout << x.front() << endl; } if(a == "size"){ cout << x.size() << endl; } if(a == "clear"){ cout << x.clear() << endl; } if(a == "exit"){ cout << x.exit() << endl; return 0; } } return 0; } |
Ход решения
Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.
Ссылка на засчитанное решение находится здесь.
Код на сайте ideone.com находится здесь.