Стек и Очередь: две фундаментальные структуры — Блог
$ cat learn/01-stack-queue.md

Стек и Очередь: две фундаментальные структуры

Алгоритмы Stack Queue Структуры данных

Стек и Очередь: две фундаментальные структуры данных

История

В 1946 году Алан Тьюринг предложил концепцию стека как способа управления вызовами подпрограмм. Идея была проста: последняя добавленная задача должна выполняться первой. Это следует принципу LIFO (Last In, First Out).

Очередь появилась чуть позже в работах Клода Шеннона и его коллег по теории информации. Очередь следует принципу FIFO (First In, First Out).

Реальные примеры из жизни

Стек в реальной жизни

Представьте стопку тарелок на кухне:

  • Когда моете посуду, вы кладете чистые тарелки сверху
  • Когда нужна тарелка — вы берете сверху
  • Вы не можете взять тарелку из середины, не убрав верхние

Это и есть стек. Каждая новая тарелка “кладется” на вершину стека.

Очередь в реальной жизни

Очередь в магазине:

  • Первый человек, занявший очередь, первым и обслуживается
  • Каждый новый человек встает в конец очереди
  • Это очередь — FIFO

Где используется

Стек:

  • Отмена действий (Ctrl+Z)
  • История браузера (кнопка “назад”)
  • Вызов функций в программе
  • Парсинг выражений (калькуляторы)

Очередь:

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

Как это работает

Стек (Stack)

Представьте такую аналогию:

    [Тарелка 5] <- TOP (вершина)
    [Тарелка 4]
    [Тарелка 3]
    [Тарелка 2]
    [Тарелка 1] <- BOTTOM (дно)

Добавили тарелку 6:      Взяли тарелку:
    [Тарелка 6]              [Тарелка 4]
    [Тарелка 5]              [Тарелка 3]
    [Тарелка 4]              [Тарелка 2]
    [Тарелка 3]              [Тарелка 1]
    [Тарелка 2]
    [Тарелка 1]

Очередь (Queue)

Аналогия с очередью в магазине:

    [Человек 1] → обслужен   [Человек 2] →
    [Человек 2]              [Человек 3]
    [Человек 3]              [Человек 4]
    [Человек 4]              [Человек 5]
    [Человек 5]
       ↑
   FRONT (начало)          REAR (конец)

Код

Реализация Стека на массиве

// stack_array.h
#define STACK_TYPE int
#define MAX_SIZE 100

// Структура стека
typedef struct {
    STACK_TYPE data[MAX_SIZE];
    int top; // индекс верхнего элемента
} Stack;

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

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

// Проверка на полноту
int is_full(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

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

// Извлечение элемента (pop)
STACK_TYPE pop(Stack *s) {
    if (is_empty(s)) {
        printf("Стек пуст!\n");
        return -1;
    }
    return s->data[s->top--];
}

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

Реализация Очереди на массиве

// queue_array.h
#define QUEUE_TYPE int
#define MAX_SIZE 100

typedef struct {
    QUEUE_TYPE data[MAX_SIZE];
    int front; // индекс первого элемента
    int rear;  // индекс за последним элементом
} Queue;

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

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

// Проверка на полноту
int is_full(Queue *q) {
    return q->rear == MAX_SIZE;
}

// Добавление элемента (enqueue)
void insert(Queue *q, QUEUE_TYPE value) {
    if (is_full(q)) {
        printf("Очередь переполнена!\n");
        return;
    }
    q->data[q->rear++] = value;
}

// Извлечение элемента (dequeue)
QUEUE_TYPE delete(Queue *q) {
    if (is_empty(q)) {
        printf("Очередь пуста!\n");
        return -1;
    }
    return q->data[q->front++];
}

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

Пример использования

Стек: проверка сбалансированности скобок

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

int is_balanced(const char *str) {
    Stack s;
    create_stack(&s);
    
    for (int i = 0; i < strlen(str); i++) {
        char c = str[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&s, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (is_empty(&s)) return 0;
            char top = pop(&s);
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return 0;
            }
        }
    }
    return is_empty(&s);
}

int main() {
    printf("({}) -> %s\n", is_balanced("({})") ? "сбалансировано" : "не сбалансировано");
    printf("(] -> %s\n", is_balanced("(]") ? "сбалансировано" : "не сбалансировано");
    printf("((())) -> %s\n", is_balanced("((()))") ? "сбалансировано" : "не сбалансировано");
    return 0;
}

Результат:

({}) -> сбалансировано
(] -> не сбалансирован��
((())) -> сбалансировано

Очередь: симуляция очереди в магазине

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

typedef struct {
    char name[50];
    int items;
} Person;

int main() {
    Queue q;
    create_queue(&q);
    
    // Добавляем людей в очередь
    insert(&q, (Person){"Анна", 3});
    insert(&q, (Person){"Борис", 1});
    insert(&q, (Person){"Вика", 5});
    
    // Обслуживаем по очереди
    while (!is_empty(&q)) {
        Person p = delete(&q);
        printf("Обслужен: %s (товаров: %d)\n", p.name, p.items);
    }
    
    return 0;
}

Результат:

Обслужен: Анна (товаров: 3)
Обслужен: Борис (товаров: 1)
Обслужен: Вика (товаров: 5)

Сложность операций

ОперацияStackQueue
Push/InsertO(1)O(1)
Pop/DeleteO(1)O(1)
Top/FirstO(1)O(1)
ПоискO(n)O(n)

Ключевые выводы

  1. Стек (LIFO) — последний пришел, первый ушел. Используется для отмены действий, истории, рекурсии.

  2. Очередь (FIFO) — первый пришел, первый ушел. Используется для обработки задач в порядке поступления.

  3. Обе структуры поддерживают основные операции за O(1) — это делает их очень эффективными.

  4. Понимание стека и очереди — фундамент для изучения более сложных структур и алгоритмов.

Что дальше?

В следующем посте мы перейдем к деревьям — более сложной, но мощной структуре данных, которая позволяет организовывать данные иерархически.

← Все статьи