Что такое стек как структура данных и как его реализовать в Go?

Ответ

Стек (Stack) — это абстрактная структура данных, работающая по принципу LIFO (Last-In, First-Out / «Последним пришел — первым вышел»). Представить стек можно как стопку тарелок: вы можете добавить новую тарелку только сверху и взять тоже только верхнюю.

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

Push: Добавить элемент на вершину стека.
Pop: Удалить и вернуть элемент с вершины стека.
Peek (или Top): Посмотреть элемент на вершине, не удаляя его.
IsEmpty: Проверить, пуст ли стек.

Идиоматичная реализация на Go

В Go стек удобно реализовывать на основе слайса. Важно правильно обрабатывать случай, когда стек пуст.

package main

import (
    "fmt"
)

// Stack определяет стек для целых чисел
type Stack []int

// IsEmpty проверяет, пуст ли стек
func (s *Stack) IsEmpty() bool {
    return len(*s) == 0
}

// Push добавляет элемент на вершину стека
func (s *Stack) Push(v int) {
    *s = append(*s, v) // Просто добавляем в конец слайса
}

// Pop удаляет элемент с вершины и возвращает его.
// Возвращает (значение, true) при успехе и (0, false), если стек пуст.
func (s *Stack) Pop() (int, bool) {
    if s.IsEmpty() {
        return 0, false
    }
    index := len(*s) - 1   // Индекс последнего элемента
    res := (*s)[index]      // Получаем значение
    *s = (*s)[:index]       // Уменьшаем слайс, удаляя элемент
    return res, true
}

func main() {
    var s Stack
    s.Push(10)
    s.Push(20)
    s.Push(30)

    val, ok := s.Pop() // val: 30, ok: true
    if ok {
        fmt.Printf("Popped: %dn", val)
    }

    val, ok = s.Pop() // val: 20, ok: true
    if ok {
        fmt.Printf("Popped: %dn", val)
    }

    val, ok = s.Pop() // val: 10, ok: true
    if ok {
        fmt.Printf("Popped: %dn", val)
    }

    val, ok = s.Pop() // val: 0, ok: false
    if !ok {
        fmt.Println("Stack is empty")
    }
}

Основные области применения:

Отслеживание вызовов функций (стек вызовов).
Операции «Отменить»/«Вернуть» (Undo/Redo) в редакторах.
Разбор (парсинг) синтаксических конструкций и математических выражений.
Алгоритмы обхода графов и деревьев (DFS - Depth-First Search).