Чем стек отличается от очереди и где они применяются?

Стек поддерживает push (положить наверх), pop (снять верхний) и peek (посмотреть верхний). Где используется:

• стек вызовов — при вызове функции её локальные переменные и адрес возврата кладутся на стек, при выходе снимаются. Слишком глубокая рекурсия переполняет его;
• отмена действий (undo), история браузера «назад»;
• проверка парности скобок, разбор выражений;
• обход графа в глубину (DFS) без рекурсии.

Очередь поддерживает enqueue (в конец) и dequeue (из начала):

• обработка задач в порядке поступления, очереди сообщений;
• буферы ввода-вывода;
• обход графа в ширину (BFS).

Реализация: стек — на динамическом массиве (операции с концом). Очередь на массиве с удалением из начала даёт O(n) на операцию — поэтому используют кольцевой буфер или связный список, а на практике — дек (deque в Python, ArrayDeque в Java), который добавляет и удаляет с обоих концов за O(1).

Классическая задача — очередь на двух стеках: кладём во входной стек, забираем из выходного; когда выходной пуст, перекладываем туда всё из входного. Каждый элемент перекладывается один раз, поэтому операции амортизированно O(1).

def balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

balanced("{[()]}")   # True
balanced("([)]")     # False