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. Какво извежда първият ред?
  2. Какво извежда вторият ред след двете премахвания?
  3. Коя структура пази реда на пристигане при обслужване?
  4. Коя структура е подходяща за отмяна на последната редакция и защо?

Отговори за самопроверка

Отговор 1

9 4. Върхът е последно добавеният номер, а началото на опашката е първо добавеният.

Отговор 2

4 9. След премахването във всяка структура остава по един номер.

Отговор 3

Опашката. Документ №4 пристига първи и се обслужва първи.

Отговор 4

Стекът. Последната редакция се намира на върха.

Изтегли main.cpp.

В речника Стек · Опашка.