Реализовать Stack на слайсе

Решение

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

Подход

Используем слайс для хранения элементов:

• Push: добавить элемент в конец слайса
• Pop: удалить и вернуть последний элемент
• Peek: вернуть последний элемент без удаления

Реализация

package main

import "fmt"

type Stack struct {
    items []int
}

func NewStack() *Stack {
    return &Stack{
        items: make([]int, 0),
    }
}

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

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

func (s *Stack) Peek() (int, bool) {
    if s.IsEmpty() {
        return 0, false
    }
    
    return s.items[len(s.items)-1], true
}

func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

func (s *Stack) Size() int {
    return len(s.items)
}

func main() {
    s := NewStack()
    
    s.Push(1)
    s.Push(2)
    s.Push(3)
    
    val, ok := s.Pop()  // 3
    fmt.Printf("Pop: %d, ok: %v\n", val, ok)
    
    val, ok = s.Peek()  // 2
    fmt.Printf("Peek: %d, ok: %v\n", val, ok)
    
    fmt.Printf("Size: %d\n", s.Size())  // 2
    
    fmt.Printf("IsEmpty: %v\n", s.IsEmpty())  // false
}

Пошаговый пример

Операция    Stack       Size
────────────────────────────
NEW         []          0
Push(1)     [1]         1
Push(2)     [1,2]       2
Push(3)     [1,2,3]     3
Pop()       [1,2]       2  (вернула 3)
Peek()      [1,2]       2  (вернула 2, не удалила)
Size()      [1,2]       2
Pop()       [1]         1  (вернула 2)
Pop()       []          0  (вернула 1)
Pop()       []          0  (ошибка: стек пуст)

Анализ сложности

• Push: O(1) amortized — append к слайсу
• Pop: O(1) — удаление с конца
• Peek: O(1) — доступ к последнему элементу
• Size/IsEmpty: O(1)

Полный код с примерами

package main

import "fmt"

type Stack struct {
    items []int
}

func NewStack() *Stack {
    return &Stack{
        items: make([]int, 0),  // инициализируем пустой слайс
    }
}

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

// Pop удаляет и возвращает элемент с вершины
func (s *Stack) Pop() (int, bool) {
    if s.IsEmpty() {
        return 0, false  // ошибка: стек пуст
    }
    
    val := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return val, true
}

// Peek возвращает элемент с вершины без удаления
func (s *Stack) Peek() (int, bool) {
    if s.IsEmpty() {
        return 0, false
    }
    
    return s.items[len(s.items)-1], true
}

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

// Size возвращает количество элементов
func (s *Stack) Size() int {
    return len(s.items)
}

func main() {
    // Пример 1: Базовое использование
    fmt.Println("=== Пример 1: Базовое использование ===")
    s := NewStack()
    
    s.Push(1)
    s.Push(2)
    s.Push(3)
    
    val, ok := s.Pop()
    fmt.Printf("Pop: %d (ok=%v)\n", val, ok)  // 3, true
    
    val, ok = s.Peek()
    fmt.Printf("Peek: %d (ok=%v)\n", val, ok)  // 2, true
    
    fmt.Printf("Size: %d\n", s.Size())  // 2
    fmt.Printf("IsEmpty: %v\n", s.IsEmpty())  // false
    
    // Пример 2: Пустой стек
    fmt.Println("\n=== Пример 2: Операции на пустом стеке ===")
    s2 := NewStack()
    
    val, ok = s2.Pop()
    fmt.Printf("Pop на пустом: (ok=%v)\n", ok)  // false
    
    val, ok = s2.Peek()
    fmt.Printf("Peek на пустом: (ok=%v)\n", ok)  // false
    
    fmt.Printf("IsEmpty: %v\n", s2.IsEmpty())  // true
    
    // Пример 3: Проверка скобок (практический пример)
    fmt.Println("\n=== Пример 3: Проверка сбалансированности скобок ===")
    isBalanced := checkBalancedParentheses("((({})")
    fmt.Printf("((({}) сбалансирована: %v\n", isBalanced)  // false
    
    isBalanced = checkBalancedParentheses("(()())")
    fmt.Printf("(()()) сбалансирована: %v\n", isBalanced)  // true
}

// Практический пример: проверка сбалансированности скобок
func checkBalancedParentheses(s string) bool {
    stack := NewStack()
    
    for _, char := range s {
        switch char {
        case '(':
            stack.Push(int(char))
        case ')':
            if stack.IsEmpty() {
                return false
            }
            stack.Pop()
        }
    }
    
    return stack.IsEmpty()
}

Обработка ошибок через tuple (comma-ok idiom)

val, ok := s.Pop()
if !ok {
    fmt.Println("Stack is empty!")
    return
}
fmt.Printf("Popped: %d\n", val)

Альтернативный подход: возвращать ошибку

import "errors"

var ErrStackEmpty = errors.New("stack is empty")

func (s *Stack) Pop() (int, error) {
    if s.IsEmpty() {
        return 0, ErrStackEmpty
    }
    
    val := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return val, nil
}

// Использование
val, err := s.Pop()
if err != nil {
    fmt.Printf("Ошибка: %v\n", err)
}

Generic версия (Go 1.18+)

type Stack[T any] struct {
    items []T
}

func NewStack[T any]() *Stack[T] {
    return &Stack[T]{items: make([]T, 0)}
}

func (s *Stack[T]) Push(val T) {
    s.items = append(s.items, val)
}

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

func main() {
    // Работает со строками
    stringStack := NewStack[string]()
    stringStack.Push("hello")
    stringStack.Push("world")
    
    val, _ := stringStack.Pop()
    fmt.Println(val)  // world
    
    // Работает с float64
    floatStack := NewStack[float64]()
    floatStack.Push(3.14)
    val2, _ := floatStack.Pop()
    fmt.Println(val2)  // 3.14
}

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

1. Обратная строка

func reverseString(s string) string {
    stack := NewStack()
    for _, ch := range s {
        stack.Push(int(ch))
    }
    
    result := ""
    for !stack.IsEmpty() {
        ch, _ := stack.Pop()
        result += string(rune(ch))
    }
    return result
}

// reverseString("hello") → "olleh"

2. Вычисление выражения в обратной польской нотации

func evaluateRPN(tokens []string) int {
    stack := NewStack()
    
    for _, token := range tokens {
        switch token {
        case "+", "-", "*", "/":
            b, _ := stack.Pop()
            a, _ := stack.Pop()
            result := 0
            switch token {
            case "+":
                result = a + b
            case "-":
                result = a - b
            case "*":
                result = a * b
            case "/":
                result = a / b
            }
            stack.Push(result)
        default:
            num := parseString(token)
            stack.Push(num)
        }
    }
    
    result, _ := stack.Pop()
    return result
}

Производительность: Предварительное выделение памяти

// Если знаем примерный размер
func NewStackWithCapacity(capacity int) *Stack {
    return &Stack{
        items: make([]int, 0, capacity),
    }
}

// Использование
s := NewStackWithCapacity(1000)  // заранее выделяем место
for i := 0; i < 1000; i++ {
    s.Push(i)  // нет переаллокаций
}

Ключевые выводы

1. Stack = слайс с добавлением/удалением с конца
2. Идеально для LIFO операций: скобки, история действий, DFS
3. O(1) операции на Push/Pop
4. comma-ok idiom для обработки пустого стека
5. Generics позволяют писать универсальные структуры данных

Stack — это фундаментальная структура, используемая в системах управления памятью, парсерах и поисковых алгоритмах.