Использование динамической памяти при организации списков и их обработке. Лекция 10

1. Программирование на языке С++

Использование динамической памяти при организации
списков и их обработке
Зариковская Наталья Вячеславовна
Лекция 10

2. Линейные структуры данных

• Стек (stack)
• Очередь (queue)
• Дэк (deque; double-ended queue)
• Список (list)
2

3. Стек

Стеком (англ. stack) называется хранилище данных, в
котором можно работать только с одним элементом: тем,
который был добавлен в стек последним. Стек должен
поддерживать следующие операции:
– Push
Добавить (положить) в конец стека новый элемент
– Pop
Извлечь из стека последний элемент
– Top
Узнать значение последнего элемента (не удаляя его)
– Size
Узнать количество элементов в стеке
– Clear
Очистить стек (удалить из него все элементы)
3

4. Способы реализации линейных динамических структур

• Реализация на базе массива фиксированного
размера
• Реализация на базе динамического массива
• «Ссылочная» реализация
4

5. Реализация стека на базе массива

struct Stack {
int data[MAX_SIZE];
int size;
};
void push(Stack *stack, int value) {
stack->data[stack->size] = value;
stack->size++;
}
int size(Stack *stack) {
return stack->size;
}
void clear(Stack *stack) {
stack->size = 0;
}
int pop(Stack *stack) {
stack->size--;
return stack->data[stack->size];
}
int top(Stack *stack) {
return stack->data[stack->size – 1];
}
5

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

struct Stack {
int *data;
int size;
int max_size;
};
void push(Stack *stack, int value) {
if(stack->size == stack->max_size) {
resize(stack, stack->max_size * 2);
}
stack->data[stack->size] = value;
stack->size++;
}
int pop(Stack *stack) {
stack->size--;
return stack->data[stack->size];
}
int top(Stack *stack) {
return stack->data[stack->size – 1];
}
int size(Stack *stack) {
return stack->size;
}
void clear(Stack *stack) {
stack->size = 0;
}
void resize(Stack *stack, int new_size) {
int *new_data = new int[new_size];
for(int i = 0; i < stack->size; i++) {
new_data[i] = stack->data[i];
}
delete [] stack->data;
stack->data = new_data;
stack->max_size = new_size;
6
}

7. «Ссылочная» реализация стека

struct StackElement {
int value;
StackElement *prev;
};
struct Stack {
StackElement *top;
int size;
};
int pop(Stack *stack) {
StackElement *top = stack->top;
int ret = top->value;
stack->top = top->prev;
delete top;
stack->size--;
return ret;
}
void push(Stack *stack, int value) {
StackElement *new_top =
new StackElement();
new_top->value = value;
new_top->prev = stack->top;
stack->top = new_top;
stack->size++;
}
int size(Stack *stack) {
return stack->size;
}
int top(Stack *stack) {
return stack->top->value;
}
void clear(Stack *stack) {
StackElement *cur = stack->top;
while(cur != 0) {
cur = cur->prev;
delete cur;
}
stack->top = 0;
}
7

8. Очередь

Очередью (aнгл. queue)) называется структура данных, в
которой элементы кладутся в конец, а извлекаются из
начала. Таким образом, первым из очереди будет извлечен
тот элемент, который будет добавлен раньше других.
– Enqueue
Добавить (положить) в конец очереди новый элемент
– Dequeue
Извлечь из очереди первый элемент
– Front
Узнать значение первого элемента (не удаляя его)
– Size
Узнать количество элементов в очереди
– Clear
Очистить очередь (удалить из нее все элементы)
8

9. Очередь на массиве

Элементы очереди будем также хранить в массиве. При
этом из очереди удаляется первый элемент, и, чтобы не
сдвигать все элементы очереди, будем в отдельном поле
start_index хранить индекс элемента массива, с которого
начинается очередь. При удалении элементов, очередь
будет "ползти" дальше от начала массива. Чтобы при этом
не происходил выход за границы массива, замкнем массив в
кольцо: будем считать, что за последним элементом массива
следует первый.
9

10. Очередь на массиве

struct Queue {
int data[MAX_SIZE];
int size;
int start_index;
};
void enqueue(Queue *queue, int value) {
queue->data[(queue->start_index + queue->size) % MAX_SIZE] = value;
queue->size++;
}
int dequeue(Queue *queue) {
int ret = queue->data[queue->start_index % MAX_SIZE];
queue->size--;
queue->start_index++;
return ret;
}
10

11. Дек

Деком (англ. deque – аббревиатура от double-ended
queue, двухсторонняя очередь) называется структура
данных, в которую можно удалять и добавлять элементы как
в начало, так и в конец. Дек хранится в памяти так же, как и
очередь. Система команд дека:
–
–
–
–
–
–
–
–
push_front : Добавить (положить) в начало дека новый элемент
push_back : Добавить (положить) в конец дека новый элемент
pop_front : Извлечь из дека первый элемент
pop_back : Извлечь из дека последний элемент
front : Узнать значение первого элемента (не удаляя его)
back : Узнать значение последнего элемента (не удаляя его)
size : Узнать количество элементов в деке
clear : Очистить дек (удалить из него все элементы)
11

12. Связанный список

• Узел односвязного списка:
struct Node {
int value;
Node *next;
};
12

13. Связанный список

• Узел двусвязного списка:
struct Node {
Node *prev;
int value;
Node *next;
};
13