Что такое стек (Stack) и как его реализовать на Go?

Ответ

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

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

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

Реализация в Go:
В Go стек удобно реализовывать на основе слайса (slice).

package main

import "fmt"

// Stack определяет стек для целых чисел (int).
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 удаляет и возвращает элемент с вершины стека.
// В продакшн-коде лучше возвращать (int, bool) или (int, error),
// чтобы избежать паники при пустом стеке.
func (s *Stack) Pop() (int, bool) {
    if s.IsEmpty() {
        return 0, false
    }
    index := len(*s) - 1   // Индекс последнего элемента
    element := (*s)[index] // Получаем элемент
    *s = (*s)[:index]      // Уменьшаем слайс, удаляя последний элемент
    return element, 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() // ok = false
    if !ok {
        fmt.Println("Stack is empty")
    }
}

Где используется:

Стек вызовов (Call Stack): для отслеживания вызовов функций в программе.
Парсинг выражений: например, для проверки сбалансированности скобок {[()]}.
Алгоритмы обхода графов и деревьев (DFS).
Функциональность "Отмена" (Undo/Redo) в приложениях.