Структуры данных C++

Репозиторий с собственной реализацией стандартных структур данных C++ для лабораторных работ по предмету "Языки программирования".

Описание

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

Реализованные структуры данных

1. Stack (Стек)

Директория: stack/

Реализация стека на основе динамического массива с автоматическим изменением размера.

Основные методы:

• push(char x) - добавление элемента в стек
• pop() - удаление и возврат верхнего элемента
• top() - получение верхнего элемента без удаления
• isEmpty() - проверка на пустоту

Файлы:

• ststack.h - заголовочный файл
• ststack.cpp - реализация
• main.cpp - пример использования

---

2. Queue (Очередь)

Директория: queue/

Шаблонная реализация очереди на основе двусвязного списка (FIFO - First In First Out).

Основные методы:

• push(T data) - добавление элемента в конец очереди
• pop() - удаление элемента из начала очереди
• front() - получение первого элемента
• last() - получение последнего элемента
• getSize() - получение размера очереди
• isEmpty() - проверка на пустоту
• clear() - очистка очереди
• display() - вывод содержимого очереди

Файлы:

• queue.h - заголовочный файл
• queue.cpp - реализация
• main.cpp - пример использования

---

3. Deque (Двусторонняя очередь)

Директория: deque/

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

Основные методы:

• pushfront(T data) - добавление элемента в начало
• pushback(T data) - добавление элемента в конец
• popfront() - удаление элемента из начала
• popback() - удаление элемента из конца
• front() - получение первого элемента
• last() - получение последнего элемента
• getSize() - получение размера
• isEmpty() - проверка на пустоту
• clear() - очистка дека

Файлы:

• deque.h - заголовочный файл
• deque.cpp - реализация
• main.cpp - пример использования

---

4. List (Двусвязный список)

Директория: list/

Шаблонная реализация двусвязного списка с расширенным функционалом для работы с элементами.

Основные методы:

• pushfront(T data) - добавление элемента в начало
• pushback(T data) - добавление элемента в конец
• popfront() - удаление первого элемента
• popback() - удаление последнего элемента
• insert(int index, T data) - вставка элемента по индексу
• removeAt(int index) - удаление элемента по индексу
• getAt(int index) - получение элемента по индексу
• operator[](int index) - доступ к элементу через оператор []
• front() - получение первого элемента
• last() - получение последнего элемента
• find(T data) - поиск индекса элемента
• is_in(T data) - проверка наличия элемента
• getSize() - получение размера списка
• isEmpty() - проверка на пустоту
• clear() - очистка списка
• display() - вывод содержимого списка

Файлы:

• list.h - заголовочный файл
• list.cpp - реализация
• main.cpp - пример использования

---

Структура проекта

Structures/
├── stack/                     # Реализация стека
├── queue/                     # Реализация очереди
├── deque/                     # Реализация двусторонней очереди
├── list/                      # Реализация двусвязного списка
└── README.md                  # Этот файл

Компиляция и сборка

Каждая структура данных содержит собственный файл main.cpp для демонстрации работы. Для компиляции можно использовать любой C++ компилятор:

Пример компиляции (g++)

# Stack
g++ stack/main.cpp stack/ststack.cpp -o stack_demo

# Queue
g++ queue/main.cpp queue/queue.cpp -o queue_demo

# Deque
g++ deque/main.cpp deque/deque.cpp -o deque_demo

# List
g++ list/main.cpp list/list.cpp -o list_demo

Использование Visual Studio

Некоторые структуры данных содержат файлы проектов Visual Studio (.vcxproj), которые можно открыть напрямую в IDE.

Особенности реализации

• Шаблоны (Templates): Queue, Deque и List реализованы как шаблонные классы для поддержки различных типов данных
• Двусвязные списки: Queue, Deque и List используют внутренний класс Node для организации двусвязного списка
• Динамическое управление памятью: все структуры корректно управляют памятью с использованием конструкторов и деструкторов
• Stack: использует динамический массив с автоматическим изменением размера при переполнении