Стеки деки очереди деревья

Простейшие структуры данных: стек, очередь, дек

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

По определению, структура данных — способ представления данных в памяти, позволяющий эффективно выполнять с ними определённый набор операций. Например, простой массив лучше всего подходит для частого обращения к элементам по индексам и их изменению. А удаление элемента из середины массива работает за \(O(N)\). Если вам для решения задачи нужно часто удалять элементы, то придётся воспользоваться другой структурой данной. Например, бинарное дерево ( std::set ) позволяет делать это за \(O(\log N)\), но не поддерживает работу с индексами, только поочерёдный обход всех элементов и поиск по значению (тоже за \(O(\log N)\)).

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

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

Стек

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

• Добавить элемент в стек (Сложность: \(O(1)\))
• Извлечь элемент из стека (Сложность: \(O(1)\))
• Проверить, пуст ли стек (Сложность: \(O(1)\))

Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем. Представьте, что на дне вашего стакана лежат несколько кусков печенья. Вы можете положить наверх ещё один кусок или достать уже находящийся наверху. Остальные куски закрыты верхним, и вы про них ничего не знаете. Для описания стека часто используется аббревиатура LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.

Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
 
struct stack  int a[1000]; int head = -1; //Индекс крайнего элемента. void push(int x)  head++; a[head] = x; > int pop()  if (head != -1)  head--; return a[head + 1]; > else  //Ошибка, попытка извлечь элемент из пустого стека. > > bool is_empty()  return head == -1; > >; 
 
Как видите, для реализации стека хватает одного массива и одного указателя, обозначающего крайний элемент.
 
Очередь
 
Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.
 
Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 
struct queue  int a[1000]; //Для более лаконичной реализации работы, мы будем //хранить указатель не на последний элемент, а //на следующий за ним (несуществующий). //Это, в частности, позволит нам проверять очередь на пустоту //простым условием head == tail int head = 0; //Индекс первого элемента. int tail = 0; //Индекс элемента, следующего за последним. void push(int x)  a[tail] = x; tail++; > int pop()  if (head != tail)  head++; return a[head - 1]; > else  //Ошибка, попытка извлечь элемент из пустой очереди. > > bool is_empty()  return head == tail; > >; 
 
При такой реализации очередь будет постепенно “ползти” вправо по выделенной области памяти (массиву), и достаточно быстро выйдет за её границы. Впрочем, эта реализация иллюстративная, на практике вы просто будете использовать уже готовую реализацию очереди из стандартной библиотеки (об этом ниже). В ней этот дефект отсутствует из-за более сложной работы с памятью.
 
Дек
 
Структура, объединяющая стек и очередь, называется дек (англ. deque - сокращение от double-ended queue, очередь с двумя концами). Как можно догадаться, она поддерживает уже знакомый набор операций:
 
 
Добавить элемент в начало дека (Сложность: \(O(1)\))
 
Извлечь элемент из начала дека (Сложность: \(O(1)\))
 
Добавить элемент в конец дека (Сложность: \(O(1)\))
 
Извлечь элемент из конца дека (Сложность: \(O(1)\))
 
Проверить, пуст ли дек (Сложность: \(O(1)\))
 
 
В принципе мы можем реализовать её таким же способом, как и две предыдущих, но как и в случае с очередью, эта реализация будет далека от оптимальной.
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
 
struct deque  int a[2000]; //Используя такие начальные значения индексов, у нас //будет свободная память как слева, так и справа. int head = 1000; //Индекс первого элемента. int tail = 1000; //Индекс элемента, следующего за последним. void push_front(int x)  head--; a[head] = x; > void push_back(int x)  a[tail] = x; tail++; > int pop_front()  if (head != tail)  head++; return a[head - 1]; > else  //Ошибка, попытка извлечь элемент из пустого дека. > > int pop_back()  if (head != tail)  tail--; return a[tail]; > else  //Ошибка, попытка извлечь элемент из пустого дека. > > bool is_empty()  return head == tail; > >; 
 
Стек, очередь и дек в стандартной библиотеке C++
 
Все три структуры данных являются базовыми и относительно часто встречаются в програмировании, поэтому они уже реализованы в стандартной библиотеке в виде трёх шаблонных классов. Пример работы со стеком и очередью:
 
stackint> s; //создание стека s.push(5); //добавление элемента cout  <s.top(); //обращение к верхнему элементу if (!s.empty())  //проверка на пустоту s.pop(); //извлечение элемента (не возвращает значения, //нужно предварительно использовать .top()) > queueint> q; //создание очереди q.push(5); //добавление элемента cout  <q.front()  <' '  <q.back(); //обращение к первому и последнему элементам if (!q.empty())  //проверка на пустоту q.pop(); //извлечение элемента (не возвращает значения, //нужно предварительно использовать .top()) > 
 
С реализацией дека дела обстоят несколько иначе. Стандартный класс std::deque является не классическим деком, а скорее вектором с возможностью вставки и добавления в начало за \(O(1)\). Он поддерживает все операции, поддерживаемые классом std::vector , в том числе обращение к элементу по индексу и итераторы с произвольным доступом. Так что для работы с ним используйте те же методы, что и при работе с вектором.
 
Более сложные структуры данных
 
Приведённый выше материал мог вызвать у вас лёгкое недоумение и сомнения в целесообразности всех этих ограничений на обычные массивы. На самом деле, стек, очередь и дек являются лишь простейшими примерами структур данных, не предоставляющими выгоды в скорости выполнения операций. Серьёзным структурам данных посвящены отдельные темы. Стек, очередь и дек призваны проиллюстрировать, что главными характеристиками структуры данных являются набор поддерживаемых операций и скорость их выполнения.
 
brestprog
 
Олимпиадное программирование в Бресте и Беларуси
 
Источник
 
Презентация, доклад Динамические структуры данных. Стек, очередь, дек, деревья
 
Вы можете изучить и скачать доклад-презентацию на тему Динамические структуры данных. Стек, очередь, дек, деревья. Презентация на заданную тему содержит 49 слайдов. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций в закладки!
 
Источник