Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 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
. . .
Верх
Дно
Указатель списка