Описание структуры данных программы

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

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

1. Понятие структуры данных
2. Классификация структур данных
3. Основные типы структур данных
4. Массив
5. Динамический массив
6. Связанный список

Пройди тест и узнай, какая сфера тебе подходит:
айти, дизайн или маркетинг.
Бесплатно от Geekbrains

Понятие структуры данных

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

В рамках программирования структуры данных представляют собой специальные контейнеры. Они хранят информацию в определённом формате, который придает структуре те или иные свойства. Именно эти качества отличают одну структуру данных от другой. Кроме того, они определяют ее пригодность для тех или иных сценариев применения.

6 важных структур данных

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

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

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

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

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

Классификация структур данных

Различают физические и логические структуры. Физические отражают способ представления данных в памяти ЭВМ. Из-за этого их иногда называют внутренними.

Типы структур данных по составу:

• Простые. Они не делятся на составные части, которые больше, чем биты. Для простого типа четко определен размер и способ размещения структуры в памяти устройства.
• Сложные (интегрированные). Они включают в себя другие структуры, которые, в свою очередь, могут быть простыми или сложными.

Для вас подарок! В свободном доступе до 09.07 —>
Скачайте ТОП-10
бесплатных нейросетей
для программирования
Помогут писать код быстрее на 25%
Чтобы получить подарок, заполните информацию в открывшемся окне

Типы структур данных по наличию связи:

• несвязные структуры: массивы, векторы, строки, стеки (Last In, First Out), очереди (First In, First Out);
• связные структуры (например, связные списки).

Нельзя не упомянуть про так называемую изменчивость. Речь идёт об изменении числа элементов или связей между ними. В зависимости от уровня изменчивости выделяют:

Вам нужно знать только 3 структуры данных

• статические;
• полустатические;
• динамические.

В зависимости от признака упорядоченности элементов различают два типа структур организации данных:

• Нелинейные: деревья, графы, многосвязные списки.
• Линейные. В зависимости от типа распределения компонентов в памяти устройства они могут иметь последовательное распределение (строки, векторы, массивы, стеки, очереди) и произвольное связное распределение (односвязные и двусвязные списки).

При указании типа данных определяются следующие параметры:

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

Теперь поговорим о самых важных структурах данных, с помощью которых вы сможете решать те или иные задачи.

Основные типы структур данных

Массив

Массив – это очень распространенная структура, отличающаяся своей простотой. Каждому элементу в массиве соответствует положительное целое число — индекс. Оно указывает на расположение элемента. Практически во всех языках программирования индексы начинаются с нуля (данный подход называют нумерацией на основе нуля).

Выделяют две разновидности массивов:

• Одномерные — простейшие линейные структуры.
• Многомерные — вложенные структуры, которые состоят из других массивов.

Как используются? За счёт своей простоты эти составные элементы более сложных структур (стеков, очередей и т.п.) применяются для хранения несложных связанных данных. Они также нужны для различных алгоритмов сортировки (сортировка вставок, сортировка пузырьком и т.д.).

Динамический массив

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

Узнай, какие ИТ — профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Александр Сагун
Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ ресурсов об IT-сфере

Только лучшие телеграм-каналы, каналы Youtube, подкасты, форумы и многое другое для того, чтобы узнавать новое про IT

ТОП 50+ сервисов и приложений от Geekbrains

Безопасные и надежные программы для работы в наши дни

Получить подборку бесплатно
Уже скачали 21542

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

Вы можете добавить сколько угодно элементов в динамический массив. Место размещения также выбирается произвольно. Но учтите, что если вставить их в середину, то остальные элементы нужно будет передвинуть. Это, как правило, занимает немало времени. Исходя из этого, рекомендуется добавлять элементы в конец такого массива.

Как используются? Динамические массивы играют роль блоков для структур данных. Их применяют в целях хранения неопределённого количества элементов.

Связанный список

Описание данного типа структуры данных будет следующим. Связанный список представляет собой набор элементов (узлов) в линейной последовательной структуре. Узел — это простой объект, имеющий 2 свойства: переменные для хранения данных и адреса памяти следующего узла в списке. Узел хранит информацию о типе данных, которые он содержит, а также о своем соседе. Благодаря этому можно создавать связанные списки, где все узлы будут связаны между собой.

Различают несколько разновидностей списков:

• Односвязный. Обходить элементы можно лишь в прямом направлении.
• Двусвязный. Кроме прямого, допускается ещё и обратное направление. Узлы включают дополнительный указатель(prev), который указывает на предыдущий узел.
• Круговые связанные. Так называют связанные списки, в которых предыдущий (prev) указатель «головы» указывает на «хвост», а следующий указатель «хвоста» указывает на «голову».

Как используются? Связанные списки играют роль строительных блоков сложных структур данных (очередей, стеков и некоторых разновидностей графиков). В динамических структурах они нужны для выделения памяти, а в ОС — для упрощения переключения вкладок. Кроме того, их используют в слайд-шоу изображений, так как картинки идут поочередно.

Стек

Стек представляет собой линейную структуру данных, которая формируется на базе массивов или связанных списков. Стек работает по принципу LIFO (от Last-In-First-Out — «первым на вход — последним на выход»). Проще говоря, первым элементом, который покинет стек, станет тот, который последний в него войдёт. Название «stack» переводится как «стопка». Дело в том, что данная структура может быть визуализирована как стопка книг, лежащих на столе.

Очередь

Очередь относится к линейному типу структуры данных так же, как и стек. Формируется она на основе массивов или связанных списков. Работает по принципу FIFO (First-In-First-Out — «первым на вход — первым на выход»). Иначе говоря, первым покинувшим очередь элементом будет тот, который первый в неё вошёл.

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

Множество

Во множестве данные не упорядочены и хранятся группой. При этом их нельзя структурировать, а иногда даже сортировать. Однако их можно использовать как обычные математические множества, например, объединять, искать пересечения, вычислять разность и смотреть, является ли одно множество подмножеством другого.

Как правило, в таких структурах размещаются объекты, которые имеют те или иные общие признаки. При этом порядок объектов может быть любым.

Как используются? Множества применяют для поддержания большого количества уникальных объектов. Их также используют для хранения данных, которые не требуется сортировать. Помимо этого, множества нужны для сравнения, объединения наборов данных и выполнения других прочих операций.

Карта (Map)

Внутри карт данные хранятся в паре «ключ/значение». Поэтому такие структуры называют ассоциативными массивами или словарями. При этом каждый ключ уникален, в отличие от значений, которые могут использоваться по несколько раз. Если вы знаете ключ, то поиск данных будет выполняться быстрее, нежели в других типах структур.

Как используются? Карты применяются для создания баз, в которых будут храниться уникальные соответствия между двумя множествами значений. Они размещаются в ключе. При этом структура контролирует отсутствие повторений этих ключей.

Рассмотрим яркий пример такой структуры данных — hash-map (хэш-таблица). В ней размещаются ключи и значения, а для их реализации добавляются индексы. С помощью хэш-функции можно вычислить индекс, зная ключ. Это позволяет отыскивать необходимые данные. Если в хэш-таблицу вставляют ту или иную информацию, то добавляют ключ и данные.

После этого функция хэширует ключ, переводит его в число и записывает данные в ячейку, которая соответствует этому числу. Если требуется запросить данные, то следует ещё раз ввести ключ, чтобы хэш-функция выполнила поиск.

Только до 6.07
Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней
Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы зарегистрироваться на бесплатный интенсив и получить в подарок подборку файлов от GeekBrains, заполните информацию в открывшемся окне

Двоичное дерево поиска

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

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

Как используются? Деревья применяются для быстрого поиска данных и их хранения в отсортированном виде. При этом их можно быстро добавлять и удалять.

Префиксное дерево (бор, нагруженное дерево)

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

Как используются? Префиксные деревья применяются в целях хранения данных, которые нужно выдавать по цепочке. К примеру, слова для функции автозаполнения на мобильном устройстве: пользователь вбивает одну букву, и дерево предлагает следующие. Кроме того, префиксные деревья используются для хранения данных, у которых есть повторяющиеся участки (к примеру, IP-адресов).

Граф (Graph)

Граф представляет собой структуру данных, состоящую из нескольких узлов (вершин), связанных между собой. Пару (x,y) называют ребром. Таким образом, вершина x соединена с вершиной y. Ребро может определять вес/стоимость (стоимость прохождения по пути между двумя вершинами).

Графы представляют собой более общие случаи деревьев, которые, в свою очередь, нередко называют ациклическими графами. Можно выделить две особенности, которые отличают одну структуру от другой:

• В графе могут быть циклы (когда «ребенок» является «родителем» для того же объекта).
• Ребра могут нести смысловую нагрузку (необходимо сохранять их значения).

Различают два вида граф: ориентированные и неориентированные. В первом случае у рёбер между узлами есть направление. Поэтому для ориентированных граф имеет значение порядок элементов. У неориентированных разновидностей нет направлений. Следовательно, их можно читать и обходить как угодно.

Популярные статьи

Стоит отметить, что графы нередко представляют как матрицы смежности. При этом каждая строка или столбец – узел. Если в ячейке появилось значение «1», то между узлами есть связь, а если «0», то связь отсутствует. Учтите, что если у связей (рёбер графа) есть вес, то его можно разместить в ячейке.

Как используются? Графы полезны для хранения данных, которые связаны между собой сложными соотношениями. Кроме того, эти структуру используются для формирования маршрутов из точки А в точку Б, а также для выполнения анализа соотносящейся между собой информации.

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

Структуризацию данных в программировании можно выполнять самыми разными методами. Если вы будете знать, как устроены структуры, то сможете улучшить ПО. Кроме того, процесс написания кода станет проходить гораздо быстрее. Еще на стадии формирования спецификаций и требований следует обращать внимание на особенности поставленных задач. Это позволит правильно выбрать формат данных.

Источник: gb.ru

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

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

Рассмотрим подробнее структуру классов «дерево решений» SolutionTree и «узел дерева решений» TreeNode.

Класс TreeNode содержит три поля: информационное поле узла question, в котором содержатся вопросы или ответы, ссылку на левого и правого потомка узла yes и no. Кроме того, здесь имеется три соответствующих полям свойства:Yes, No, Question. Для удобства доступа к объектам данного класса используется три конструктора: без параметров, с одним параметроминформационным полем и с тремя параметрамиинформационным полем и ссылками на левую и правую дочь узла.

Класс SolutionTree содержит три поля: ссылки на корень дерева решений, на текущий узел и на предыдущий узел, расположенный уровнем выше. В классе содержатся свойство Root, конструктор по умолчанию. Кроме того, здесь описаны методы для записи и чтения информации в XML-файл:Save и Open соответственно, а также методы рисования структуры дерева решений P, R и L.

В данной программе для хранения дерева решений используется XML-файл, поскольку эта структура наглядно отражает иерархическую структуру данных и реализует принцип вложенности, что удобно для извлечения информации, размещенной в узлах дерева. В отличие от бинарных форматов, XML содержит метаданные об именах, типах и классах описываемых объектов, по которым приложение может обработать документ неизвестной структуры. Иерархическая структура XML подходит для описания практически любых типов документов, кроме аудио и видео мультимедийных потоков, растровых изображений, сетевых структур данных и двоичных данных. Для того чтобы в файле не дублировались значения полей и свойств, используется объект класса XmlIgnoreAttribute, который инструктирует метод Serialize, принадлежащий XmlSerializer, не сериализовывать значение открытого поля или открытого свойства чтения/записи. Для создания корневого элемента иерархии вызывается конструктор класса XmlRootAttribute с двумя параметрами – именем корневого элемента и проинициализованным значением false свойством IsNullable, указывающим, что XmlSerializer не должен выполнять сериализацию члена со значением Nothing в атрибут xsi:nil.

Структура дерева решений изображена на рис.1.

Источник: studfile.net

Maxim-Doronin/mp2-lab3-lists-stack

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Switch branches/tags
Branches Tags
Could not load branches
Nothing to show
Could not load tags

Nothing to show

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Cancel Create

• Local
• Codespaces

HTTPS GitHub CLI
Use Git or checkout with SVN using the web URL.
Work fast with our official CLI. Learn more about the CLI.

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

Latest commit message
Commit time

README.md

Реализация стека на линейном односвязном списке

Содержание:

• Постановка задачи
• Руководство пользователя
• Руководство программиста

• Используемые инструменты
• Общая структура проекта
• Описание структуры программы
• Описание структур данных

• Структура данных «список»
• Структура данных «стек»

• Алгоритм перевода в постфиксную запись
• Алгоритм подсчета выражения в постфиксной записи

Цель данной лабораторной работы — разработать на языке программирования С++ статическую библиотеку, реализующую динамическую структуру данных — стек, основанный на динамической структуре — список.

Написать тестирующую программу для каждой структуры данных с помощью Google C++ Testing Framework.

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

Написать консольные приложения для демонстрации работы списков и стеков.

Запуск приложения и ввод данных

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

Чтобы запустить программу, необходимо открыть исполняемый файл sample_postfix.exe и далее следовать инструкциям программы.

1. Введите арифметическое выражение и нажмите клавишу «Ввод»
2. Введите значение каждой из символьных переменных, нажимая клавишу «Ввод» после каждого введенного значения.
3. Получите преобразованное выражение и численный результат.

Для завершения работы нажмите любую клавишу.

В ходе лабораторной работы использовались следующие инструменты:

• Система контроля версий Git.
• Фреймворк для написания автоматических тестов Google Test.
• Среда разработки Microsoft Visual Studio (2010 или старше).

Общая структура проекта

• gtest — библиотека Google Test.
• img — директория с изображениями, используемых в отчете к лабораторной работе.
• include — директория для размещения заголовочных файлов.
• samples — директория для размещения тестового приложения.
• sln — директория с файлами решений и проектов для Visual Studio 2010
• src — директория для размещения исходных кодов (cpp-файлы).
• test — директория с модульными тестами и основным тестовым приложением, инициализирующим запуск тестов.
• README.md — отчет о выполненной лабораторной работе.
• Служебные файлы

• .gitignore — перечень расширений файлов, игнорируемых Git при добавлении файлов в репозиторий.

Описание структуры программы

Программа состоит из 7 проектов:

• stack — статическая библиотека, которая содержит объявление и реализацию шаблонных классов NODE , List и Stack

• NODE — описывает сущность «узел» списка. «Узел» хранит в себе значение «ключа» и указатель на следующий узел, то есть на объект такого же класса.
• List — класс «список», агрегирующий в себе класс NODE .
• Stack — класс «стек», агрегирующий в себе класс List .

• postfix_notation — метод непосредственного перевода выражения в постфиксную запись, учитывающая корректность данных. Входные и выходные данные — строковый тип.
• postfix_calculation — метод вычисления результата, считывающая аргументы арифметического выражения из потока данных. Входные данные — строковый тип (выражение в постфиксной форме), выходные — вещественное число. Так же учитывает корректность введенных данных, и соответствие количества операндов и операций.

Описание структур данных

Структура данных «список»

Односвязный линейный список — динамическая структура данных, состоящая из однотипных «узлов», каждый из которых содержит данные определенного типа и указатель на последующий узел списка. Указатель последнего элемента списка равен нулю, что является признаком конца списка. Указателем на список является указатель на его первый элемент (pFirst).

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

В данной лабораторной работе структура данных «список» представлена в виде класса List , который содержит в себе следующие методы:

• Конструктор по умолчанию.
• Конструктор копирования списков.
• Деструктор.
• print — метод печати элементов списка.
• search — метод поиска элемента с заданным ключом, возвращающая указатель на элемент
• searchPrev — скрытый метод поиска элемента, предшествующего элементу с заданным ключом.
• erase — перегруженный метод удаления элемента с заданным ключом или по указателю на элемент.
• insertFirst — метод создания элемента с заданным ключом и вставки его в начало списка.
• insertLast — метод создания элемента с заданным ключом и вставки его в конец списка.
• insertBefore — метод вставки элемента, на который передан указатель, до элемента с заданным ключом.
• insertAfter — метод вставки элемента, на который передан указатель, после элемента с заданным ключом.
• getFirst — метод, возвращающий указатель на первый элемент списка.

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

Класс List реализован с использованием шаблонов для покрытия его использования с различными типами данных.

Структура данных «стек»

Стек — динамическая структура данных, представляющая собой список элементов, организованных по принципу FILO (англ. first in — last out, «последним пришёл — первым вышел»).

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

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

В данной лабораторной работе структура данных «стек» представлена в виде класса Stack , который агрегирует в себя объект класса List и содержит следующие методы:

• Конструктор по умолчанию, который явно вызывает конструктор класса List .
• Конструктор копирования.
• Деструктор.
• isEmpty — метод проверки стека на пустоту
• isFull — метод проверки стека на полноту. По факту, проверяется наличие доступной памяти в виртуальном адресном пространстве программы для создания нового узла списка.
• push — метод добавления элемента с заданным значением на вершину стека.
• pop — метод изъятия элемента с вершины стека. Метод возвращает значение элемента.
• look — метод просмотра элемента на вершине стека.

Методы, реализованные в классе Stack необходимы и достаточны для полноценного использования этой структуры данных. Пример использования этой структуры данных содержится в приложении sample_stack.exe .

Класс Stack реализован с использованием шаблонов для покрытия его использования с различными типами данных.

Алгоритм перевода в постфиксную запись

Описание алгоритма перевода из инфиксной записи в постфиксную:

1. Каждой операции ставится приоритет
2. Операциям умножения * и деления / наивысший приоритет, равный 3.
3. Операциям сложения + и вычитания — приоритет 2
4. Операции открывающей скобки ( приоритет 1.
5. Операции равенства = приоритет 0.
6. Создается 2 стека: стек для хранения текущей постфиксной формы trackStack и стек для хранения операций opStack .
7. Выражение просматривается слева-направо, при этом возможно 4 случая:

1. Встретился операнд. Тогда он добавляется в стек trackStack .
2. Встретилась операция, приоритет которой выше, чем приоритет операции, лежащей на вершине стека opStack , или стек opStack пуст. В этом случае операция добавляется в стек для хранения операций opStack .
3. Встретилась операция, приоритет которой равен или ниже приоритета операции, лежащей на вершине стека opStack . В этом случае все операции, приоритет которых больше данной перекладываются в стек trackStack до тех пор, пока на вершине стека opStack не появится операции с меньшим приоритетом или opStack не станет пустым. Новая же операция добавляется в стек хранения операций.
4. Встретилась операция закрывающей скобки. В этом случае из стека opStack перекладываются все операции в trackStack до первого вхождения операции открывающей скобки. Операция открывающей скобки удаляется из стека операций.

Алгоритм подсчета выражения в постфиксной записи

Описание алгоритма вычисления арифметического выражения в постфиксной форме:

1. Создается один стек с вещественным типом данных trackStack .
2. Выражение просматривается слева-направо, при этом возможно 2 случая:

1. Встретился операнд. В этом случае от пользователя запрашивается его значение (в случае, если ранее значение для данного символьного операнда не запрашивалось) и добавляется на вершину стека trackStack .
2. Встретилась операция. Тогда из стека trackStack изымаются 2 операнда, над ними совершается операция, результат операции снова добавляется в стек.

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

В процессе было написано 46 тестов, которые покрывают всевозможные ситуации использования методов класса. Все тесты успешно пройдены.

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

• Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы = Data Structures and Algorithms. — М.: Вильямс, 2000. — 384 с.
• Майкл Мейн, Уолтер Савитч. Структуры данных и другие объекты в C++ = Data Structures and Other Objects Using C++. — 2-е изд. — М.: Вильямс, 2002. — 832 с.

Источник: github.com