Стек неограниченного размера
Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Пояснение: Размер стека должен быть ограничен только размером доступной оперативной памяти.
Решение
Предлагается реализация стека через связные списки.
Положительные стороны:
В условии сказано, что стек потенциально может занимать всю оперативную память, поэтому при такой реализации мы будем экономнее выделять память и не получим WA на тестах, которые не вместились бы в фиксированный размер массива.
Отрицательные стороны:
Конструктор срабатывает для каждого узла достаточно медленно, решение уступает в скорости связному списку массивов.
Ссылка на задачу. Ссылка на засчитанное решение.
Код программы:
|
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 |
#include <iostream> #include <string> using namespace std; struct node { int value=0; node* prev=NULL; node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке }; struct stack { int cnt=0; node* top=NULL; void push (int n) { top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину cnt++; } bool empty() { return cnt == 0; } int pop() { node* prev = top->prev; // записываем предыдущий узел во временную переменную int topVal = top->value; delete top; // удаляем последний элемент стека top = prev; // говорим, что он теперь равен прдыдущему cnt--; return topVal; } int back() { return top->value; } int size() { return cnt; } void clear() { while (!empty()) pop(); } }; int main() { ios::sync_with_stdio(false); string t; int val; stack s; while (1) { cin >> t; if (t=="push") { cin >> val; s.push(val); cout << "ok" << endl; } else if (t=="pop") { if (s.empty()) cout << "error" << endl; else { val = s.pop(); cout << val << endl; } } else if (t=="back") { if (s.empty()) cout << "error" << endl; else cout << s.back() << endl; } else if (t=="size") cout << s.size() << endl; else if (t=="clear") { s.clear(); cout << "ok" << endl; } else if (t=="exit") { cout << "bye" << endl; break; } } return 0; } |
Очень хорошо.
Добавьте, пожалуйста, «связные списки» или «linked list» в метки. И допишите про положительные и отрицательные стороны.
Метку добавила, положительные и отрицательные стороны описала.