111. Стек и опашка
Стекът обслужва последно добавения елемент първи (LIFO). Опашката обслужва първо добавения елемент първи (FIFO). И двете структури могат да се реализират с масив или свързани възли.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Два документа с номера 4 и 9 пристигат в този ред. Програмата пази номерата в стек и в опашка. push добавя, pop премахва достъпния елемент, top чете върха, а front чете началото. Всяко четене и премахване тук е върху непразна структура.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
#include <queue> // Включваме библиотеката за опашки от тип queue.
#include <stack> // Включваме библиотеката за стекове от тип stack.
using namespace std; // Така можем да пишем cout вместо std::cout.
int main() { // Оттук започва изпълнението на програмата.
stack<int> lastFirst; // Създаваме празен стек от цели числа.
queue<int> firstFirst; // Създаваме празна опашка от цели числа.
lastFirst.push(4); // С push слагаме 4 на върха на стека.
lastFirst.push(9); // Слагаме 9 върху досегашния връх.
firstFirst.push(4); // С push добавяме 4 в края на опашката.
firstFirst.push(9); // Добавяме 9 в края на опашката.
cout << lastFirst.top() << ' ' << firstFirst.front() << '\n'; // Печатаме върха на стека с top и началото на опашката с front.
lastFirst.pop(); // С pop махаме елемента от върха на стека.
firstFirst.pop(); // С pop махаме елемента от началото на опашката.
cout << lastFirst.top() << ' ' << firstFirst.front() << '\n'; // Отново печатаме върха на стека и началото на опашката.
} // Край на програмата.
- Какво извежда първият ред?
- Какво извежда вторият ред след двете премахвания?
- Коя структура пази реда на пристигане при обслужване?
- Коя структура е подходяща за отмяна на последната редакция и защо?
Отговори за самопроверка
Отговор 1
9 4. Върхът е последно добавеният номер, а началото на опашката е първо добавеният.
Отговор 2
4 9. След премахването във всяка структура остава по един номер.
Отговор 3
Опашката. Документ №4 пристига първи и се обслужва първи.
Отговор 4
Стекът. Последната редакция се намира на върха.