Введение

В этом уроке ты

Узнаешь, что такое стек.
Научишься использовать стек в своем языке программирования.
Познакомишься с основными операциями стека.

Что такое стек

Представь, что перед приходом гостей тебе нужно достать все тарелки из коробки и разложить их на столе. Ты будешь брать самую верхнюю тарелку и класть её на стол. А после ужина, складывая тарелки обратно в коробку, ты будешь класть каждую следующую тарелку сверху на предыдущие.

Эта ситуация очень похожа на работу структуры данных, которая называется стек.

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

Кроме добавления и удаления элементов, стек поддерживает ещё несколько операций:

push — добавление элемента в вершину стека.
pop — удаление элемента с вершины стека.
top — просмотр последнего элемента (без удаления).
size — получение размера стека.

Операция	Время	Память
push	O(1)	O(1)
top	O(1)	O(1)
pop	O(1)	O(1)
size	O(1)	O(1)
Построение из массива	O(n)	O(n)

Анатомия стека

Самый последний элемент стека называется вершиной, а операцию добавления элемента часто называют push (от англ. «толкать» или «класть»).

Вот пример того, как это может звучать в разговоре программистов: «...нужно просто пушить очередной элемент и сравнивать вершину с максимальным значением...».

Стек в программировании

При работе со стеком доступен только самый верхний (последний добавленный) элемент. Чтобы получить доступ к элементам, находящимся ниже, нужно последовательно удалять элементы сверху.

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

Несмотря на различные способы реализации, любая структура, используемая как стек, должна поддерживать операции вставки, удаления, просмотра последнего элемента и определения размера с одинаковой скоростью выполнения — O(1).

using System;

class Solution
{
    static void Main()
    {
        
        // создаём стек
        Stack<string> stack = new Stack<string>();

        // добавляем два элемента
        stack.Push("первый");
        stack.Push("второй");

        // удаляем элемент с вершины
        stack.Pop();

        // получаем текущую вершину и длину стека
        string top = stack.Peek();
        int length = stack.Count;

        Console.WriteLine($"Вершина стека: {top}");  // выведет "первый"
        Console.WriteLine($"Длина стека: {length}"); // выведет 1
    }
}

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    
    // создаём стек
    stack<string> stack;

    // добавляем два элемента
    stack.push("первый");
    stack.push("второй");

    // удаляем элемент с вершины
    stack.pop();

    // получаем текущую вершину и длину стека
    string top = stack.top();
    size_t length = stack.size();

    cout << "Вершина стека: " << top << endl;  // выведет "первый"
    cout << "Длина стека: " << length << endl; // выведет 1

    return 0;
}

package main

import (
    "fmt"
)

func main() {
    // В языке Go нет встроенного типа данных
    // с названием «стек», поэтому обычно используется
    // срез (slice), который подходит для этих целей:

    // создаём стек
    stack := make([]string, 0)

    // добавляем два элемента
    stack = append(stack, "первый")
    stack = append(stack, "второй")

    // удаляем элемент с вершины
    stack = stack[:len(stack)-1]

    // получаем текущую вершину и длину стека
    top := stack[len(stack)-1]
    length := len(stack)

    fmt.Printf("Вершина стека: %s\n", top) // выведет "первый"
    fmt.Printf("Длина стека: %d\n", length) // выведет 1
}

import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        
        // создаём стек
        Stack<String> stack = new Stack<>();

        // добавляем два элемента
        stack.push("первый");
        stack.push("второй");

        // удаляем элемент с вершины
        stack.pop();

        // получаем текущую вершину и длину стека
        String top = stack.peek();
        int length = stack.size();

        System.out.printf("Вершина стека: %s%n", top);  // выведет "первый"
        System.out.printf("Длина стека: %d%n", length); // выведет 1
    }
}

# В языке Python нет встроенного типа данных
# с названием «стек», поэтому обычно используется
# структура данных deque (дек), которая подходит для этих целей:

from collections import deque

# создаём стек
stack = deque()

# добавляем два элемента
stack.append('первый')
stack.append('второй')

# удаляем элемент с вершины
stack.pop()

# получаем текущую вершину и длину стека
top = stack[-1]
length = len(stack)

print(f'Вершина стека: {top}')  # выведет "первый"
print(f'Длина стека: {length}')  # выведет 1

// В языке JavaScript нет встроенного типа данных
// с названием «стек», поэтому обычно используется
// массив, который подходит для этих целей:

// создаём стек
const stack = [];

// добавляем два элемента
stack.push('первый');
stack.push('второй');

// удаляем элемент с вершины
stack.pop();

// получаем текущую вершину и длину стека
const top = stack[stack.length - 1];
const length = stack.length;

console.log(`Вершина стека: ${top}`);  // выведет "первый"
console.log(`Длина стека: ${length}`); // выведет 1

Кратко о главном

Стек — это структура данных, поддерживающая операции вставки элемента в конец (push), удаление верхнего элемента (pop), просмотр последнего элемента (top) и получение размера (size). Все эти операции работают за O(1).
При работе с классическим стеком ты можешь взаимодействовать только с последним элементом. Доступ к элементам, находящимся ниже, возможен только после удаления всех элементов, которые находятся выше.
В некоторых языках программирования нет специальной структуры «стек», поэтому используется дек(deque).

Что дальше?

Скорее переходи к следующему уроку, где мы разберём задачу с собеседования, в решении которой применяется стек!