Лабораторная работа №13. Контейнер List. Выполнение операций над списками

Последовательное представление линейных списков
Стек
Для последовательного представления одного стека достаточно иметь указатель top на вершину стека (рис. 2).

Рис. 2 Указатель top

При работе с двумя стеками возможны два способа организации (рис. 3):

1. 
   выделить каждому стеку отдельную область памяти;
   
2. 
   расположить стеки в памяти так, чтобы они росли навстречу друг другу (этот способ является оптимальным).
   

Рис. 3 Два способа организации

При работе с тремя стеками возможны следующие способы реализации (рис. 4):

1. 
   выделить каждому стеку отдельную область памяти;
   
2. 
   расположить два стека так, чтобы они росли навстречу друг другу, а третий расположить отдельно;
   
3. 
   расположить два стека так, чтобы они росли навстречу друг другу с концов выделенной для работы области памяти, а третий стек будет расти одновременно навстречу им обоим.
   

Рис. 4 Способы реализации при работе с тремя стеками
Очередь
При последовательном представлении очереди необходимо хранить указатели на начало F и конец очереди R (рис. 5). Если указатель на конец или начало доходит до конца области памяти, то он перемещается на начало области памяти (рис. 6). Такая очередь называется циклической.

Рис. 5 Указатели на начало F и конец очереди R



Рис. 6 Циклическая очередь

При работе с двумя очередями возможны два способа организации:

1. 
   выделить каждой очереди отдельный кусок памяти (рис. 7);
   

Рис. 7 Выделение каждой очереди отдельный кусок памяти

2. 
   очереди двигаются друг за другом по кругу (рис. 8).
   

Рис. 8 Очереди двигаются друг за другом по кругу