Определение стека
Стек — это структура данных, реализованная по принципу последнего пришедшего — первым обслуженного. Элементы добавляются и удаляются только из одного конца структуры, называемого вершиной стека.
Операции со стеком
— добавляет элемент x в вершину стека.
— удаляет верхний элемент стека и возвращает его значение.
— возвращает верхний элемент стека без удаления.
— проверяет, пуст ли стек.
Определение очереди
Очередь — это структура данных, реализованная по принципу первого пришедшего — первым обслуженного. Элементы добавляются в один конец очереди, а извлекаются из другого.
Операции с очередью
— добавляет элемент x в конец очереди.
— удаляет первый элемент очереди и возвращает его значение.
— возвращает первый элемент очереди без удаления.
back() — возвращает последний элемент очереди без удаления.
empty() — проверяет, пуста ли очередь.
Связный список
Связный список — это линейная структура данных, состоящая из элементов, называемых узлами. Каждый узел содержит данные и ссылку на следующий узел.
Основные операции со списком
insert(data, position) — вставляет новый узел с данными data на позицию position.
delete(position) — удаляет узел на позиции position.
search(data) — ищет узел с заданными данными и возвращает его индекс или false.
print_list() — выводит содержимое списка.
Реализация стека и очереди через массивы
Реализовать стек и очередь можно с помощью массива фиксированной длины. Однако такой подход имеет ограничения по размеру.
Реализация стека и очереди через связные списки
Использование связных списков позволяет реализовать неограниченные по размеру стеки и очереди.
Пример реализации стека на Python
```python class Stack: def __init__(self): self.items = []
def push(self, item): self.items.append(item)
def pop(self): return self.items.pop() ```
Пример реализации очереди на Python
```python class Queue: def __init__(self): self.items = []
def enqueue(self, item): self.items.append(item)
def dequeue(self): return self.items.pop(0) ```
Вопросы для самопроверки
Что такое стек?
Какие основные операции выполняются над стеком?
Как реализуется очередь?
В чем отличие между стеком и очередью?
Что такое связный список?