Задача. Реализуйте структуру данных «стек». Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
- push [latex]n[/latex] — Добавить в стек число [latex]n[/latex] (значение [latex]n[/latex] задается после команды). Вывести ok.
- pop — Удалить из стека последний элемент. Программа должна вывести его значение.
- back — Вывести значение последнего элемента, не удаляя его из стека.
- size — Вывести количество элементов в стеке.
- clear — Очистить стек и вывести ok.
- exit — Вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.
Тесты
| № | Входные данные | Выходные данные |
| 1 | push 2 push 3 push 5 back size pop size push 7 pop clear size exit |
ok ok ok 5 3 5 2 ok 7 ok 0 bye |
| 2 | push 7 size push 1 pop back exit push 4 pop |
ok 1 ok 1 7 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 |
#include <iostream> #include <string> using namespace std; #define SIZE 100 struct stack { int storage[SIZE]; int cursor = 0; // указатель на верхнюю незаполненную ячейку void push (int n) { storage[cursor] = n; cursor++; } int pop () { return storage[--cursor]; } int back () { return storage[cursor-1]; } unsigned int size () { return cursor; } void clear () { cursor = 0; } }; int main () { stack s; string str; int n; while (cin >> str) { if (str == "push") { cin >> n; s.push(n); cout << "ok" << endl; } else if (str == "pop") cout << s.pop() << endl; else if (str == "back") cout << s.back() << endl; else if (str == "size") cout << s.size() << endl; else if (str == "clear") { s.clear(); cout << "ok" << endl; } else if (str == "exit") { cout << "bye" << endl; break; } } return 0; } |
Для запроса на выполнение нажать здесь.
Решение
Реализуем стек с помощью массива, указателя на на верхнюю незаполненную ячейку массива ([latex]cursor[/latex]) и функций, с помощью которых выполняются команды push, pop, back, size, clear:
- функция push выполняет запись в ячейку с номером [latex]cursor[/latex] элемента [latex]n[/latex];
- функция pop возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом удаляя его из стека;
- функция back возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом не удаляя его из стека;
- функция size возвращает значение [latex]cursor[/latex], то есть размер стека;
- функция clear присваивает [latex]cursor[/latex] значение [latex]0[/latex].
Команда exit выполнена с помощью оператора [latex]break[/latex], который заканчивает выполнение цикла, в котором запрашиваются команды.
Ссылка на засчитанное решение.
Зачтено.
Однако, Вы совершенно забыли сделать описание программы (две строчки ни о чем не считаются).
Спасибо, Игорь Евгеньевич, я исправила.