Задачи модуля "Очередь и дек": от двух стеков до транспонирования

Один стек инвертирует порядок элементов. Что произойдет с порядком после двух переливаний?

Заведем стеки stack_in (вход) и stack_out (выход):

1. Enqueue: всегда Push в stack_in - O(1).
2. Dequeue: самый старый элемент лежит на дне stack_in. Если stack_out пуст, переливаем в него все элементы из stack_in - они переворачиваются, и старейший оказывается на вершине. Затем Pop из stack_out. Если stack_out не пуст - сразу Pop из него.

Каждый элемент проходит не больше двух переливаний за всю жизнь, поэтому амортизированная сложность Dequeue - O(1). Эта задача хорошо показывает, что структуры данных выражаются друг через друга.

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

void Push(Node** top, int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data; n->next = *top; *top = n;
}

int Pop(Node** top) {
    if (*top == NULL) return -1;
    Node* t = *top; int data = t->data;
    *top = t->next; free(t);
    return data;
}

bool IsEmpty(Node* top) { return top == NULL; }

/* Очередь из двух стеков */
typedef struct {
    Node* stack_in;
    Node* stack_out;
} PseudoQueue;

void InitQueue(PseudoQueue* q) {
    q->stack_in = NULL;
    q->stack_out = NULL;
}

void Enqueue(PseudoQueue* q, int data) {
    Push(&(q->stack_in), data); /* всегда во входной стек */
}

int Dequeue(PseudoQueue* q) {
    /* Выходной пуст - переливаем в него входной целиком */
    if (IsEmpty(q->stack_out)) {
        if (IsEmpty(q->stack_in)) {
            printf("Очередь пуста!\n");
            return -1;
        }
        while (!IsEmpty(q->stack_in)) {
            Push(&(q->stack_out), Pop(&(q->stack_in)));
        }
    }
    /* На вершине stack_out - самый старый элемент */
    return Pop(&(q->stack_out));
}

int main(void) {
    PseudoQueue q;
    InitQueue(&q);

    Enqueue(&q, 10); Enqueue(&q, 20); Enqueue(&q, 30);
    printf("%d\n", Dequeue(&q)); /* 10 */
    Enqueue(&q, 40);
    printf("%d\n", Dequeue(&q)); /* 20 */
    printf("%d\n", Dequeue(&q)); /* 30 */
    printf("%d\n", Dequeue(&q)); /* 40 */
    return 0;
}

Очередь можно "прокрутить": извлечь элемент из головы и тут же вернуть в хвост. Как за одну прокрутку найти минимум?

Сортировка выбором на двух очередях:

1. Прокручиваем исходную очередь целиком (Dequeue + Enqueue обратно), запоминая минимальное значение.
2. Прокручиваем второй раз: найденный минимум отправляем в отсортированную очередь, остальные элементы возвращаем в исходную. Если минимум встречается несколько раз, изымаем только одно вхождение.
3. Повторяем, пока исходная очередь не опустеет, затем перекладываем отсортированную очередь обратно.

Сложность O(N²) - по две прокрутки на каждый из N элементов. Сравните с сортировкой стека из прошлой темы: прием тот же, меняется только доступный набор операций.

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* head;
    Node* tail;
    int size;
} Queue;

void InitQueue(Queue* q) { q->head = q->tail = NULL; q->size = 0; }
int IsEmpty(Queue* q) { return q->size == 0; }

void Enqueue(Queue* q, int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data; n->next = NULL;
    if (q->tail) q->tail->next = n;
    q->tail = n;
    if (!q->head) q->head = n;
    q->size++;
}

int Dequeue(Queue* q) {
    if (IsEmpty(q)) return -1;
    Node* t = q->head; int data = t->data;
    q->head = q->head->next;
    if (!q->head) q->tail = NULL;
    q->size--; free(t);
    return data;
}

void SortQueue(Queue* orig) {
    Queue sorted;
    InitQueue(&sorted);
    int total = orig->size;

    for (int i = 0; i < total; i++) {
        /* Прокрутка 1: ищем минимум */
        int min = INT_MAX;
        int n = orig->size;
        for (int j = 0; j < n; j++) {
            int val = Dequeue(orig);
            if (val < min) min = val;
            Enqueue(orig, val);
        }

        /* Прокрутка 2: изымаем одно вхождение минимума */
        int extracted = 0;
        for (int j = 0; j < n; j++) {
            int val = Dequeue(orig);
            if (val == min && !extracted) {
                Enqueue(&sorted, val);
                extracted = 1;
            } else {
                Enqueue(orig, val);
            }
        }
    }

    while (!IsEmpty(&sorted)) {
        Enqueue(orig, Dequeue(&sorted));
    }
}

void PrintQueue(Queue* q) {
    for (Node* c = q->head; c; c = c->next) printf("%d ", c->data);
    printf("\n");
}

int main(void) {
    Queue q;
    InitQueue(&q);
    Enqueue(&q, 45); Enqueue(&q, 12); Enqueue(&q, 89);
    Enqueue(&q, 12); Enqueue(&q, 3);  Enqueue(&q, 77);

    printf("До сортировки:    "); PrintQueue(&q);
    SortQueue(&q);
    printf("После сортировки: "); PrintQueue(&q);
    return 0;
}

Палиндром требует сравнивать первый символ с последним, второй - с предпоследним. Какая структура выдает элементы с обоих концов?

Дек создан для этой задачи:

1. Проходим строку: буквы переводим в нижний регистр и добавляем в дек (PushBack), остальные символы пропускаем.
2. Пока в деке больше одного элемента, снимаем по букве с обоих концов: PopFront и PopBack.
3. Пара не совпала - не палиндром. Дек опустел (или остался один центральный символ при нечетной длине) - палиндром.

Сложность O(N): каждый символ попадает в дек и покидает его не больше одного раза.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct Node {
    char data;
    struct Node *next, *prev;
} Node;

typedef struct Deque {
    Node *head, *tail;
    int size;
} Deque;

void InitDeque(Deque* d) { d->head = d->tail = NULL; d->size = 0; }

void PushBack(Deque* d, char c) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = c; n->next = NULL; n->prev = d->tail;
    if (d->tail) d->tail->next = n;
    d->tail = n;
    if (!d->head) d->head = n;
    d->size++;
}

char PopFront(Deque* d) {
    if (!d->head) return '\0';
    Node* t = d->head; char c = t->data;
    d->head = d->head->next;
    if (d->head) d->head->prev = NULL;
    else d->tail = NULL;
    d->size--; free(t);
    return c;
}

char PopBack(Deque* d) {
    if (!d->tail) return '\0';
    Node* t = d->tail; char c = t->data;
    d->tail = d->tail->prev;
    if (d->tail) d->tail->next = NULL;
    else d->head = NULL;
    d->size--; free(t);
    return c;
}

bool IsPalindrome(const char* str) {
    Deque d;
    InitDeque(&d);

    /* 1. Только буквы, в нижнем регистре */
    for (int i = 0; i < strlen(str); i++) {
        if (isalpha((unsigned char)str[i])) {
            PushBack(&d, tolower((unsigned char)str[i]));
        }
    }

    /* 2. Сравниваем концы */
    while (d.size > 1) {
        if (PopFront(&d) != PopBack(&d)) {
            while (d.size > 0) PopFront(&d); /* чистим память */
            return false;
        }
    }
    return true;
}

int main(void) {
    printf("%s\n", IsPalindrome("Radar") ? "палиндром" : "не палиндром");
    printf("%s\n", IsPalindrome("Hello World") ? "палиндром" : "не палиндром");
    printf("%s\n", IsPalindrome("A man a plan a canal Panama")
        ? "палиндром" : "не палиндром");
    return 0;
}

У каждого узла два указателя: next и prev. Что произойдет с направлением обхода, если в каждом узле поменять их местами?

1. Проходим по всем узлам от головы к хвосту.
2. В каждом узле меняем местами next и prev.
3. В конце меняем местами указатели head и tail самого дека.

Тонкий момент: после обмена указателей внутри узла "следующий" узел цепочки лежит уже в поле prev - именно по нему нужно шагать дальше. Сложность O(N), дополнительной памяти нет.

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

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct Deque {
    Node* head;
    Node* tail;
} Deque;

void ReverseDeque(Deque* d) {
    if (d == NULL || d->head == NULL) return;

    Node* current = d->head;
    Node* temp = NULL;

    while (current != NULL) {
        /* Меняем местами next и prev текущего узла */
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;

        /* Следующий узел теперь лежит в prev! */
        current = current->prev;
    }

    /* Меняем местами head и tail самого дека */
    temp = (Node*)d->head;
    d->head = d->tail;
    d->tail = temp;
}

void PushBack(Deque* d, int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data; n->next = NULL; n->prev = d->tail;
    if (d->tail) d->tail->next = n;
    d->tail = n;
    if (!d->head) d->head = n;
}

void PrintDeque(Deque* d) {
    for (Node* c = d->head; c; c = c->next) printf("%d ", c->data);
    printf("\n");
}

int main(void) {
    Deque d = {NULL, NULL};
    PushBack(&d, 10); PushBack(&d, 20);
    PushBack(&d, 30); PushBack(&d, 40);

    printf("Исходный дек:      "); PrintDeque(&d);
    ReverseDeque(&d);
    printf("Дек после реверса: "); PrintDeque(&d);
    return 0;
}

После удаления головы у нового первого узла остается указатель prev на освобожденную память. Что с ним делать? И что происходит с tail, когда удален последний элемент?

PopFront:

1. Запоминаем текущий head.
2. Сдвигаем голову: head = head->next.
3. Если новый head существует - обнуляем его prev. Если нет - дек опустел, обнуляем и tail.
4. Освобождаем память старого узла.

PopBack - зеркально: сдвигаем tail на tail->prev, обнуляем next нового хвоста, при опустевшем деке обнуляем head.

Главный источник ошибок - забытая ветка "удален последний элемент": если не обнулить второй указатель дека, он останется висеть на освобожденной памяти.

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

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct Deque {
    Node* head;
    Node* tail;
} Deque;

int PopFront(Deque* d) {
    if (d->head == NULL) {
        printf("Дек пуст!\n");
        return -1;
    }

    Node* t = d->head;
    int data = t->data;

    d->head = d->head->next;
    if (d->head != NULL) {
        d->head->prev = NULL; /* новая голова не имеет соседа слева */
    } else {
        d->tail = NULL;       /* удален последний элемент */
    }

    free(t);
    return data;
}

int PopBack(Deque* d) {
    if (d->tail == NULL) {
        printf("Дек пуст!\n");
        return -1;
    }

    Node* t = d->tail;
    int data = t->data;

    d->tail = d->tail->prev;
    if (d->tail != NULL) {
        d->tail->next = NULL; /* новый хвост не имеет соседа справа */
    } else {
        d->head = NULL;       /* удален последний элемент */
    }

    free(t);
    return data;
}

void PushBack(Deque* d, int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data; n->next = NULL; n->prev = d->tail;
    if (d->tail) d->tail->next = n;
    d->tail = n;
    if (!d->head) d->head = n;
}

int main(void) {
    Deque d = {NULL, NULL};
    PushBack(&d, 10); PushBack(&d, 20); PushBack(&d, 30);

    printf("PopFront: %d\n", PopFront(&d)); /* 10 */
    printf("PopBack:  %d\n", PopBack(&d));  /* 30 */
    printf("PopFront: %d\n", PopFront(&d)); /* 20, дек опустел */
    PopFront(&d);                            /* сообщение: дек пуст */
    return 0;
}

Строка результата - это столбец исходной матрицы. Элементы столбца приходят при построчном чтении по одному, сверху вниз. Какая структура накопит их в правильном порядке?

Заводим по очереди на каждый столбец исходной матрицы:

1. Читаем матрицу построчно; элемент из столбца j отправляем в j-ю очередь (Enqueue).
2. После чтения очередь № j содержит весь j-й столбец в порядке сверху вниз - а это ровно j-я строка транспонированной матрицы.
3. Выводим очереди одну за другой - получаем результат.

FIFO здесь принципиален: очередь сохраняет порядок элементов столбца. Стек на ее месте выдал бы столбцы задом наперед.

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* head;
    Node* tail;
} Queue;

void InitQueue(Queue* q) { q->head = q->tail = NULL; }

void Enqueue(Queue* q, int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = data; n->next = NULL;
    if (q->tail) q->tail->next = n;
    q->tail = n;
    if (!q->head) q->head = n;
}

int Dequeue(Queue* q) {
    if (!q->head) return 0;
    Node* t = q->head; int data = t->data;
    q->head = q->head->next;
    if (!q->head) q->tail = NULL;
    free(t);
    return data;
}

int main(void) {
    int rows = 2, cols = 3;
    int input[2][3] = { {1, 2, 3}, {4, 5, 6} };

    /* Очередь на каждый столбец исходной матрицы */
    Queue* queues = (Queue*)malloc(cols * sizeof(Queue));
    for (int j = 0; j < cols; j++) InitQueue(&queues[j]);

    /* Построчное чтение: элемент столбца j - в очередь j */
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            Enqueue(&queues[j], input[i][j]);
        }
    }

    printf("Транспонированная матрица:\n");
    for (int j = 0; j < cols; j++) {
        for (int i = 0; i < rows; i++) {
            printf("%d ", Dequeue(&queues[j]));
        }
        printf("\n");
    }

    free(queues);
    return 0;
}