# 22. Динамические структуры данных. Односвязный список, стек и очередь. Алгоритмы их обработки.
**Динамические структуры данных** - составные структуры данных, динамически меняющие свой размер во время выполнения программы.
## Односвязный список
**Однонаправленный (односвязный) список** - динамическая структура данных, состоящая из узлов (Node). Каждый узел хранит значение и указатель на следующий узел. Последний узел хранит указатель на NULL.
```c
// Пример реализации узла
struct Node {
Book data; //поле данных
struct Node* next; //укзатель на следующий элемент
};
```
### Доступные операции:
1. Создание списка
2. Добавление элемента в список
3. Удаление узла списка
4. Удаление всего списка
5. Операции обхода списка
## Создание списка
```c
struct Node * init(int a) // а - значение первого узла
{
struct Node *list;
list = (struct Node*)malloc(sizeof(struct Node)); // выделение памяти под корень списка
list->data = a;
list->next = NULL; // это последний узел списка
return(list);
}
```
#### Добавление элемента в список:
1. Выделить память под элемент
2. Добавить в него ссылку на следующий
3. Связать предыдущий элемент с новым
```c
struct Node * addelem(struct Node *list, int number)
{
struct Node *temp, *p;
temp = (struct Node*)malloc(sizeof(Node));
p = list->ptr; // сохранение указателя на следующий узел
list->ptr = temp; // предыдущий узел указывает на создаваемый
temp->data = number; // сохранение поля данных добавляемого узла
temp->next = p; // созданный узел указывает на следующий элемент
return(temp);
}
```
**Удаление элемента из списка:**
1. Связать предыдущий и следующий
2. Очистить память от текущего
```c
struct Node * deletelem(struct Node *list, struct Node *root)
{
struct Node *temp;
temp = root;
while (temp->next != list) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий list
temp = temp->next;
}
temp->next = list->next; // переставляем указатель
free(list); // освобождаем память удаляемого узла
return(temp);
}
```
**Удаление корня списка**
```c
struct Node * deletehead(struct Node *root)
{
struct Node *temp;
temp = root->ptr;
free(root); // освобождение памяти текущего корня
return(temp); // новый корень списка
}
```
### **Стек**
**Стек** - динамическая структура данных, организованная по принципу LIFO (Last in first out).
`std::stack` - реализация стека
```c
#include "stack.h"
struct StackNode {
Book data;
StackNode* next;
};
struct Node {
Book data;
Node* next;
};
struct Stack {
StackNode* top;
Node* top;
};
Stack initStack() {
Stack stack = { NULL };
return stack;
}
bool isEmpty(Stack* stack) {
return !!stack->top;
return !stack->top;
}
void push(Stack* stack, Book book) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = book;
newNode->next = stack->top;
stack->top = newNode;
}
bool pop(Book* book, Stack* stack) {
if (isEmpty(stack))
return false;
Node* node = stack->top;
stack->top = stack->top->next;
*book = node->data;
free(node);
return true;
}
void clear(Stack* stack) {
while (stack->top) {
Node* tmp = stack->top;
stack->top = stack->top->next;
free(tmp);
}
}
bool peek(Book* book, Stack* stack) {
if (isEmpty(stack))
return false;
*book = stack->top->data;
return true;
}
```
## Очередь
**Очередь** - динамическая структура данных, организованная по принципу FIFO (First in first out).
`std::queue` - очередь
```c
#include "queue.h"
struct Queue {
Node *head, *tail;
};
Queue initQueue() {
Queue queue;
queue.head = NULL;
queue.tail = NULL;
return queue;
}
bool isEmpty(Queue* queue) {
return !!queue->head;
return !queue->head;
}
bool pop(Book* book, Queue* queue) {
if(isEmpty(queue))
return false;
Node* node = queue->head;
*book = node->data;
queue->head = node->next;
free(node);
return true;
}
void push(Queue *queue, Book book) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = book;
node->next = NULL;
if(isEmpty(queue))
queue->head = queue->tail = node;
else
queue->tail->next = node;
queue->tail = node;
}
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/22.-dinamicheskie-struktury-dannykh.-odnosvyaznyi-spisok-stek-i-ochered.-algoritmy-ikh-obrabotki..md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.