---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Структура узла списка
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Стек (реализован на связном списке)
typedef struct {
    Node* top;
} Stack;

// Очередь (реализована на связном списке)
typedef struct {
    Node* front;
    Node* rear;
} Queue;

// === 1. ФУНКЦИИ ДЛЯ РАБОТЫ СО СТЕКОМ ===

void initStack(Stack* stack) {
    stack->top = NULL;
}

void push(Stack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Ошибка выделения памяти!\n");
        return;
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

void fillStackAscending(Stack* stack, int n) {
    initStack(stack);
    for (int i = n; i >= 1; i--) {
        push(stack, i);
    }
}

void fillStackDescending(Stack* stack, int n) {
    initStack(stack);
    for (int i = 1; i <= n; i++) {
        push(stack, i);
    }
}

void fillStackRandom(Stack* stack, int n, int min, int max) {
    initStack(stack);
    for (int i = 0; i < n; i++) {
        int randomValue = min + rand() % (max - min + 1);
        push(stack, randomValue);
    }
}

// === 2. ФУНКЦИИ ДЛЯ РАБОТЫ С ОЧЕРЕДЬЮ ===

void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

void enqueue(Queue* queue, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Ошибка выделения памяти!\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;

    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

void fillQueueAscending(Queue* queue, int n) {
    initQueue(queue);
    for (int i = 1; i <= n; i++) {
        enqueue(queue, i);
    }
}

void fillQueueDescending(Queue* queue, int n) {
    initQueue(queue);
    for (int i = n; i >= 1; i--) {
        enqueue(queue, i);
    }
}

void fillQueueRandom(Queue* queue, int n, int min, int max) {
    initQueue(queue);
    for (int i = 0; i < n; i++) {
        int randomValue = min + rand() % (max - min + 1);
        enqueue(queue, randomValue);
    }
}

// === 3. ФУНКЦИИ ДЛЯ РАБОТЫ СО СПИСКОМ ===

void printList(Node* head) {
    printf("Список: ");
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int calculateChecksum(Node* head) {
    int sum = 0;
    Node* current = head;
    while (current != NULL) {
        sum += current->data;
        current = current->next;
    }
    return sum;
}

// Исправленная функция подсчета количества серий
// Серия - это максимальная последовательность, в которой элементы не убывают (возрастают или равны)
int countSeries(Node* head) {
    if (head == NULL) return 0;
    if (head->next == NULL) return 1;
    
    int seriesCount = 1; // Начинаем с первой серии
    Node* current = head;
    
    while (current->next != NULL) {
        // Если следующий элемент МЕНЬШЕ текущего, то начинается новая серия
        if (current->next->data < current->data) {
            seriesCount++;
        }
        current = current->next;
    }
    return seriesCount;
}

void deleteAllNodes(Node** head) {
    Node* current = *head;
    Node* next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

void printStack(Stack* stack) {
    printf("Стек (вершина -> дно): ");
    Node* current = stack->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void printQueue(Queue* queue) {
    printf("Очередь (начало -> конец): ");
    Node* current = queue->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current =current->next;
    }
    printf("\n");
}

int main() {
    srand(time(NULL));
    
    // 1. РАБОТА СО СТЕКОМ
    printf("==================== 1. РАБОТА СО СТЕКОМ ====================\n\n");
    
    Stack stack;
    
    printf("1.1 Стек из 10 возрастающих чисел (1-10):\n");
    fillStackAscending(&stack, 10);
    printStack(&stack);
    printf("Контрольная сумма: %d\n", calculateChecksum(stack.top));
    printf("Количество серий: %d\n\n", countSeries(stack.top));
    deleteAllNodes(&stack.top);

    printf("1.2 Стек из 10 убывающих чисел (10-1):\n");
    fillStackDescending(&stack, 10);
    printStack(&stack);
    printf("Контрольная сумма: %d\n", calculateChecksum(stack.top));
    printf("Количество серий: %d\n\n", countSeries(stack.top));
    deleteAllNodes(&stack.top);

    printf("1.3 Стек из 10 случайных чисел (1-100):\n");
    fillStackRandom(&stack, 10, 1, 100);
    printStack(&stack);
    printf("Контрольная сумма: %d\n", calculateChecksum(stack.top));
    printf("Количество серий: %d\n\n", countSeries(stack.top));
    deleteAllNodes(&stack.top);

    // 2. РАБОТА С ОЧЕРЕДЬЮ
    printf("==================== 2. РАБОТА С ОЧЕРЕДЬЮ ====================\n\n");
    
    Queue queue;
    
    printf("2.1 Очередь из 10 возрастающих чисел (1-10):\n");
    fillQueueAscending(&queue, 10);
    printQueue(&queue);
    printf("Контрольная сумма: %d\n", calculateChecksum(queue.front));
    printf("Количество серий: %d\n\n", countSeries(queue.front));
    deleteAllNodes(&queue.front);

    printf("2.2 Очередь из 10 убывающих чисел (10-1):\n");
    fillQueueDescending(&queue, 10);
    printQueue(&queue);
    printf("Контрольная сумма: %d\n", calculateChecksum(queue.front));
    printf("Количество серий: %d\n\n", countSeries(queue.front));
    deleteAllNodes(&queue.front);

    printf("2.3 Очередь из 10 случайных чисел (1-100):\n");
    fillQueueRandom(&queue, 10, 1, 100);
    printQueue(&queue);
    printf("Контрольная сумма: %d\n", calculateChecksum(queue.front));
    printf("Количество серий: %d\n\n", countSeries(queue.front));
    deleteAllNodes(&queue.front);

    // 3. РАБОТА СО СПИСКОМ
    printf("==================== 3. РАБОТА СО СПИСКОМ ====================\n\n");
    
    Node* list = NULL;
    
    printf("3.1 Список из 10 возрастающих чисел (1-10):\n");
    Node* nodes1[10];
    for (int i = 0; i < 10; i++) {
        nodes1[i] = (Node*)malloc(sizeof(Node));
        nodes1[i]->data = i + 1;
        if (i > 0) {
            nodes1[i-1]->next = nodes1[i];
        }
    }
    nodes1[9]->next = NULL;
    list = nodes1[0];
    printList(list);
    printf("Контрольная сумма: %d\n", calculateChecksum(list));
    printf("Количество серий: %d (одна непрерывная возрастающая последовательность)\n\n", countSeries(list));
    deleteAllNodes(&list);
    
    printf("3.2 Список из 10 убывающих чисел (10-1):\n");
    Node* nodes2[10];
    for (int i = 0; i < 10; i++) {
        nodes2[i] = (Node*)malloc(sizeof(Node));
        nodes2[i]->data = 10 - i;
        if (i > 0) {
            nodes2[i-1]->next = nodes2[i];
        }
    }
    nodes2[9]->next = NULL;
    list = nodes2[0];
    printList(list);
    printf("Контрольная сумма: %d\n", calculateChecksum(list));
    printf("Количество серий: %d (каждый элемент меньше предыдущего - 10 серий)\n\n", countSeries(list));
    deleteAllNodes(&list);
    
    printf("3.3 Список из 10 случайных чисел (1-100):\n");
    Node* nodes3[10];
    for (int i = 0; i < 10; i++) {
        nodes3[i] = (Node*)malloc(sizeof(Node));
        nodes3[i]->data = 1 + rand() % 100;
        if (i > 0) {
            nodes3[i-1]->next = nodes3[i];
        }
    }
    nodes3[9]->next = NULL;
    list = nodes3[0];
    printList(list);
    printf("Контрольная сумма: %d\n", calculateChecksum(list));
    printf("Количество серий: %d\n\n", countSeries(list));
    deleteAllNodes(&list);
    
    printf("3.4 Список из 10 чисел с повторениями (1,1,2,2,3,3,4,4,5,5):\n");
    Node* nodes4[10];
    for (int i = 0;


i < 10; i++) {
        nodes4[i] = (Node*)malloc(sizeof(Node));
        nodes4[i]->data = (i / 2) + 1;
        if (i > 0) {
            nodes4[i-1]->next = nodes4[i];
        }
    }
    nodes4[9]->next = NULL;
    list = nodes4[0];
    printList(list);
    printf("Контрольная сумма: %d\n", calculateChecksum(list));
    printf("Количество серий: %d (5 серий по 2 одинаковых элемента)\n\n", countSeries(list));
    deleteAllNodes(&list);
    
    printf("3.5 Дополнительный тест: список (1,2,3,2,1,2,3,4,3,2):\n");
    Node* nodes5[10];
    int testData[] = {1, 2, 3, 2, 1, 2, 3, 4, 3, 2};
    for (int i = 0; i < 10; i++) {
        nodes5[i] = (Node*)malloc(sizeof(Node));
        nodes5[i]->data = testData[i];
        if (i > 0) {
            nodes5[i-1]->next = nodes5[i];
        }
    }
    nodes5[9]->next = NULL;
    list = nodes5[0];
    printList(list);
    printf("Контрольная сумма: %d\n", calculateChecksum(list));
    printf("Количество серий: %d\n\n", countSeries(list));
    deleteAllNodes(&list);

    return 0;
}