Стек на срезе

Новых конструкций Go в этой теме нет. Вы соберёте небольшие инструменты из деталей, которые уже знаете: срезов, циклов, map, методов и ошибок. Первый инструмент — стек.

Представьте стопку тарелок. Чистую тарелку кладут сверху, и брать тоже удобно сверху. Тарелка, которую положили последней, уйдёт первой.

Так же работает кнопка «Отменить» в редакторе: сначала она отменяет последнее действие, затем предпоследнее. Программе здесь нужен порядок, обратный порядку записи.

Отмена действий

В Go обратный порядок даёт обычный срез, если добавлять и забирать элементы только с его конца:

package main

import "fmt"

func main() {
    var stack []string
    stack = append(stack, "type", "bold", "delete")
    last := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    fmt.Println(last, stack) // delete [type bold]
}

Давайте разберём пример по строкам:

1. var stack []string объявляет пустую стопку.
2. append кладёт в стопку три действия: набор текста, жирный шрифт и удаление.
3. last := stack[len(stack)-1] берёт верхнее действие, "delete".
4. stack = stack[:len(stack)-1] убирает его из стопки.
5. fmt.Println(last, stack) печатает delete [type bold].

Вершина стека

Стек — набор значений, в который добавляют и из которого забирают только с одного конца. Этот конец называют вершиной. Значение, положенное последним, забирают первым.

В срезе вершина — его последний элемент, stack[len(stack)-1].

Здесь аналогия с тарелками заканчивается. Из настоящей стопки нижнюю тарелку не вытащить, а срез позволяет прочитать любой элемент по индексу. Стеком срез делает договорённость: код трогает только его конец.

Операции со стеком

Со стеком на срезе работают три операции.

Положить на стек

Положить значение на стек — значит добавить его вызовом append. Вызов append(stack, "type", "bold", "delete") добавляет три значения по очереди, и на вершине оказывается последнее из них, "delete".

Посмотреть на вершину

Выражение stack[len(stack)-1] только читает вершину и стек не меняет.

Снять со стека

Снять значение — это два шага:

1. Прочитать вершину: stack[len(stack)-1].
2. Укоротить срез выражением stack[:len(stack)-1].

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

Обратный порядок

Цикл for len(stack) > 0 снимает значения, пока стек не опустеет. Они выходят в порядке, обратном тому, в котором их клали:

words := []string{"one", "two", "three"}
var stack []string
for _, w := range words {
    stack = append(stack, w)
}
var out []string
for len(stack) > 0 {
    top := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    out = append(out, top)
}
fmt.Println(out) // [three two one]

Давайте разберём, что здесь происходит:

1. Первый цикл кладёт слова на стек.
2. Второй цикл снимает их по одному и дописывает в out.
3. Последним на стек попало "three", поэтому оно выходит первым, и программа печатает [three two one].

Тип элементов может быть любым: стек чисел или рун устроен так же.

Где нужен стек

Стек подходит задачам, где то, что открылось последним, должно закрыться первым. Два примера:

• вложенные скобки в выражении — проверка скобок стеком часто встречается на собеседованиях;
• вызовы функций — Go хранит их так же: функция, вызванная последней, завершается первой.

Частая ошибка

Значение снимают с пустого стека:

var stack []int
top := stack[len(stack)-1] // ✗
fmt.Println(top)

panic: runtime error: index out of range [-1]

Длина пустого среза равна 0, поэтому индекс получается -1, и программа останавливается с паникой. Из пустой стопки тарелку не взять. Перед тем как читать вершину, проверьте, что len(stack) > 0, как в цикле выше.

Главное

• Стек кладёт и снимает значения с одного конца: последнее положенное снимается первым.
• На срезе положить на стек — это append, вершина — stack[len(stack)-1], снять со стека — прочитать вершину и stack = stack[:len(stack)-1].
• Снятые значения выходят в обратном порядке.
• Перед чтением вершины проверяйте len(stack) > 0, иначе пустой стек вызовет панику.