Программирование на языке С - Стеки и очереди

 

2.1.5. Стеки и очереди

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

Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=<>.

Допустимыми операциями над стеком являются:

- проверка стека на пустоту S=<>,

- добавление нового элемента Sn+1 в конец стека - преобразование < S1,...,Sn> в < S1,...,Sn+1>;

- изъятие последнего элемента из стека - преобразование < S1,...,Sn-1,Sn> в < S1,...,Sn-1>;

- доступ к его последнему элементу Sn, если стек не пуст.

Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху.

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

Двусторонняя очередь - это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов.

Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами.

Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.

Например, выражение

                       (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);
  }