Задача
Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и popпрограмма должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Входные данные
Описаны в условии.
Выходные данные
Описаны в условии.
Тесты:
| ввод | вывод | ввод | вывод |
| push 7 clear push 4 back push 1151 back pop back size exit |
ok ok ok 4 ok 1151 1151 4 1 bye |
push 2 push 7 back pop pop back push 1 back pop exit |
ok ok 7 7 2 error ok 1 1 bye |
| pop push 42 back size pop size push 17 push 19 push 24 back size clear size exit |
error ok 42 1 42 0 ok ok ok 24 3 ok 0 bye |
back size clear size back pop push 2 pop push 1 size back exit |
error 0 ok 0 error error ok 2 ok 1 1 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 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 |
#include <iostream> using namespace std; const short int link_array_size = 30; //количество элементов в одном звене struct link //звено списка { int array [link_array_size]; //массив, элементы которого и являются элементами стека short int capacity; //свободное место в массиве link* next; //адресс следующего звена link () //создание звена { capacity = link_array_size; } void link_push (int n) { capacity--; array [capacity] = n; } int link_pop () { capacity++; return array[capacity-1]; } }; struct stack //сам стек { link* head; //указатель на первое звено int s; //количество элементов в стеке stack (link* h = NULL) // создание стека { head = h; s = 0; } void add_link() //добавление звена { link* a = new link; a->next = head; head = a; } void destroy_link() //удаление звена { link * a = head; head = a->next; delete a; } void push (int n) { if ((head == NULL)||(head->capacity == 0)) { add_link(); } head->link_push(n); s++; } int pop () { if (s>0) { int n = (head->link_pop()); if (head->capacity == link_array_size) { destroy_link(); } s--; return n; } else { throw 0; } } int back() { if (s>0) { return head->array[head->capacity]; } else { throw 0; } } int size() { return s; } void clear() { while (head!=NULL) { destroy_link(); } s = 0; } }; int main() { string s; stack Q; while (cin>>s) { if (s == "push") { int n; cin>>n; Q.push(n); cout<<"ok"<<endl; } if (s == "pop") { try { cout<<Q.pop()<<endl; } catch (int e) { cout<<"error"<<endl; } } if (s == "back") { try { cout<<Q.back()<<endl; } catch (int e) { cout<<"error"<<endl; } } if (s == "size") { cout<<Q.size()<<endl; } if (s == "clear") { Q.clear(); cout<<"ok"<<endl; } if (s == "exit") { cout<<"bye"<<endl; break; } } return 0; } |
Решение
В данном решении стек состоит из объектов, далее именуемых звеньями, каждый из которых состоит из массива, переменной, отвечающей свободному месту в массиве, ссылки на следующее звено. Кроме того, у звена есть метод для его создания, методы push и pop. В этих методах, кроме их прямой функции, отслеживается количество свободного места в звене. С этим всем работает сам стек. В самом стеке есть указатель на первое звено (звено, в которое был добавлен последний элемент, который все еще есть в стеке) и переменная S, отвечающая количеству элементов в стеке. Еще есть такие методы, как создание и удаление звена, а также все методы указанные в условии. Создается звено, если нужно что-то добавить в стек и в текущих звеньях уже нет свободного места, а удаляется, если после извлечения чего-то из стека первое звено пустое (или при методе clear). Для этого и нужна переменная отвечающая свободному месту в звене.
Теперь немного о методах, указанных в условии. Во-первых, все методы, меняющие число элементов в стеке, соответственно влияют на переменную, этому числу отвечающую, а size ее просто возвращает. Методы push и pop непосредственно для выполнения своей функции обращаются к своим аналогам в первом звене. Методы pop и back проверяют в начале, не пуст ли стек, через переменную S. Back получает значение последнего элемента, работая непосредственно с массивом первого звена. exit вообще не создан, как метод, а обрабатывается непосредственно в функции Main(). Собственно, сама эта функция только принимает и обрабатывает через условные операторы запросы, а потому описывать ее нет смысла (см. код программы).
Немного слов для обобщения. Если бы стек бы основан просто на массиве, для неограниченности пришлось бы каждый раз, когда в текущем массиве заканчивается место, копировать уже имеющиеся данные в новый массив большего размера. Кроме того, возникла бы необходимость в очень большом цельном участке памяти. Если бы в этой реализации стека вообще не использовались массивы, а просто у каждого элемента была ссылка на следующий, это бы очень увеличило затраты памяти, т.к. эти ссылки в количестве, равном количеству элементов в стеке, нужно где-то хранить. В данном же решении нужно какое-то количество цельных, но не таких больших участков памяти, не так много памяти под ссылки на следующее звено, а при заполнении имеющихся массивов ничего не приходится переписывать — просто добавляется еще один. Примечание: эффективность для разных задач зависит от размеров массива в звене.
задача взята с сайта e-olymp