В чем разница между стэком и очередью?

# Стэк vs Очередь: основные различия

Это фундаментальный вопрос о структурах данных, который часто задают для проверки базовых знаний. Оба — это абстрактные структуры данных, используемые в Java и повсеместно в программировании.

Определения

Стэк (Stack)

LIFO — Last In, First Out (последний вошел, первый вышел)

Стэк тарелок в столовой:
    [     ]      ← top (берём отсюда)
    [ 5 ]
    [ 4 ]
    [ 3 ]
    [ 2 ]
    [ 1 ]
    -------      ← bottom

Операции:
- push(5) → добавляем 5 наверх
- pop() → берём 5 (последний добавленный)

Очередь (Queue)

FIFO — First In, First Out (первый вошел, первый вышел)

Очередь в магазине:
[1] [2] [3] [4] [5]
 ↑                ↑
front/head      rear/tail
(берём)          (добавляем)

Операции:
- enqueue(5) → добавляем 5 в конец
- dequeue() → берём 1 (первый добавленный)

Таблица сравнения

Java реализация

Stack в Java

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

// Основные операции:
stack.push(1);      // Добавить 1
stack.push(2);      // Добавить 2
stack.push(3);      // Добавить 3

System.out.println(stack.peek());   // 3 (смотрим, не удаляем)
System.out.println(stack.pop());    // 3 (удаляем и возвращаем)
System.out.println(stack.pop());    // 2
System.out.println(stack.pop());    // 1

// Порядок: 3, 2, 1 (обратный порядок добавления)

Queue в Java

import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();

// Основные операции:
queue.add(1);           // Добавить 1 (enqueue)
queue.add(2);           // Добавить 2
queue.add(3);           // Добавить 3

System.out.println(queue.peek());   // 1 (смотрим начало)
System.out.println(queue.poll());   // 1 (удаляем и возвращаем)
System.out.println(queue.poll());   // 2
System.out.println(queue.poll());   // 3

// Порядок: 1, 2, 3 (порядок добавления сохран)

Практические примеры

Стэк: Калькулятор обратной польской нотации (RPN)

public class RPNCalculator {
    public static double calculate(String[] tokens) {
        Stack<Double> stack = new Stack<>();
        
        for (String token : tokens) {
            if (isOperator(token)) {
                double b = stack.pop();  // Второй операнд
                double a = stack.pop();  // Первый операнд
                
                double result = switch(token) {
                    case "+" -> a + b;
                    case "-" -> a - b;
                    case "*" -> a * b;
                    case "/" -> a / b;
                    default -> 0;
                };
                
                stack.push(result);
            } else {
                stack.push(Double.parseDouble(token));
            }
        }
        
        return stack.pop();
    }
}

// Использование:
// ["3", "4", "+"] → 7
// ["10", "2", "/"] → 5
// ["15", "7", "1", "1", "-", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"] → 5

Стэк: Проверка сбалансированных скобок

public class BalancedBrackets {
    public static boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

// Примеры:
isBalanced("()[]{}");       // true
isBalanced("([{}])");       // true
isBalanced("([)]");         // false (скобки перекрывают друг друга)
isBalanced("([)");          // false

Очередь: Система обработки задач (Task Queue)

public class TaskProcessor {
    private Queue<Task> taskQueue = new LinkedList<>();
    
    public void addTask(Task task) {
        taskQueue.add(task);  // Добавляем в конец очереди
    }
    
    public void processTasks() {
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();  // Берём первую задачу
            processTask(task);
            System.out.println("Processed: " + task.getName());
        }
    }
    
    private void processTask(Task task) {
        // Обработка задачи
    }
}

// Использование:
TaskProcessor processor = new TaskProcessor();
processor.addTask(new Task("Send email"));
processor.addTask(new Task("Generate report"));
processor.addTask(new Task("Clean cache"));

processor.processTasks();
// Вывод:
// Processed: Send email
// Processed: Generate report
// Processed: Clean cache

Очередь: BFS (поиск в ширину)

public class BFS {
    public static void bfs(Graph graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.vertexCount()];
        
        queue.add(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.println("Visited: " + vertex);
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

Стэк: DFS (поиск в глубину)

public class DFS {
    public static void dfs(Graph graph, int start) {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.vertexCount()];
        
        stack.push(start);
        visited[start] = true;
        
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            System.out.println("Visited: " + vertex);
            
            for (int neighbor : graph.getNeighbors(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }
}

Операции в Java Collections

Stack

Stack<String> stack = new Stack<>();

// Добавление
stack.push("A");        // Добавляет элемент

// Удаление
stack.pop();            // Удаляет и возвращает верхний элемент
                        // Бросает EmptyStackException если пусто

// Просмотр
stack.peek();           // Возвращает верхний элемент без удаления
stack.empty();          // Проверяет пусто ли

// Поиск
stack.search("A");      // Возвращает позицию элемента (1-indexed)

Queue

Queue<String> queue = new LinkedList<>();

// Добавление
queue.add("A");         // Добавляет, бросает exception если нельзя
queue.offer("B");       // Добавляет, возвращает false если нельзя

// Удаление
queue.remove();         // Удаляет и возвращает, бросает exception если пусто
queue.poll();           // Удаляет и возвращает, возвращает null если пусто

// Просмотр
queue.element();        // Возвращает начало, бросает exception если пусто
queue.peek();           // Возвращает начало, возвращает null если пусто

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

           Stack      Queue
push/add   O(1)       O(1)
pop/poll   O(1)       O(1)
peek       O(1)       O(1)

Когда использовать

Используй Stack когда:

✅ Нужен LIFO порядок
✅ Рекурсия (call stack)
✅ Откат операций (Undo/Redo)
✅ Проверка скобок/синтаксиса
✅ DFS алгоритмы
✅ Парсинг выражений

Используй Queue когда:

✅ Нужен FIFO порядок
✅ Очередь задач
✅ Системы обработки сообщений
✅ BFS алгоритмы
✅ Планировщик задач (scheduler)
✅ Обработка по приоритетам (PriorityQueue)