Стеки и очереди в языке C¶

Стеки и очереди — это две фундаментальные структуры данных, которые широко используются в программировании. Они отличаются принципом работы (LIFO и FIFO соответственно) и применяются в различных алгоритмах, от парсинга выражений до управления задачами в ОС.

1. Стек (Stack) — принцип LIFO (Last In, First Out)¶

Основные операции:

• push — добавление элемента на вершину стека.
• pop — удаление элемента с вершины стека.
• peek (или top) — просмотр верхнего элемента без удаления.
• isEmpty — проверка на пустоту.

Реализация стека на C (на основе массива)¶

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// Инициализация стека
void initStack(Stack *s) {
    s->top = -1;
}

// Проверка на пустоту
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// Проверка на переполнение
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// Добавление элемента (push)
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Стек переполнен!\n");
        return;
    }
    s->data[++s->top] = value;
}

// Удаление элемента (pop)
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Стек пуст!\n");
        return -1; // Ошибка
    }
    return s->data[s->top--];
}

// Просмотр верхнего элемента (peek)
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Стек пуст!\n");
        return -1;
    }
    return s->data[s->top];
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Верхний элемент: %d\n", peek(&s)); // 30
    printf("Извлеченный элемент: %d\n", pop(&s)); // 30
    printf("Теперь верхний элемент: %d\n", peek(&s)); // 20

    return 0;
}

Применение стеков:¶

• Парсинг математических выражений (например, обратная польская запись).
• Отмена действий (Ctrl+Z в редакторах).
• Рекурсивные вызовы функций (стек вызовов).

2. Очередь (Queue) — принцип FIFO (First In, First Out)¶

Основные операции:

• enqueue — добавление элемента в конец очереди.
• dequeue — удаление элемента из начала очереди.
• front — просмотр первого элемента без удаления.
• isEmpty — проверка на пустоту.

Реализация очереди на C (на основе массива)¶

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} Queue;

// Инициализация очереди
void initQueue(Queue *q) {
    q->front = q->rear = -1;
}

// Проверка на пустоту
bool isEmpty(Queue *q) {
    return q->front == -1;
}

// Проверка на переполнение
bool isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// Добавление элемента (enqueue)
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Очередь переполнена!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE;
    }
    q->data[q->rear] = value;
}

// Удаление элемента (dequeue)
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Очередь пуста!\n");
        return -1;
    }
    int value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1; // Очередь опустела
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return value;
}

// Просмотр первого элемента (front)
int front(Queue *q) {
    if (isEmpty(q)) {
        printf("Очередь пуста!\n");
        return -1;
    }
    return q->data[q->front];
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Первый элемент: %d\n", front(&q)); // 10
    printf("Извлеченный элемент: %d\n", dequeue(&q)); // 10
    printf("Теперь первый элемент: %d\n", front(&q)); // 20

    return 0;
}

Применение очередей:¶

• Обработка задач в порядке поступления (например, печать документов).
• Алгоритмы поиска в ширину (BFS).
• Буферизация данных (например, в сетевых пакетах).

Сравнение стека и очереди¶

Вывод¶

• Стек используется, когда важен порядок LIFO (например, история браузера).
• Очередь применяется, когда важен порядок FIFO (например, очередь печати).