Void init(Vector*);

Void resize(Vector*, int);

Void push_back(Vector*, double);

Лекция 14. Алгоритмы и структуры данных (продолжение).

Вопрос №75. Структура данных «стек» (на базе вектора): основные характеристики и внутреннее устройство. Интерфейс структуры данных «стек».

Стек – это одна из простейших динамических структур данных со специфическими правилами включения и удаления элементов.

Стек работает по принципу «последним пришёл – первым ушёл» (last-in, first-out – сокращённо LIFO). Включение новых элементов в стек всегда производится в конце последовательности элементов (в вершине стека). Получить (выбрать) элемент из стека можно также только из вершины, прямого доступа к элементам стека по индексу нет.

Для размещения стека удобно использовать массив, а еще лучше – вектор, т.к. стек – это динамическая структура.

Теперь начнем разработку функций, поддерживающих абстракцию «стек».

Первая из функций – init_s должна выполнять инициализацию стека, т.е. создавать пустой стек:

Вторая функция - push_s добавляет к стеку новый элемент:

Void push_s(Stack *st, double d) {

push_back(&st->v, d); // добавляем

++st->top; // инкрементируем вершину

}

Третья функция - pop_s извлекает из стека элемент:

Теперь займемся конструированием модульной структуры приложения, использующего абстракцию «стек». По аналогии с абстракцией «вектор» сначала сформируем интерфейс, в который поместим описание структуры Stack, а также описания клиентских функций для работы со стеками: init_s, push_s и pop_s.

Как отмечалось ранее, интерфейс помещается в заголовочный файл, который назовем Stack.h :

// Stack.h

#include "Vector.h"

typedef struct Stack{

int top;

Vector v;} Stack;

void init_s(Stack*);

void push_s(Stack*, double);

int pop_s(Stack*, double*);

Вопрос №76. Структура данных «очередь» (на базе вектора): основные характеристики и внутреннее устройство. Интерфейс структуры данных «очередь».

Очередь – также одна из простейших динамических структур данных со своими правилами включения и удаления элементов.

Очередь работает по принципу «первым пришёл – первым ушёл» (first-in, first-out – сокращённо FIFO). Включение новых элементов в очередь всегда производится в конце последовательности элементов (в «хвосте» - tail). Получить (выбрать) элемент из очереди можно только из «головы» (head) очереди; прямого доступа к элементам очереди по индексу также нет.

Для размещения очереди в памяти компьютера можно использовать массив, но лучше – вектор, т.к. очередь – это также динамическая структура.

Разработаем функции, поддерживающих абстракцию «очередь».

Первая из функций – init_q должна выполнять инициализацию очереди, т.е. создавать пустую очередь:

Void init_q(Queue *q) {

q->head = q->tail = 0; init(&q->v);

}

Вторая функция - enqueue добавляет к очереди новый элемент:

Void enqueue(Queue *q, double d) {

push_back(&q->v, d); // добавляем в «хвост»

++q->tail; // инкрементируем «хвост»

}

Третья функция - dequeue извлекает из очереди элемент: