На этом шаге мы дадим общую характеристику списков магазинного типа .
В практике информационного моделирования часто используются линейные списки, в которых включение, исключение или доступ к звеньям почти всегда производится в первом или последнем звеньях.
Назовем списком магазинного типа линейный список, все звенья которого вставляются и удаляются только с одного или обоих концов списка. Списки магазинного типа подразделяются на очереди, стеки и деки.
Очередь - список магазинного типа, в котором все включения производятся на одном конце списка, а все исключения делаются на другом его конце.
Очередь иногда называют циклической памятью или списком типа FIFO ("First In - First Out" - "первым включается - первым исключается").
Мы часто будем использовать термины начало и конец очереди: информация помещается в конец очереди и удаляется в момент, когда, наконец, достигает ее начала. Изобразим это схематически:
Рис.1. Очередь
Стек - список магазинного типа, в котором все включения и исключения звеньев делаются в одном конце списка.
Из стека мы всегда исключаем "младший" элемент из имеющихся в списке (тот элемент, который был включен позже других). Для очереди справедливо в точности противоположное правило: исключается всегда самый "старший" элемент; элементы "покидают" список в том порядке, в котором они в него вошли.
Существуют и другие названия стека: магазин, список типа LIFO ("Last In - First Out" - "последним включается - первым исключается"); "пуш-даун" список ("push-down"), реверсивная память, гнездовая память.
Рис.2. Стек
Дек ("Double-Ended Queue" - "двухсторонняя очередь") - список магазинного типа, в котором все включения и исключения звеньев делаются на обоих концах списка.
Очевидно, что дек обладает большей общностью, чем стек или очередь; он имеет некоторые общие свойства с колодой игральных карт.
Замечание. Понятие стек было введено А.М.Тьюрингом в 1947 г. и названо им реверсивной памятью (оно использовалось для связи подпрограмм). Термин "дек" был введен Швеппе (E.J.Schweppe).
Со следующего шага мы начнем знакомиться с очередью.
