Задача. Одним из наиболее часто встречающихся видов списка является стек-список, в котором все включения и исключения элементов делаются только на одном его конце — вершине стека. Механизм функционирования стека хорошо отражен в другом его названии — список типа «LIFO» (last in first out) -«последним вошел — первым вышел»).
При работе со стеком предполагаются две операции: занесение очередного элемента в вершину стека и удаление элемента, находящегося в вершине стека. Тем самым операция удаления элемента из стека может быть применена только к элементу, помещенному в стек самым последним. И, следовательно, любой элемент не может быть удален из стека раньше, чем будут удалены все элемента, помещенные в стек после него.
Составить процедуры, реализующие операции занесения элемента в стек и удаления элемента из его вершины.
Тесты:
| Ввод | Вывод | Комментарий |
| push 5push 7
pop push 11 pop exit |
okok
7 ok 11 bye |
Пройден |
| push 1pop
pop push 15 pop exit |
ok1
error ok 15 bye |
Пройден |
| poppush 7
push 9 push 9 push 1 pop pop pop pop exit |
errorok
ok ok ok 1 9 9 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> using namespace std; struct stack { int size=0;//размер int storage[1000];//массив void push (int n)//добавление эл-та { storage[size]=n; size++; } int pop () //удаление эл-та { int b=storage[size-1]; size--; return b; } }; int main () { stack st; string s; while (55) { cin >> s; if (s=="push") { int n; cin >> n; st.push(n); cout << "ok\n"; } if (s=="pop") { if (st.size==0) { cout << "error\n"; } else cout << st.pop() << endl; } if (s=="exit") { cout << "bye\n"; break; } } return 0; } |
Решение:
В структуре stack, реализованной с помощью массива, опишем операции добавления элемента в стек и удаления элемента из его вершины.
Данные операции выполняются после получения соответствующих команд. В программе будем выполнять дополнительную проверку, чтобы избежать удаления элемента из пустого стека.
Программа завершает работу после получения команды exit.
С работой программы можно ознакомиться здесь.
А исключительные ситуации при переполнении стека или попытке извлечения элемента из пустого стека?