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

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

По определению, структура данных - способ представления данных в памяти, позволяющий эффективно выполнять с ними определённый набор операций. Например, простой массив лучше всего подходит для частого обращения к элементам по индексам и их изменению. А удаление элемента из середины массива работает за \(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++

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

stack<int> s;           //создание стека
s.push(5);              //добавление элемента
cout << s.top();        //обращение к верхнему элементу
if (!s.empty()) {       //проверка на пустоту
    s.pop();            //извлечение элемента (не возвращает значения,
                        //нужно предварительно использовать .top())
}

queue<int> q;                             //создание очереди
q.push(5);                                //добавление элемента
cout << q.front() << ' ' << q.back();     //обращение к первому и последнему элементам
if (!q.empty()) {                         //проверка на пустоту
    q.pop();                              //извлечение элемента (не возвращает значения,
                                          //нужно предварительно использовать .top())
}

С реализацией дека дела обстоят несколько иначе. Стандартный класс std::deque является не классическим деком, а скорее вектором с возможностью вставки и добавления в начало за \(O(1)\). Он поддерживает все операции, поддерживаемые классом std::vector, в том числе обращение к элементу по индексу и итераторы с произвольным доступом. Так что для работы с ним используйте те же методы, что и при работе с вектором.

Более сложные структуры данных

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