Алгоритмы и структуры данных на С++. Аксёнова Е.А - 22 стр.

22                              Глава 2. Линейные структуры данных


   Некоторые операции со списками эффективнее реализуются при
связном представлении, а некоторые – при последовательном, так на-
пример:

     1) при связном представлении легко включать и исключать эле-
        менты, при последовательном для этого необходимо сдвигать
        информацию;
     2) доступ к k-му элементу быстрее при последовательном представ-
        лении;
     3) при связном представлении легко объединять списки и разби-
        вать их на части.

   На практике часто применяются некоторые частные случаи линей-
ных списков.
   Стек (LIFO (Last In First Out) список) – это линейный список,
в котором все включения и исключения (и обычно всякий доступ)
элементов происходят на одном конце списка.
   Очередь (FIFO (First In First Out) список) – это линейный спи-
сок, в котором все включения элементов происходят на одном конце
списка, а все исключения (и обычно всякий доступ) – на другом.
   Дек – это линейный список, в котором все включения и исключе-
ния элементов производятся на обоих концах списка.



     2.2. Последовательное представление линейных
                        списков

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




                               Рис. 2.2