Задачи модуля "Стек": от скобок до пересечения

Какая скобка должна закрыться первой - та, что открылась раньше, или та, что позже? Какой порядок это напоминает?

Последней открытая скобка закрывается первой - это чистый LIFO, значит, нужен стек:

1. Читаем строку посимвольно.
2. Открывающая скобка - кладем в стек.
3. Закрывающая: если стек пуст - ошибка (лишняя закрывающая). Иначе снимаем вершину и проверяем, что типы совпали (достали ( - обязан прийти )).
4. Когда строка кончилась, стек должен быть пуст - иначе остались незакрытые скобки.

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

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

/* Стек символов на массиве */
#define MAX_LEN 1000
char stack[MAX_LEN];
int top = -1;

void Push(char c) { stack[++top] = c; }
char Pop(void) { return stack[top--]; }
bool IsEmpty(void) { return top == -1; }

bool IsMatchingPair(char open, char close) {
    if (open == '(' && close == ')') return true;
    if (open == '{' && close == '}') return true;
    if (open == '[' && close == ']') return true;
    return false;
}

bool CheckBalancedBrackets(const char* expr) {
    top = -1; /* сбрасываем стек */

    for (int i = 0; i < strlen(expr); i++) {
        if (expr[i] == '{' || expr[i] == '(' || expr[i] == '[') {
            Push(expr[i]);
        }
        else if (expr[i] == '}' || expr[i] == ')' || expr[i] == ']') {
            if (IsEmpty()) return false;       /* лишняя закрывающая */
            if (!IsMatchingPair(Pop(), expr[i])) return false;
        }
    }

    return IsEmpty(); /* остались незакрытые? */
}

int main(void) {
    printf("%s\n", CheckBalancedBrackets("{[()]}") ? "Правильно" : "ОШИБКА");
    printf("%s\n", CheckBalancedBrackets("{[(])}") ? "Правильно" : "ОШИБКА");
    return 0;
}

Представьте, что вы раскладываете карты в отсортированную стопку. Что делать, если очередная карта меньше верхней карты стопки?

Идея - сортировка вставками, где отсортированная часть живет во временном стеке:

1. Снимаем верхний элемент исходного стека в переменную temp.
2. Пока временный стек не пуст и его вершина больше temp - перекладываем элементы из временного стека обратно в исходный: освобождаем место.
3. Кладем temp во временный стек - теперь он на своем месте.
4. Повторяем, пока исходный стек не опустеет, и в конце переливаем все обратно.

Худший случай - O(N²) перекладываний, зато никаких нарушений интерфейса стека.

#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;
}

int Peek(Node* top) { return top ? top->data : -1; }
bool IsEmpty(Node* top) { return top == NULL; }

void SortStack(Node** origStack) {
    Node* tmpStack = NULL;

    while (!IsEmpty(*origStack)) {
        int temp = Pop(origStack);

        /* Вершина временного стека больше temp?
           Возвращаем ее в исходный - освобождаем место */
        while (!IsEmpty(tmpStack) && Peek(tmpStack) > temp) {
            Push(origStack, Pop(&tmpStack));
        }

        Push(&tmpStack, temp);
    }

    /* Переливаем отсортированное обратно */
    while (!IsEmpty(tmpStack)) {
        Push(origStack, Pop(&tmpStack));
    }
}

void PrintStack(Node* top) {
    while (top) { printf("%d ", top->data); top = top->next; }
    printf("\n");
}

int main(void) {
    Node* s = NULL;
    Push(&s, 34); Push(&s, 3); Push(&s, 31);
    Push(&s, 98); Push(&s, 92); Push(&s, 23);

    printf("Исходный стек:        "); PrintStack(s);
    SortStack(&s);
    printf("Отсортированный стек: "); PrintStack(s);
    return 0;
}

Стек на массиве - это блок ячеек плюс счетчик. Чем файл прямого доступа с fseek отличается от массива? Где хранить счетчик?

Файл прямого доступа - тот же массив, только на диске: fseek заменяет индексацию. Раскладка файла: первые 4 байта - количество элементов top, дальше подряд сами элементы.

1. Push: читаем top из начала файла, прыгаем на позицию sizeof(int) + top * sizeof(int), пишем туда значение, увеличиваем top и перезаписываем его в начале файла.
2. Pop: читаем top, уменьшаем на 1, прыгаем к последнему элементу, читаем его и перезаписываем уменьшенный счетчик.

Это буквально стек на массиве, где массив лежит на диске: та же двойная роль счетчика - и глубина, и указатель на свободную ячейку.

#include <stdio.h>

const char* filename = "stack_storage.bin";

/* Создает файл-стек и пишет количество элементов = 0 */
void InitStack(void) {
    FILE* f = fopen(filename, "wb");
    if (f) {
        int initial_top = 0;
        fwrite(&initial_top, sizeof(int), 1, f);
        fclose(f);
    }
}

void Push(int value) {
    FILE* f = fopen(filename, "r+b");
    if (!f) { InitStack(); f = fopen(filename, "r+b"); }

    int top;
    fseek(f, 0, SEEK_SET);              /* 1. читаем счетчик */
    fread(&top, sizeof(int), 1, f);

    fseek(f, sizeof(int) + top * sizeof(int), SEEK_SET);
    fwrite(&value, sizeof(int), 1, f);  /* 2. пишем значение */

    top++;                              /* 3. обновляем счетчик */
    fseek(f, 0, SEEK_SET);
    fwrite(&top, sizeof(int), 1, f);

    fclose(f);
}

int Pop(void) {
    FILE* f = fopen(filename, "r+b");
    if (!f) return -1;

    int top;
    fseek(f, 0, SEEK_SET);
    fread(&top, sizeof(int), 1, f);

    if (top == 0) { fclose(f); return -1; } /* стек пуст */

    top--;
    int value;
    fseek(f, sizeof(int) + top * sizeof(int), SEEK_SET);
    fread(&value, sizeof(int), 1, f);

    fseek(f, 0, SEEK_SET);
    fwrite(&top, sizeof(int), 1, f);

    fclose(f);
    return value;
}

int main(void) {
    InitStack();
    Push(10); Push(20); Push(30);
    printf("Извлечено: %d\n", Pop()); /* 30 */
    printf("Извлечено: %d\n", Pop()); /* 20 */
    Push(40);
    printf("Извлечено: %d\n", Pop()); /* 40 */
    printf("Извлечено: %d\n", Pop()); /* 10 */
    return 0;
}

Если перелить S1 прямо в S2, элементы лягут в обратном порядке. Сколько переворотов нужно, чтобы порядок восстановился?

Каждое переливание инвертирует порядок, а два переливания восстанавливают его:

1. Переливаем весь S1 во временный стек T - элементы легли вверх ногами (вершина S1 стала дном T).
2. Переливаем T поверх S2 - элементы перевернулись снова и легли в правильном порядке.

Результат - в S2, S1 опустел. Сложность O(N) по длине S1. Существует и другой способ: если известно, что стек - связный список, можно привязать next нижнего узла S1 к вершине S2. Это быстрее, но нарушает инкапсуляцию, поэтому в решении используются только операции стека.

#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; }

/* Положить все элементы S1 поверх S2.
   После вызова S1 пуст, результат - в S2 */
void ConcatStacks(Node** s1, Node** s2) {
    Node* tempStack = NULL;

    /* 1. S1 → temp: элементы легли вверх ногами */
    while (!IsEmpty(*s1)) {
        Push(&tempStack, Pop(s1));
    }

    /* 2. temp → S2: перевернулись обратно, порядок верный */
    while (!IsEmpty(tempStack)) {
        Push(s2, Pop(&tempStack));
    }
}

void PrintStack(Node* top) {
    while (top) { printf("%d ", top->data); top = top->next; }
    printf("\n");
}

int main(void) {
    Node* S1 = NULL; /* вершина: 1 2 3 */
    Push(&S1, 3); Push(&S1, 2); Push(&S1, 1);

    Node* S2 = NULL; /* вершина: 4 5 6 */
    Push(&S2, 6); Push(&S2, 5); Push(&S2, 4);

    ConcatStacks(&S1, &S2);

    printf("Объединенный стек: "); /* 1 2 3 4 5 6 */
    PrintStack(S2);
    return 0;
}

Чтобы "просмотреть" стек, его придется разобрать. Куда складывать разобранное, чтобы потом собрать все как было?

Понадобятся два временных стека - по одному на каждый исходный:

1. Снимаем очередной элемент val с S1 и сразу сохраняем его в temp1 (для последующего восстановления S1).
2. Ищем val в S2: переливаем S2 в temp2 поэлементно; если очередной элемент совпал - нашли пересечение, печатаем и прекращаем поиск.
3. Возвращаем все из temp2 обратно в S2 - его исходное состояние восстановлено для следующей проверки.
4. Когда S1 опустел, восстанавливаем его из temp1.

Сложность O(N × M): для каждого элемента S1 просматриваем S2 целиком. Дорого, но по-другому с чистым интерфейсом стека и не получится - в этом и суть задачи.

#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; }

/* Печатает пересечение, не разрушая исходные стеки */
void PrintIntersection(Node** S1, Node** S2) {
    Node* temp1 = NULL;
    Node* temp2 = NULL;

    printf("Пересечение стеков: ");

    while (!IsEmpty(*S1)) {
        int current_val = Pop(S1);
        Push(&temp1, current_val); /* чтобы восстановить S1 */

        bool found = false;

        /* Ищем current_val в S2 */
        while (!IsEmpty(*S2)) {
            int check_val = Pop(S2);
            Push(&temp2, check_val); /* чтобы восстановить S2 */
            if (check_val == current_val) {
                found = true;
                break;
            }
        }

        if (found) printf("%d ", current_val);

        /* Возвращаем элементы обратно в S2 */
        while (!IsEmpty(temp2)) {
            Push(S2, Pop(&temp2));
        }
    }
    printf("\n");

    /* Восстанавливаем S1 */
    while (!IsEmpty(temp1)) {
        Push(S1, Pop(&temp1));
    }
}

int main(void) {
    Node* S1 = NULL;
    Push(&S1, 10); Push(&S1, 20); Push(&S1, 30); Push(&S1, 40);

    Node* S2 = NULL;
    Push(&S2, 50); Push(&S2, 20); Push(&S2, 60); Push(&S2, 10);

    PrintIntersection(&S1, &S2); /* ожидается: 20 10 */
    return 0;
}