В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью.
Стек — это конечная последовательность некоторых однотипных элементов — скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >. Допустимыми операциями над стеком являются:
Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху.
Очередь — это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине). Двусторонняя очередь — это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов.
Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами. Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.
Например, выражение
(6+8)*5-6/2
в польской инверсной записи имеет вид
6 8 + 5 * 6 2 / -
Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид
S = < >;  <6>;  <6,8>;  <14>;  <14,5>;  <70>;
<70,6>;  <70,6,2>;  <70,3>;  <67>.
Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 — операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l.
float eval (float *m, int l)
  { int p,n,i;
    float stack[50],c;
      for(i=0; i < l ;i++)
       if ((n=m[i])<0)
         {  c=st[p--];
            switch(n)
            { case -1:  stack[p]+=c;  break;
              case -2:  stack[p]-=c;  break;
              case -3:  stack[p]*=c;  break;
              case -4:  stack[p]/=c;
            }
         }
       else stack[++p]=n;
      return(stack[p]);
  }

Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1." то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека — чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.
#include
typedef struct st    /* объявление типа STACK */
{ char ch;
  struct st *ps;   } STACK;
main()
{  STACK *p,*q;
   char a;
   p=NULL;
   do /* заполнение стека */
     { a=getch();
       q=malloc(sizeof(STR1));
       q->ps=p; p=q;
       q->ch=a;
     }  while(a!='.');
   do  /* Печать стека */
     { p=q->ps;free(q);q=p;
       printf("%c",p->ch);
     } while(p->ps!=NULL);
}
Очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (firet-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO. Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помешенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.
Очереди очень часто встречаются в реальной жизни, например, около банкоматов и в ресторанах быстрого обслуживания. Чтобы представить себе работу очереди, введем две функции: qstore() и qretrieve() (от "store" — "сохранять, «retrieve"— "получать"). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В ледующей таблице показано действие последовательности таких операций.
Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Поэтому после извлечения всех элементов очередь будет пуста.
В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.
Чтобы проиллюстрировать работу очереди, создадим простую программу планирования встреч. Эта программа позволяет сохранять информацию о некотором количестве встреч; потом по мере прохождения каждой встречи она удаляется из списка. Для упрощения описание встреч ограничено 255 символами, а количество встреч - произвольным числом 100.
При разработке этой простой программы планирования необходимо прежде реализовать описанные здесь функции qstore () и qretrieve (). Они будут хранить указатели на строки, содержащие описания встреч.
Таблица 1    
ДействиеСодержимое очереди
qstore(A)A
qstore(B)А В
qstore(C)А В С
qretrieve() возвращает А  В С
qstore(D)В С D
qretrieve() возвращает В C D
qretrieve() возвращает СD

#define MAX 100
char *p[MAX];
int  spo s =. 0;   
int  r pos = 0;
/* Сохранение встречи. */ void qstore{char *q)
{
if (spos==MAX)    {
printf("Список переполнен\n");
return; 
}
p[spos]= q; spos++;
}
/*  Получение  встречи.   */ char  *qretrieve()
if(rpos==spos)   {

printf ("Встреч больше нет.\n"); return '\0';
}
rpos++;
return p[rpos-l];
}
Этим двум функциям требуются две глобальные переменные: spos, в которой хранится индекс следующего свободного места в списке и rpos, в которой хранится индекс следующего элемента, подлежащего выборке. С по¬мощью этих функций можно организовать очередь данных другого типа, просто по¬меняв базовый тип обрабатываемого ими массива.
Функция qstore() помешает описания новых встреч в конец списка и проверяет не переполнен ли список. Функция qretrieve() извлекает встречи из очереди, если таковые имеются. При назначении встреч увеличивается значение переменной spos а по мере их прохождения увеличивается значение переменной rроs. По существу, rpos "догоняет" spos в очереди. Если rpos и spos равны, назначенные события отсутствуют. Даже несмотря на то, что функция qretrieve()не уничтожает храня¬щуюся в очереди информацию физически, эту информацию можно считать уничто¬женной, так как повторно получить доступ к ней невозможно.