Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос нашим менторам. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Стек

Алгоритмы — это хорошо, но структуры данных — ещё лучше.

Структура данных — это конкретный способ хранения и организации данных. В зависимости от решаемых задач, удобным оказывается либо один способ организации данных, либо другой. Как минимум, одну структуру данных вы уже знаете достаточно хорошо — это массив. С точки зрения организации, массив представляет собой совокупность элементов, к которым имеется индексированный доступ (доступ по индексу), а вот с точки зрения хранения — все сложнее. Массивы бывают разные и внутри языка реализуются тоже по-разному.

Каноническая организация хранения массива — непрерывный блок памяти. А индекс в таком случае играет роль смещения по ней. Именно поэтому индексация в массивах начинается с нуля, так как указывает на начало этого блока, а индекс под номером 1 уже является смещением. Но на практике всё сложнее. В PHP нет настоящих массивов. Об этом вы узнаете в следующем курсе.

Кроме массивов существует множество других структур данных, таких как списки, хеш-таблицы, деревья, графы, стек, очередь и другие. Использование структуры данных, подходящей под решаемую задачу, позволяет кардинально упростить код, устраняя запутанную логику.

Некоторые из перечисленных структур данных мы рассмотрим в процессе прохождения курсов и проектов, другие вам нужно будет подтянуть самостоятельно из книг (книги лучше, чем статьи). В любом случае алгоритмы и структуры данных (без фанатизма) составляют базу, на которую нанизывается все остальное в разработке.

Стоит разделять три понятия:

  • Структура данных
  • Конкретный тип данных (или просто "тип данных")
  • Абстрактный тип данных (АТД)

Со структурой данных всё понятно, выше было определение. С типом данных тоже все просто. Например, массив в PHP — это тип данных. Понятие «тип данных» всегда привязано к конкретному языку и может быть абсолютно чем угодно в зависимости от предпочтений разработчиков языка. Другими словами, если бы разработчики PHP решили, что числа надо назвать типом данных Array, то никто бы им этого не запретил, несмотря на абсурдность такого имени для чисел. Кроме встроенных типов данных, бывают и пользовательские. Так, PHP позволяет создавать интерфейсы и классы, но об этом мы поговорим чуть позже.

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

АТД нередко путают с понятием «структура данных», более того, часто, структуры данных и АТД имеют одно и тоже название.

Стек

Стек — упорядоченная коллекция элементов, в которой добавление новых и удаление старых элементов всегда происходит с одного конца коллекции. Обычно его называют вершиной стека.

Стек

У стека есть аналоги из реальной жизни. Слово stack с английского переводится как «стопка». По сути, любая стопка может рассматриваться как стек. Если не применять грубую физическую силу, то со стопками мы работаем двумя способами. Либо кладём новый элемент (например, книгу) на верхушку стопки, либо снимаем элемент с верхушки. Ещё более показательный пример — магазин в огнестрельном оружии. Первый заложенный патрон выйдет из магазина последним. Поэтому стек ещё называют "Last In First Out" (LIFO), то есть "последний зашёл, первый вышел".

Магазин

Возможно, на этом этапе у вас возник вопрос: ну да, есть стек, но зачем нам всё это?

Перед тем, как разбирать конкретную задачу, я покажу вам, что стек играет огромную роль в программировании. Вспомните, как исполняется любая программа. Одни функции вызывают другие, которые, в свою очередь, вызывают третьи, и так далее. После того, как выполнение заходит в самую глубокую функцию, та возвращает значение, и начинается обратный процесс. Сначала идёт выход из наиболее глубоких функций, затем из тех, что уровнем выше, и так далее до тех пор, пока не дойдёт до самой внешней функции. Вызов функций — не что иное, как добавление элемента в стек, а возврат — снятие со стека. Именно так всё устроено на аппаратном уровне. К тому же, если в процессе выполнения программы происходит ошибка, то её вывод часто называют Stack Trace (трассировка стека).

Другой пример, связанный с программированием — кнопка «назад» в браузере. История посещений представляет собой стек, каждый новый переход по ссылке добавляет её в историю, а кнопка «назад» извлекает из стека последний элемент.

Стек — абстрактный тип данных со следующим набором операций:

  • Добавить в стек (push)
  • Взять из стека (pop)
  • Вернуть элемент с вершины стека без удаления (peek)
  • Проверить на пустоту (isEmpty)
  • Вернуть размер (size)

В PHP стек можно создать на основе массивов. Для этого используется следующий набор функций: array_push, array_pop, empty, count.

<?php

$stack = [];
array_push($stack, 3);
print_r($stack);
// => Array
// => (
// =>     [0] => 3
// => )

array_push($stack, 'Winterfall');
print_r($stack);
// => Array
// => (
// =>     [0] => 3
// =>     [1] => Winterfall
// => )

array_push($stack, true);
print_r($stack);
// => Array
// => (
// =>     [0] => 3
// =>     [1] => Winterfall
// =>     [2] => 1
// => )

$element1 = array_pop($stack);
print_r("\n{$element1}\n");
// => 1

print_r($stack);
// => Array
// => (
// =>     [0] => 3
// =>     [1] => Winterfall
// => )

$element2 = array_pop($stack);
print_r("\n{$element2}\n");
// => Winterfall

print_r($stack);
// => Array
// => (
// =>     [0] => 3
// => )

https://repl.it/@hexlet/php-arrays-stack

Обратите внимание, что array_pop и array_push изменяют исходный массив. array_pop не только изменяет его, но и возвращает элемент, снятый со стека.

(Для любознательных: В PHP встроена реализация большинства популярных структур данных. Работа с ними требует знания механизмов ООП в PHP.)

Рассмотрим задачку, решение которой тривиально при использовании стека. Кстати, её нередко задают на собеседованиях, как раз чтобы убедиться, хорошо ли вы знаете базовые структуры данных.

Задача:

Необходимо реализовать функцию, которая проверяет, что парные символы сбалансированы. То есть каждый открывающий символ имеет закрывающий, и они не перекрываются, например так [{]}. К таким символам в нашем случае относятся <>, {}, () []. Входом в функцию может быть ()<>{}. Такой пример проходит проверку, а вот этот уже нет: [({)}]. Здесь происходит перекрытие фигурных и круглых скобок.

Решение со стеком выглядит так:

  1. Если перед нами открывающий элемент, то заносим его в стек
  2. Если закрывающий, то достаём из стека элемент (очевидно, последний добавленный) и смотрим, что он открывающий для данного закрывающего. Если проверка провалилась, значит выражение не соответствует требуемому формату.
  3. Если мы дошли до конца строки и стек пустой, то всё хорошо. Если в стеке остались элементы, то проверка не прошла. Такое может быть, если в начале строки были открывающие элементы, но в конце не было закрывающих.
<?php

function checkIfBalanced($expression)
{
    $stack = [];
    $startSymbols = ['{', '(', '<', '['];
    $pairs = ['{}', '()', '<>', '[]'];

    for ($i = 0, $len = strlen($expression); $i < $len; $i++) {
        $curr = $expression[$i]; 
        if (in_array($curr, $startSymbols)) {
            array_push($stack, $curr);
        } else {
            $prev = array_pop($stack); 
            $pair = "{$prev}{$curr}";
            if (!in_array($pair, $pairs)) {
                return false;
            }
        }
    }

    return count($stack) === 0;
}

var_dump(checkIfBalanced('[')); // => bool(false)
var_dump(checkIfBalanced('}{')); // => bool(false)
var_dump(checkIfBalanced('(([<>]){})')); // => bool(true)
var_dump(checkIfBalanced('([{]})')); // => bool(false)

https://repl.it/@hexlet/php-arrays-stack-balancing

Разберём его построчно:

<?php

function checkIfBalanced(string $expression): boolean
{
    // Инициализируем стек
    $stack = [];
    // Инициализируем список открывающих элементов
    $startSymbols = ['{', '(', '<', '['];
    // Инициализируем список пар.
    $pairs = ['{}', '()', '<>', '[]'];

    // Проходимся по строке от первого до последнего символа
    for ($i = 0; $i < strlen($expression); $i++) {
        $curr = $expression[$i];
        // Если текущий символ находится в списке открывающих символов, то заносим его в стек
        if (in_array($curr, $startSymbols)) {
            array_push($stack, $curr);
        } else { // Если элемент не входит в список открывающих, значит считаем что это закрывающий символ
            $prev = array_pop($stack);
            // Составляем из этих символов пару
            $pair = "{$prev}{$curr}";
            // Проверяем, что она входит в список $pairs. Если входит, то все правильно, двигаемся дальше; если нет,
            // то это автоматически означает, что символы не сбалансированы
            if (!in_array($pair, $pairs)) {
                return false;
            }
        }
    }

    // Если стек оказался пустой после обхода строки, то значит все хорошо
    return count($stack) === 0;
}

Предположим, что на вход функции попала следующая строка: [{]. Ниже описание ключевых шагов при выполнении функции проверки:

  1. Первый символ [ заносится в стек, так как он входит в список открывающих
  2. Символ { также заносится в стек по той же самой причине
  3. Символ ] относится к закрывающим, поэтому со стека забирается последний символ {. Из них составляется пара {], которая не проходит проверку.

Семантика

Может возникнуть соблазн использовать эти функции в повседневной практике. Например, чтобы извлечь из массива последний элемент. Несмотря на то, что array_pop действительно позволяет это сделать, такой вариант использования крайне нежелателен по нескольким причинам:

  1. Побочный эффект данной операции — изменение исходного массива. Даже если далее массив не используется, такой код вносит потенциальные проблемы и заставляет его переписывать в будущем.
  2. Нарушается семантика. Инструменты нужно использовать по назначению, иначе рождается код, который декларирует одно, но в реальности делает другое. Любой опытный программист, который видит array_pop или array_push сразу считает, что массив в данной части программы используется как стек, но на самом деле он этого не делает. Подобный код заставляет напрягаться и анализировать его лишний раз для понимания сути.

Дополнительные материалы

  1. array_push
  2. array_pop

<span class="translation_missing" title="translation missing: ru.web.courses.lessons.mentors.mentor_avatars">Mentor Avatars</span>

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят менторы из команды Хекслета или другие студенты.

Для полного доступа к курсу нужна профессиональная подписка

Профессиональная подписка откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, даст возможность обращаться за помощью к менторам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
115
курсов
892
упражнения
2241
час теории
3196
тестов

Зарегистрироваться

или войти в аккаунт

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 115 курсов, 2000+ часов теории
  • 800 практических заданий в браузере
  • 250 000 студентов

Отправляя форму, вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг». Защита от спама reCAPTCHA «Конфиденциальность» и «Условия использования».

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Rambler
Логотип компании Bookmate
Логотип компании Botmother

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг». Защита от спама reCAPTCHA «Конфиденциальность» и «Условия использования».