Страница 72-86 §2.2 номер 13, ГДЗ по информатике за 9 класс к учебнику Босовой

Стек

Стек характерен тем, что получить доступ к его элементам можно лишь с одного конца, называемого вершиной стека; иначе говоря: стек – структура данных типа «список», функционирующая по принципу LIFO (last in — first out, «последним пришёл — первым вышел»).

Графически его удобно изобразить в виде вертикального списка (см. рис.), например, стопки книг, где чтобы воспользоваться одной из них, и не нарушить установленный порядок, нужно поднять все те книги, что лежат выше нее, а положить книгу можно лишь поверх всех остальных.

Впервые стек был предложен в 1946 году Аланом Тьюрингом, как средство возвращения из подпрограмм. В 1955 году немцы Клаус Самельсон и Фридрих Бауэр из Технического университета Мюнхена использовали стек для перевода языков программирования и запатентовали идею в 1957 году. Но международное признание пришло к ним лишь в 1988 году.

Очередь – линейный список, в котором извлечение данных происходит из начала, а добавление – в конец списка.

Очередь организована по принципу FIFO (First In, First Out) – первым вошел, первым выйдет.

Работа с очередью реализуется при помощи динамических структур, для которых необходимо выделение и освобождение памяти.

Простой пример – очередь в кассу, если очереди нет, обсуживаешься сразу, иначе, становишься в ее конец.

Последовательно обслуживаются стоящие в начале очереди.

В течение дня очередь то увеличивается, то уменьшается и может отсутствовать.

Очереди организуются в виде односвязных или двухсвязных списков, в зависимости от количества связей (указателей) в адресной части элемента структуры.