У вас вопросы?
У нас ответы:) SamZan.net

Лекция 19 Стеки Стеки Стек stck это упорядоченная последовательность элементов в которой выполняютс

Работа добавлена на сайт samzan.net: 2015-07-05

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 20.2.2025

Лекция 19. Стеки

Стеки

Стек (stack) - это упорядоченная последовательность элементов, в которой выполняются операции включения и исключения элемента по принципу LIFO (Last-In-First-Out) - "последним пришел - первым ушел", т. е. включение и исключение всегда происходят в одном конце (рис. 19.1). Этот конец называют верхом, противоположный - дном стека. Другие названия стека: магазин (по аналогии с магазином пистолета или автомата), очередь типа LIFO.

S[1]

S[2]

S[k]





Дно

Верх

Включение и

исключение

элементов

Рис. 19.1. Стек

Примеры стека: заднее сиденье легкового автомобиля, когда посадка и высадка происходит с одной стороны; стопка подносов в столовой, где подносы берутся и кладутся только сверху.

Назовем некоторые из многочисленных применений стека.

1. Переупорядочивание данных для обработки в порядке, отличающемся от порядка поступления.

2. Запоминание подзадач некоторой задачи с последующим решением подзадач в порядке, обратном порядку их возникновения (см. алгоритм  обхода дерева в глубину).

3. Области локальных данных (включая параметры и адреса возврата) вложенных вызовов подпрограмм.

4. Области локальных данных вложенных блоков программы.

5. Трансляция скобочных структур: выражений, вложенных ветвлений, циклов, блоков и всей программы.

6. ЭВМ и микрокалькуляторы с безадресной магазинной памятью.

7. Стек в мозге человека (7 ± 2 элемента). Психологи обнаружили, что человек может воспринимать именно такую глубину вложенности, например, придаточных предложений фразы или такое количество рассматриваемых вместе дел, понятий и т. п.

Типовые операции над стеком:

1. Инициализация (создание, подготовка к работе);

2. Вталкивание (включение) элемента - PUSH;

3. Выталкивание (исключение) элемента - POP;

4. Проверка пустоты стека;

5. Проверка переполнения стека;

6. Доступ к вершине (получение / изменение значения последнего поступившего элемента).

Представление стека в виде вектора

Чаще всего стек представляется в виде вектора с указателем (рис. 19.2).

Рис. 19.2. Хранение стека в виде вектора

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

Два стека удобно хранить в одном векторе, заполняя их навстречу друг другу (рис. 19.3).

Рис. 19.3. Хранение двух стеков в одном векторе

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

Программирование операций на языке С (С++)

1. Описание данных для представления стека вектором

#define N 100   /* Максимальная длина стека    */

тип-элемента st[N];  /* Отображающий вектор стека    */

int ist;    /* Указатель стека (индекс последнего элемента) */

2.  Инициализация (создание) пустого стека:

ist = -1;

Как и в очереди, при невозможности выполнения операции действия зависят от решаемой задачи. Обычно пустота стека используется как условие окончания алгоритма, а переполнение означает ошибку.

3. Выталкивание из стека элемента и присваивание его величине X (обозначим эту операцию  Стек ==> X; без запоминания элемента: Стек ==>):

тип-элемента  X;    /* Значение вытолкнутого элемента  */

. . .

if (ist >= 0)     /* В стеке есть элементы    */

{  X = st[ist];    /* Получение значения     */

   ist--;     /* Выталкивание элемента    */

}

else  . . .     /* Стек пуст      */

4. Вталкивание в стек элемента, равного X (обозначим эту операцию Стек <== X):

тип-элемента  X;    /* Вталкиваемое значение   */

. . .

if (ist < N-1)    /* Есть место в стеке    */

{  ist++;     /* Увеличение стека    */

   st[ist] = X;    /* Запись x в вершину стека   */

}

else  . . .     /* Стек переполнен    */

Задача. Дано арифметическое выражение длиной до 80 символов, оканчивающееся пробелом. Выражение содержит целые числа без знака и знаки операций +, -, *, /.  Вычислить значение выражения.

Например, входной текст: 130+25*3-160/20*6  .

Результат: 157.

Метод решения  задачи  основан на использовании стека операндов, операций и приоритетов.  Операции * и / имеют одинаковый  приоритет, причем  более высокий,  чем операции + и - .  При просмотре выражения происходит выделение очередного операнда (числа), преобразование его из  символьной  формы  в  целочисленную  и запись в стек полученного  числа, следующей за ним операции и присвоенного ей приоритета. Пока в  стеке более одного элемента и приоритет последней операции оказывается не выше приоритета предыдущей операции  в  стеке,  происходит  выполнение  соответствующих операций над двумя последними операндами стека и удаление ненужных элементов из стека.  В конце концов, когда просмотр выражения закончится,  первый элемент стека и будет искомым  результатом.

На рис. 19.4  показано, как меняется содержимое стека.

 операнд    приор-т

       оп-ция

   ┌───┬────┬───┐  ┌───┬─┬─┐  ┌───┬─┬─┐  ┌───┬─┬─┐  ┌───┬─┬─┐  ┌───┬─┬─┐

   │130│  + │ 1 │  │130│+│1│  │205│-│1│  │205│-│1│  │205│-│1│  │157│ │0│

   │ 25│  * │ 2 │  │ 75│-│1│  │160│/│2│  │  8│*│2│  │ 48│ │0│  │   │ │ │

   │  3│  - │ 1 │  │   │ │ │  │ 20│*│2│  │  6│ │0│  │   │ │ │  │   │ │ │

   └───┴────┴───┘  └───┴─┴─┘  └───┴─┴─┘  └───┴─┴─┘  └───┴─┴─┘  └───┴─┴─┘

      

      Рис. 19.4. Пример заполнения стека операндов, операций и приоритетов.

В программе стек реализован в виде трех параллельных массивов.

Программа:

    #include <stdio.h>

    #include <conio.h>

        /*──────────────────────────────────*/

        /*   Функция выделения числа и преобразования его из     */

        /*    символьной формы представления в целочисленную  */

        /*──────────────────────────────────*/

    int Сhislo ( char text [], int *i )

           /* Входные данные:                                          */

           /*      text - символьная строка,                         */

           /*      *i - индекс первой цифры числа в строке text.  */

           /* Выходные данные:                                      */

           /*      *i - индекс следующего после числа символа.  */

           /* Функция возвращает целое число                       */

    {   int c=0;   /* возвращаемое значение  */

         while (text[*i]>='0' && text[*i]<='9')

         {  c=c*10+(text[*i]-'0');

             (*i)++;

         }

         return c;

     }

             /*───────────────────*/

             /*       Главная функция                 */

             /*───────────────────*/

    main()

    {   char  text [80]; /* вх. текст - арифм. выражение */

         int   i ;              /* индекс массива text */

         float  opd [3];  /* стек операндов   */

         char   opc [3];  /* стек операций    */

         int    pr [3] ;     /* стек приоритетов */

         int    j = -1 ;     /* указатель стека */

         printf ("\nВведите арифметическое выражение.\n");

         gets (text);

         i=-1;

         do

         {  i++;

               /* запись числа, операции и ее приоритета в стек */

             opd[++j] = Сhislo(text,&i);  opc[j] = text[i];

             switch  (text[i])

             {

                 case '+':

                 case '-': pr[j]=1; break;

                 case '*':

                 case '/': pr[j]=2; break;

                 case ' ' /* пробел */: pr[j]=0;

             }

             while  (j>0 && pr[j]<=pr[j-1])

             {       /* выполнение соответствующей операции */

                 switch  (opc[j-1])

                 {  case '+' :  opd[j-1] = opd[j-1] + opd[j]; break;

                     case '-' :   opd[j-1] = opd[j-1] - opd[j];  break;

                     case '*' :  opd[j-1] = opd[j-1] * opd[j]; break;

                     case '/' :   opd[j-1] = opd[j-1] / opd[j];

                 }

                     /* удаление выполненной операции из стека */

                 opc[j-1]=opc[j];  pr[j-1]=pr[j];  j=j-1;

             }

         }

         while (text[i]!=' ');

         printf ("Результат: %.2f\n",opd[0]);

         getch();

   }

       

       

    

  Результаты тестирования:

              

   Введите арифметическое выражение.

   9/4-12

   Результат: -9.75

   Введите арифметическое выражение.

   10*2/5+6/3

   Результат: 6.00

   Введите арифметическое выражение.

   130+25*3-160/20*6

   Результат: 157.00

   Введите арифметическое выражение.

   2345

   Результат: 2345.00

      

Представление стека в виде списка

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

Рис. 19.5 Стек в виде списка

Контрольные вопросы  и  упражнения

1. Что такое стек?

2. Как можно хранить стек?

3. Опишите стек, состоящий из целых чисел, в виде списка. Опишите отдельные функции вталкивания элемента в стек и выталкивания элемента из стека. Приведите примеры их вызова.

Выполнение контрольных заданий

             

1. Получите у преподавателя индивидуальное задание.

2. Составьте программу на языке С и подберите тесты для проверки программы на компьютере.

3. Отладьте программу на компьютере.

5. Оформите и сдайте отчет.

Контрольные задания

1. Дано арифметическое выражение длиной до 20 символов,  оканчивающееся пробелом. Выражение содержит однобуквенные идентификаторы и  знаки  операций  +,  -,  *,  /.  Преобразовать  выражение в обратную  польскую запись, используя стек операций и приоритетов.

Пример.

Вх. текст:  a*b+c/d-e

Результат:  ab*cd/+e-

2. Дано  арифметическое  выражение   в   постфиксной   (обратной польской) записи длиной до 20 символов, оканчивающееся пробелом. Получить эквивалентную последовательность  элементарных  присваиваний, содержащих одну арифметическую операцию (используя стек операндов).

а) В  левой части операторов присваивания использовать вспомогательные переменные R1,R2,R3,...

Пример.

Вх. текст:    abc*+def+/-

Результат:   R1:=b*c

R2:=a+R1

R3:=e+f

R4:=d/R3

R5:=R2-R4

б) В левой части операторов присваивания использовать  вспомогательные переменные R1,R2,R3,..., сократив до минимума число этих переменных.

Пример.

Вх. текст:    abc*+def+/-

Результат:   R1:=b*c

R1:=a+R1

R2:=e+f

R2:=d/R2

R2:=R1-R2

3. Дано арифметическое выражение длиной до 30 символов,  оканчивающееся знаком равенства.  Выражение содержит знаки операций +,  -, *,  / и однозначные целые числа и представлено в  обратной  польской  записи. Вычислить значение выражения, используя стек операндов.

Пример.

Вх. текст: 345+2*63/-+= 19

                                      результат

4. Дано скобочное выражение длиной до 50 символов,  оканчивающееся пробелом.  Напечатать попарно порядковые номера  соответствующих  открывающих и закрывающих скобок в выражении.

Пример.

                 1  4   8 10  14   19      27

Вх. текст:   (a+(b+c)/(a-b)*(x+(y+2)**3))/2

Результат:   4   8

10  14

19  23

16  27

1  28

Указание. Для запоминания номеров открывающих скобок использовать стек.

5. Дана последовательность чисел, оканчивающаяся нулем.

а) Напечатать только отрицательные числа из этой  последовательности, причем, если подряд идет несколько отрицательных чисел, печатать их в обратном порядке. Например:

Вх. последовательность: 5 -1 -20 -8 10 14 -3 5 -2 -13 -7 0

Результат:                        -8 -20 -1 -3 -7 -13 -2

Указание. Последовательность подряд расположенных отрицательных  чисел помещать в стек.

б) Напечатать только положительные числа из этой  последовательности, причем, если подряд идет несколько положительных чисел, печатать их в обратном порядке. Например:

Вх. последовательность: -2 5 10 20 15 -4 -6 2 -10 3 1 4 -5 0

Результат:                         15 20 10 5 2 4 1 3

Указание. Последовательность подряд расположенных положительных  чисел помещать в стек.

6. Дана  последовательность из n слов (n<=20) в алфавитном порядке. Длина каждого слова не более 10 букв. Напечатать слова, начинающиеся с одной и той же буквы в обратном порядке, используя стек. Например:

Вх. последовательность:            Результат:

Август    апрель

Апрель    август

Май     море

Март     март

Море     май

Лето     лето

194


A[1]

. . .

A[k]

B[m]

. . .

B[1]

Дно

Верх

тек  A

Свободная память

Указатель стека A

Верх

Дно

Стек  B

Указатель стека B

S[k]

S[1]      0

 . . .

Верх

Дно

Указатель списка




1. Сегодня статус PR как науки признается далеко не всеми учеными
2. культурная эпоха смотрит на мир своими глазами и создает собственную картину окружающего мира и собственное
3. а удучи колдуньей народа фей я являюсь мифом и жила за гранью человеческих приходов и уходов человеческих
4. Лабораторна робота 6 Аналіз вимог до ПЗ
5. Чарльз Диккенс
6. Реферат- Охрана труда несовершеннолетних и инвалидов.html
7. Местное самоуправление в зарубежных странах
8. Тема 3 Аналіз трудових показників як основа аудиту персоналу 1
9. Все хорошо прекрасная маркиза
10. Основні етапи становлення й розвитку економічної науки в СРСР Сучасна світова економічна думка формувала.html