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

Если ты всерьёз изучаешь алгоритмы — начни с основ.

Стек (stack) и очередь (queue) — две простые, но очень мощные структуры.

Они лежат в основе всего: от рекурсии до BFS, парсинга выражений и undo-функций.


🧱 Что такое стек (stack)?​


📌 Принцип: LIFO — Last In, First Out (последний пришёл — первый ушёл)

Представь стопку тарелок: ты кладёшь сверху — и снимаешь сверху.

  • push(x) — положить элемент
  • pop() — снять последний
  • top() — посмотреть на верхний

✅ Пример на Python:
Python: 
stack = []
stack.append(10)
stack.append(20)
print(stack.pop())  # 20
print(stack[-1])    # 10 (top)

✅ Пример на C:
C: 
#define MAX 100
int stack[MAX], top = -1;

void push(int x) { if (top < MAX - 1) stack[++top] = x; }
int pop()        { return (top >= 0) ? stack[top--] : -1; }
int peek()       { return (top >= 0) ? stack[top] : -1; }

---

🛤 А очередь (queue)?​


📌 Принцип: FIFO — First In, First Out (первый пришёл — первый ушёл)

Как живая очередь: кто первый стал, тот и обслужен первым.

  • enqueue(x) — поставить в конец
  • dequeue() — взять с начала

✅ Пример на Python:
Python: 
from collections import deque

q = deque()
q.append(1)       # enqueue
q.append(2)
print(q.popleft())  # 1
print(q[0])         # 2 (front)

✅ Пример на C:
C: 
#define MAX 100
int queue[MAX], front = 0, rear = 0;

void enqueue(int x) {
    if (rear < MAX) queue[rear++] = x;
}

int dequeue() {
    return (front < rear) ? queue[front++] : -1;
}

---

🔁 Где используются стек и очередь​

  • 📜 Парсеры выражений, интерпретаторы → стек
  • 📌 Undo/Redo в редакторах → стек
  • 🔍 Поиск в ширину (BFS) → очередь
  • 🔂 Менеджеры задач, буферы событий → очередь
  • 📦 Поддержка рекурсии → стек вызовов
---

📊 Сравнение​


ОперацияStackQueue
Добавить элементpush(x)enqueue(x)
Удалить элементpop()dequeue()
ПорядокLIFOFIFO
Типичная реализацияМассив / списокКольцевой буфер / deque

---

📎 Вывод​


Стек и очередь — это как гаечный ключ и отвёртка в наборе алгоритмиста.
Без них не пишется ни один парсер, ни одна поиск-алгоритм, ни одна работающая архитектура.

💬 А ты помнишь, когда впервые написал свой стек? Или очередь? Делись историями 👇