Очереди и стеки в Go: Полное руководство для собеседования

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

---

1. Очереди (FIFO)

Очередь (Queue) — структура данных, работающая по принципу FIFO (First In, First Out). Это значит, что первый добавленный элемент выходит из очереди первым. Представьте очередь людей в магазине: кто первым пришёл, тот и обслуживается первым.

---

Основные операции очереди

1. Enqueue (Добавление): Добавляет элемент в конец очереди.
2. Dequeue (Удаление): Удаляет элемент из начала очереди.
3. Peek (Просмотр): Возвращает элемент из начала очереди без его удаления.
4. IsEmpty (Проверка на пустоту): Проверяет, пуста ли очередь.

---

Типы очередей

1. Простая очередь: FIFO без дополнительных возможностей.
2. Двусторонняя очередь (Deque): Элементы можно добавлять и удалять как с начала, так и с конца.
3. Приоритетная очередь: Удаляется элемент с наивысшим приоритетом, а не первый добавленный.
4. Кольцевая очередь: Конец очереди соединён с её началом, что оптимизирует использование памяти.

---

Реализация очереди на Go

Простая очередь:

goCopy codepackage main

import "fmt"

type Queue struct {
    items []int
}

func (q *Queue) Enqueue(item int) {
    q.items = append(q.items, item)
}

func (q *Queue) Dequeue() (int, bool) {
    if len(q.items) == 0 {
        return 0, false
    }
    item := q.items[0]
    q.items = q.items[1:]
    return item, true
}

func main() {
    queue := &Queue{}
    queue.Enqueue(10)
    queue.Enqueue(20)

    fmt.Println(queue.Dequeue()) // 10
    fmt.Println(queue.Dequeue()) // 20
}

---

Кольцевая очередь:

goCopy codepackage main

import "fmt"

type CircularQueue struct {
    items []int
    size  int
    front int
    rear  int
}

func NewCircularQueue(size int) *CircularQueue {
    return &CircularQueue{
        items: make([]int, size),
        size:  size,
        front: -1,
        rear:  -1,
    }
}

func (q *CircularQueue) Enqueue(item int) bool {
    if (q.rear+1)%q.size == q.front {
        return false
    }
    if q.front == -1 {
        q.front = 0
    }
    q.rear = (q.rear + 1) % q.size
    q.items[q.rear] = item
    return true
}

func (q *CircularQueue) Dequeue() (int, bool) {
    if q.front == -1 {
        return 0, false
    }
    item := q.items[q.front]
    if q.front == q.rear {
        q.front, q.rear = -1, -1
    } else {
        q.front = (q.front + 1) % q.size
    }
    return item, true
}

func main() {
    cq := NewCircularQueue(5)
    cq.Enqueue(10)
    cq.Enqueue(20)
    fmt.Println(cq.Dequeue()) // 10
}

---

Приоритетная очередь:

goCopy codepackage main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    value    string
    priority int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Item)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}

func main() {
    pq := &PriorityQueue{}
    heap.Init(pq)

    heap.Push(pq, &Item{value: "A", priority: 3})
    heap.Push(pq, &Item{value: "B", priority: 1})
    heap.Push(pq, &Item{value: "C", priority: 2})

    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        fmt.Printf("%s (priority: %d)\n", item.value, item.priority)
    }
}

---

2. Стеки (LIFO)

Стек (Stack) — структура данных, работающая по принципу LIFO (Last In, First Out). Это значит, что последний добавленный элемент выходит первым. Пример: стопка тарелок, где последняя добавленная тарелка убирается первой.

---

Основные операции стека

1. Push (Добавление): Добавляет элемент в верхнюю часть стека.
2. Pop (Удаление): Удаляет верхний элемент.
3. Peek (Просмотр): Возвращает верхний элемент без его удаления.
4. IsEmpty (Проверка на пустоту): Проверяет, пуст ли стек.

---

Реализация стека на Go

goCopy codepackage main

import "fmt"

type Stack struct {
    items []int
}

func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
}

func (s *Stack) Pop() (int, bool) {
    if len(s.items) == 0 {
        return 0, false
    }
    item := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return item, true
}

func main() {
    stack := &Stack{}
    stack.Push(10)
    stack.Push(20)

    fmt.Println(stack.Pop()) // 20
    fmt.Println(stack.Pop()) // 10
}

---

3. Сравнение очередей и стеков

Характеристика	Очередь (FIFO)	Стек (LIFO)
Принцип	First In, First Out	Last In, First Out
Добавление	В конец очереди	В верхнюю часть стека
Удаление	С начала очереди	С верхней части стека
Пример использования	Обработка задач в порядке поступления	Реализация рекурсии или истории операций

---

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

• Очередь:
  • Потоковая обработка данных (например, очередь сообщений).
  • Планирование задач.
• Стек:
  • Управление вызовами функций.
  • Обратный обход данных (например, при парсинге или DFS).

---

Эти структуры данных являются основой многих алгоритмов и систем. Понимание их работы и умение реализовать их на практике поможет вам успешно пройти технические этапы собеседования!

https://www.youtube.com/shorts/_4qGDaMP0tY