Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Стеки и очереди
|
|
В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью.
Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >.
Допустимыми операциями над стеком являются:
- проверка стека на пустоту S=< >,
- добавление нового элемента Sn+1 в конец стека - преобразование < S1,..., Sn> в < S1,..., Sn+1>;
- изъятие последнего элемента из стека - преобразование < S1,..., Sn-1, Sn> в < S1,..., Sn-1>;
- доступ к его последнему элементу Sn, если стек не пуст.
Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху.
Очередь - это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине).
Двусторонняя очередь - это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов.
Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами.
Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.
Например, выражение
(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); }|
|