Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".
Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.
Стек можно организовать на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: линейный массив, типизированный файл, однонаправленный или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.
Выделим типовые операции над стеком и его элементами:
добавление элемента в стек;
удаление элемента из стека;
проверка, пуст ли стек;
просмотр элемента в вершине стека без удаления;
очистка стека.
Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал "Динамические структуры данных: списки").
{ Turbo Pascal, файл STACK.PAS } Unit Stack; Interface Uses Spisok; Procedure V_Stack(Var Versh : U; X : BT); Procedure Iz_Stack(Var Versh : U; Var X : BT); Function Pust(Versh : U) : Boolean; Function V_Vershine(Versh : U) : BT; Procedure Ochistka(Var Versh : U); Implementation Procedure V_Stack; Begin V_Nachalo(Versh, X) End; Procedure Iz_Stack; Begin Iz_Nachala(Versh, X) End; Function Pust; Begin Pust := Versh = Nil End; Function V_Vershine; Begin V_Vershine := Versh^.Inf End; Procedure Ochistka; Begin Spisok.Ochistka(Versh) End; Begin End. |
| /* C++, файл STACK.CPP */ #include "SPIS.CPP" Zveno *V_Stack(Zveno *Versh, BT X) { return V_Nachalo(Versh, X); } Zveno *Iz_Stack(Zveno *Versh) { return Iz_Nachala(Versh); } int SPust(Zveno *Versh) { return !Versh; } BT V_Vershine(Zveno *Versh) { return Versh->Inf; } Zveno *Chistka(Zveno *Versh) { while (!Pust(Versh)) Versh=Iz_Stack(Versh); return Versh; } |
Используя разработанные здесь библиотеки, решим задачу.
Пример. Написать программу, которая вычисляет как целое число значение выражений (без переменных), записаных (без ошибок) в постфиксной форме в текстовом файле. Каждая строка файла содержит ровно одно выражение.
Алгоритм решения. Выражение просматривается слева направо. Если встречается число, то его значение (как целое) заносится в стек, а если встечается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция и ее результат записывается в стек. В конце в стеке остается только одно число — значение всего выражения.
{ Turbo Pascal, файл ST2.PAS } Program St2; Uses Spisok, Stack; Const Znak = ['+', '-', '*', '/']; Var S, S1 : String; T : Text; I, N : Byte; X, Y : BT; Code : Integer; NS : U; Begin Write('Введите имя файла: '); ReadLn(S1); Assign(T, S1); ReSet(T); NS := Nil; While Not Eof(T) Do Begin ReadLn(T, S); I := 1; While I <= Length(S) Do Begin If S[I] In ['0'..'9'] Then Begin N := I; While S[I] In ['0'..'9'] Do I := I + 1; Val(Copy(S, N, I - N), X, Code); V_Stack(NS, X); End Else If S[I] In Znak Then Begin Iz_Stack(NS, X); Iz_Stack(NS, Y); Case S[I] Of '+' : X := X + Y; '-' : X := Y - X; '*' : X := X * Y; '/' : X := Y Div X End; V_Stack(NS, X) End; I := I + 1 End; Iz_Stack(NS, X); WriteLn(S, ' = ', X); End End. |
| /* C++, файл ST2.CPP */ #include "STACK.CPP" #include < string.h > #include < stdio.h > void main(void) { char S[255]; FILE *T; int I; BT X, Y; Zveno *NS; clrscr(); cout << "Введите имя файла: "; cin >> S; T=fopen(S, "r"); NS = NULL; while (!feof(T)) { fgets(S, 255, T); I = 0; while (I <= strlen(S)-1) { if (S[I]>='0'&&S[I]<='9') { X=0; while(S[I]>='0'&&S[I]<='9') {X=X*10+(S[I]-'0'); I++;} NS=V_Stack(NS, X); } else if (S[I]=='+'||S[I]=='-'||S[I]=='/'||S[I]=='*') { X=V_Vershine(NS); NS=Iz_Stack(NS); Y=V_Vershine(NS); NS=Iz_Stack(NS); switch (S[I]) { case '+' : X += Y; break; case '-' : X = Y - X; break; case '*' : X *= Y; break; case '/' : X = Y / X; break;} NS=V_Stack(NS, X); } I++; } X=V_Vershine(NS); NS=Iz_Stack(NS); cout << S << " => " << X << "n";} } |
Контрольные вопросы и задания
Какую структуру данных называют стеком?
На базе каких структур может быть организован стек?
Приведите из жизни примеры организации чего-либо по принципу стека.
Используя стек, напечатайте символы данной строки в обратном порядке.
Другие работы по теме:
Расчет коэффициента дисконтирования
Динамические показатели оценки инвестиционного проекта: чистая текущая стоимость; индекс доходности; внутренняя норма окупаемости. Статистические показатели его оценки: период окупаемости, динамический и статистический срок. Рентабельность инвестиций.
Лекция по Квантовой физике
1.1.Предмет классической физики: вещество и излучение. Описание эволюции физических систем происходит с помощью “динамических переменных”. Для систем с материальной точкой динамические переменные – r→(t), p→ (t); в ДСК: x(t), y(t), z(t); px(t), py(t), pz(t). С помощью динамических переменных определяется динамическое состояние физической системы в некоторый момент времени.
Факторные теории личности
Теории стали развиваться после распространения факторного анализа как инструмента количеств, измерений и классификации признаков. В психологических исследованиях Факторные теории личности были ориентированы на эмпирические исследования.
Темперамент 12
Темпераментом называют совокупность свойств, характеризующих динамические особенности протекания психических процессов и поведения человека, их силу, скорость, возникновение, прекращение и изменение.
Расчет алгоритма управления АСУ
Кривая разгона. Динамические параметры и математическое описание кривой разгона. Алгоритм управления. Выбор переходного процесса и настройки параметров алгоритмов управления АСУ. Регулирование в программе SIMULINC. Оптимизация переходного процесса.
а по теме динамика управляемых преобразовательных устройств
Введение. Цели регулирования пу. Анализ простейшей системы позиционного регулирования, сравнительная оценка идеального релейного и линейного регуляторов по быстродействию. Непрерывное и импульсное регулирование, их оценка по энергетике
Бюро долгот
25 июня 1795 года (7 мессидора третьего года по республиканскому календарю) Конвентом (французской национальной ассамблеей) основан Институт Бюро долгот. Главной целью было решение астрономических задач: определение местного времени и долготы.
Динамические объекты
Объектные переменные вo многом подобны обычным переменным турбо паскаля, в частности, их можно размещать в динамической памяти. Турбо паскаль содержит средства, облегчающие размещение объектных переменных в куче и их удаление из нее.
История и устройство микрофонов
Изобретение инструмента для усиления слабых звуков. Современный микрофон как устройство для преобразования акустического сигнала в электрический с сохранением волновых характеристик. Жидкостный, угольный, ленточный, динамический и конденсаторный микрофоны
BMW
Заднеприводной седан среднего класса со спортивным характером. Отменная управляемость и прекрасные динамические характеристики объединяются в этом автомобиле с престижным и узнаваемым внешним видом и высокой надежностью.
Структуры в С++
Такие типы данных, как int, float, char и long, являются неотъемлемой частью C/C++ и вам не нужно писать никакого кода, чтобы сообщить компилятору о том, что означают эти слова.
Динамические структуры данных
При разработке программ во многих случаях достаточно использовать простые переменные и массивы. Память под такие объекты выделяется либо на этапе компиляции, либо на этапе выполнения программы.
Динамические структуры данных: дек
Понятие класса как собрания информации, которая включает в себя данные и функции. Создание класса "Дек". Реализация методов: добавления элемента в начало и в конец дека, удаление элемента из начала и конца дека, проверка дека на наличие в нем элементов.
Динамические структуры данных
Средства создания динамических структур данных. Формат описания ссылочного типа. Структура памяти во время выполнения программы. Линейные списки, стек, очередь. Организация списков в динамической памяти. Пример создания списка в обратном порядке.
Динамические структуры данных
Разработка алгоритмов на динамических структурах данных. Описание структуры данных "стек". Процедуры добавления и удаления элемента, очистки памяти. Код распечатки содержимого всего стека. Инструкция пользователя, код программы, контрольный пример.
Динамические структуры данных: списки
В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы.
Алгоритмические языки и программирование
Московский авиационный институт (технический университет) ------------------------ Кафедра вычислительной математики и программирования К У Р С О В А Я Р А Б О Т А
Основы программирования
Динамическое распределение памяти. Списковые структуры. Технические характеристики предлагаемого модуля для работы с односвязным списком. Листинг модуля Dinamo. Листинг программы, при написании которой был использован модуль Dinamo.
Динамические структуры данных: очереди
Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой.
Разработка программ с использованием динамической памяти
Поиск источников ориентированного графа. Использование динамических структур при работе с графами. Способы представления графов, операции над ними, описание программной реализации. Процедуры и функции языка. Функции работы с динамической памятью, графами.
Понятие и элементы массива
Массив - это коллекция переменных, которые имеют общее имя и базовый тип. Функциональные возможности, виды массивов и их характеристика. Основные требования к входным и выходным данным массива. Использование IF THEN для перехвата всех возможных ошибок.
Основні принципи модульного програмування та стеки
Ініціалізація графічного режиму. Відображення координатних осей, асимптот, надписів. Відображення графіка. Перебір точок з абсцисами від лівого до правого кінця екрана. Визначення масштабу відображення точки на екрані. Визначення ординати точки. Черги та
Создание базы данных, состоящей из одной таблицы
Проектирование структуры базы данных. Конструирование структуры будущих таблиц баз данных, основные приемы их заполнения и редактирования. Простая сортировка значений таблицы. Поиск записей по образцу. Как правильно сохранить и загрузить базу данных.
Построение структурных схем систем автоматического управления
Предмет: Теория Автоматического Управления Тема: Построение структурных схем систем автоматического управления Введение Структурной схемой системы называется графическое изображение показывающее, из каких элементов состоит система, и каким образом они соединены между собой.
Алгоритмические языки и программирование
Московский авиационный институт (технический университет) ------------------------ Кафедра вычислительной математики и программирования К У Р С О В А Я Р А Б О Т А
Динамические структуры данных 4
Динамические структуры данных. Указатели До сих пор мы имели дело с переменными, которые размещаются в памяти согласно определенным правилам, а именно, для локальных переменных, описанных в подпрограмме, память отводиться при вызове подпрограммы; при выходе из нее эта память освобождается, а сами переменные прекращают существование.
Создание базы данных состоящей из одной таблицы
Проектирование структуры базы данных. Конструирование структуры будущих таблиц баз данных основные приемы их заполнения и редактирования. Простая сортировка значений таблицы. Поиск записей по образцу. Как правильно сохранить и загрузить базу данных.