Стек, очередь и дек на списках

Стек

Стек работает по принципу LIFO: последний пришёл — первый вышел. Операции:

• push — положить на вершину;
• pop — снять с вершины;
• peek — посмотреть вершину;
• is_empty — проверить пустоту.

Стек удобно реализовать на односвязном списке: вершина — это head.

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

int push(Node **top, int value)
{
    Node *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return 0;
    }

    node->value = value;
    node->next = *top;
    *top = node;
    return 1;
}

int pop(Node **top, int *out)
{
    if (*top == NULL)
    {
        return 0;
    }

    Node *node = *top;
    *out = node->value;
    *top = node->next;
    free(node);
    return 1;
}

int peek(const Node *top, int *out)
{
    if (top == NULL)
    {
        return 0;
    }

    *out = top->value;
    return 1;
}

Все операции — O(1). Память освобождается по мере pop; после работы нужно освободить остаток.

Очередь

Очередь работает по принципу FIFO: первый пришёл — первый вышел. Операции:

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

На односвязном списке удобно хранить head и tail:

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

int enqueue(Queue *q, int value)
{
    Node *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return 0;
    }

    node->value = value;
    node->next = NULL;

    if (q->tail == NULL)
    {
        q->head = q->tail = node;
    }
    else
    {
        q->tail->next = node;
        q->tail = node;
    }
    return 1;
}

int dequeue(Queue *q, int *out)
{
    if (q->head == NULL)
    {
        return 0;
    }

    Node *node = q->head;
    *out = node->value;
    q->head = node->next;
    if (q->head == NULL)
    {
        q->tail = NULL;
    }
    free(node);
    return 1;
}

enqueue и dequeue — O(1).

Дек

Дек (deque) — двусторонняя очередь: добавление и удаление с обоих концов. На двусвязном списке все четыре операции — O(1):

typedef struct DNode
{
    int value;
    struct DNode *prev;
    struct DNode *next;
} DNode;

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

• push_front — вставить перед head;
• push_back — вставить после tail;
• pop_front — удалить head;
• pop_back — удалить tail.

При каждой операции обновляйте prev, next, head и tail. Если deque пуст, после удаления оба указателя должны стать NULL.

Где это нужно

• стек — проверка вложенности, вычисление постфиксных выражений, откат действий;
• очередь — обработка заявок, обход в ширину, буферизация;
• дек — двусторонняя буферизация, скользящее окно.

Частые ошибки

Документация

• Структуры
• malloc
• free

Что запомнить

1. Стек — LIFO, вершина на head.
2. Очередь — FIFO, храним head и tail.
3. Дек — операции с обоих концов на двусвязном списке.
4. Все операции на списках — O(1).
5. Проверяйте пустоту и освобождайте память.