От начального до среднего уровня: Очереди, списки и деревья (II)

Введение

В предыдущей статье От начального до среднего уровня: Очереди, списки и деревья (I), мы начали объяснять одну из тем, которую многие новички недооценивают, поскольку в большинстве случаев они не получают должных объяснений по определенным реализациям или моделям реализации. Многие новички просто считают, что для изучения программирования достаточно засучить рукава и погрузиться в книги и статьи. Но правда в том, что само программирование не очень сложно, поскольку всё, что вам нужно знать, сводится к знанию некоторых команд и их синтаксиса.

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

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

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

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

Очереди, списки и деревья (II)

Что ж, весьма вероятно, что если вы только начинаете программировать, то остались в некотором недоумении относительно того, где и как использовать то, что рассматривалось в предыдущей статье. Тем не менее, во многих ситуациях умение применять то, что было там рассмотрено и объяснено, может сыграть важную роль в вашей практике как программиста. Но вы, должно быть, заметили, что как очередь типа FIFO, так и циклическая очередь имеют общую черту: элементы в них всегда обрабатываются в том порядке, в котором они были помещены в очередь. То есть, самый старый элемент всегда считывается первым, и, следовательно, самый новый элемент в очереди всегда считывается последним. Однако зачастую нам необходимо изменить этот порядок на обратный. Итак, мы хотим, чтобы самый новый элемент считывался первым, а самый старый элемент в очереди — последним.

Можно даже подумать, что для этого достаточно было бы изменить порядок чтения элементов, помещенных в очередь FIFO или круговую очередь. На самом деле, в некоторых практических случаях именно так и происходит. Однако существует тип очереди, созданный специально для того, чтобы это можно было реализовать без необходимости изменять уже написанный код. Такой тип очереди, созданный специально для обращения порядка элементов, называется стеком.

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

Изображение 01

Для тех, кто не знаком с этой игрушкой, она известна как Ханойская башня). Поверьте, эта игрушка уже использовалась в прошлом для анализа и сравнения процессоров. Это связано с тем, что существуют способы её применения для получения хорошей оценки скорости обработки. Однако из-за того, что многие процессоры начали оптимизироваться для ускорения работы самого алгоритма, а не реальной скорости вычислений ЦП, от этой модели сравнения впоследствии отказались. Если вы хотите попробовать найти решение для этой башни на практике, вы можете заглянуть на сайт Somatemática.

Но при чём здесь мы? Что ж, уважаемый читатель, понимание того, как работает эта "Ханойская башня", поможет вам понять логику реализации стека. Сам стек очень легко реализовать. Но понимание того, где и когда его использовать — это то, что только с практикой вы научитесь видеть быстрее и без запинок. Чтобы это было проще понять, давайте возьмем за основу код очереди типа FIFO, который был показан и объяснен в предыдущей статье. Этот же код воспроизведен ниже.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> struct stFIFO
05. {
06.     private:
07. //+----------------+
08.         T   value[];
09. //+----------------+
10.     public:
11. //+----------------+
12.     T Restore(void)
13.     {
14.         T local = NULL;
15. 
16.         if (value.Size() > 0)
17.         {
18.             local = value[0];
19.             ArrayRemove(value, 0, 1);
20.         };
21.         return local;
22.     };
23. //+----------------+
24.     void Stock(T arg)
25.     {
26.         T local[1];
27.         local[0] = arg;
28.         ArrayInsert(value, local, value.Size());
29.     }
30. //+----------------+
31. };
32. //+------------------------------------------------------------------+
33. void OnStart(void)
34. {
35.     stFIFO <char> fifo;
36. 
37.     fifo.Stock(10);
38.     fifo.Stock(84);
39.     fifo.Stock(-6);
40. 
41.     Print(fifo.Restore());
42.     Print(fifo.Restore());
43.     Print(fifo.Restore());
44.     Print(fifo.Restore());
45. }
46. //+------------------------------------------------------------------+

Код 01

При выполнении кода 01 получается результат, который нам уже известен и который можно увидеть на следующем изображении:

Изображение 02

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

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> struct stStack
05. {
06.     private:
07. //+----------------+
08.         T   value[];
09. //+----------------+
10.     public:
11. //+----------------+
12.     bool Pop(T &arg)
13.     {
14.         arg = NULL;
15. 
16.         if (value.Size() == 0)
17.             return false;
18.         arg = value[0];
19.         ArrayRemove(value, 0, 1);
20.         return true;
21.     };
22. //+----------------+
23.     void Push(T arg)
24.     {
25.         T local[1];
26.         local[0] = arg;
27.         ArrayInsert(value, local, value.Size());
28.     }
29. //+----------------+
30. };
31. //+------------------------------------------------------------------+
32. void OnStart(void)
33. {
34.     stStack <char> my;
35. 
36.     my.Push(10);
37.     my.Push(84);
38.     my.Push(-6);
39. 
40.     for (char info; my.Pop(info);)
41.         Print(info);
42. }
43. //+------------------------------------------------------------------+

Код 02

Хорошо, обратите внимание, что мы изменили некоторые моменты из кода 01 в этом коде 02. Однако, даже в этом коде 02, мы по-прежнему используем очередь FIFO. Но при запуске результат будет немного отличаться, как можно видеть на изображении 03 ниже:

Изображение 03

Теперь самое интересное: Обратите внимание, что порядок добавления элементов в очередь не изменяется. Тем не менее, мы хотим, чтобы элементы, находящиеся в конце очереди — то есть самые последние элементы — считывались и удалялись из неё первыми, благодаря чему элементы будут считываться от самого нового к самому старому. А для этого нам нужно всего лишь изменить код в строках 18 и 19 кода 02. Тем самым мы меняем очередь типа FIFO на стек. Обратите внимание, как просто внести это изменение. И поскольку изменение, которое необходимо внести, находится в очень конкретном месте, мы можем оставить в стороне остальную часть кода и сосредоточиться только на этом конкретном моменте. Таким образом, необходимые изменения можно увидеть в следующем фрагменте кода:

                   .
                   .
                   .
11. //+----------------+
12.     bool Pop(T &arg)
13.     {
14.         arg = NULL;
15. 
16.         if (value.Size() == 0)
17.             return false;
18.         arg = value[value.Size() - 1];
19.         ArrayRemove(value, value.Size() - 1, 1);
20.         return true;
21.     };
22. //+----------------+
                   .
                   .
                   .

Фрагмент 01

"Это всё? Я не верю. Мне нужно увидеть результат выполнения этого кода". Что ж, уважаемый читатель, можно убедиться в этом, взглянув на следующее изображение, на котором показан результат, отображаемый в терминале MetaTrader 5.

Изображение 04

Обратите внимание, что на этом изображении 04 элементы считываются в порядке, обратном тому, который показан на изображении 03. И поскольку мы не меняем никакую другую часть кода, а только строки 18 и 19, это означает, что мы считываем элементы от самого последнего добавленного в очередь до самого старого. Другими словами, это работает; в результате мы получаем стек.

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

"Но теперь у меня есть вопрос. Существует ли такая реализация, и если да, то где она может быть использована? Какая-то из них использует концепцию стека в круговой очереди?" Что ж, мой уважаемый читатель, это возможно; ничто не мешает этому случиться. Ключевой вопрос заключается в том, какова будет цель такой реализации. Потому что в конечном итоге круговая очередь удалит самые старые элементы внутри себя. Однако, в зависимости от типа реализуемого случая, может быть интересно использовать концепцию стека в круговой очереди. Но это зависит от каждого конкретного случая. И поскольку это очень специфическая вещь, я не вижу причин показывать, как её реализовать здесь. Но я думаю, у вас не возникнет трудностей с этим, именно из-за сходства между очередью типа FIFO и круговой очередью. Это было показано в предыдущей статье.

Теперь, когда мы уже обсудили базовые типы очередей, пришло время превратить эти самые очереди во что-то немного более сложное. И в связи с этим возникает новое понятие: списки. Чтобы понять, что такое список и почему он является эволюцией очередей, вам сначала нужно понять одну вещь, которую вы, очевидно, уже должны были заметить. При работе с очередями мы НЕ МОЖЕМ изменить, или, точнее, не можем указать, в какую позицию следует поместить тот или иной элемент в очереди. Такого рода вещь тоже НЕВОЗМОЖНА. Всё, что мы можем сделать — это отправить элемент или данные для размещения в очереди, без возможности указать, где именно они будут размещены.

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

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

Прежде чем начать говорить непосредственно о списках, мне нужно кратко объяснить ещё кое-что. Объяснение будет очень кратким, чтобы вы поняли, что будет сделано. Мы подробнее рассмотрим эту тему позже. Дело в том, что MQL5 НЕ ПОЗВОЛЯЕТ ИСПОЛЬЗОВАТЬ УКАЗАТЕЛИ НА СТРУКТУРЫ. "Не понимаю. Почему это проблема для нас?" Что ж, уважаемый читатель, проблема в том, что для корректного создания списков нам необходимо использовать указатели. И какой бы ни была причина, здесь, в MQL5, мы не можем сделать это с помощью структур.

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

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

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. class stList
05. {
06.     private:
07. //+----------------+
08.         int info;
09. //+----------------+
10.     public:
11. //+----------------+
12.         void Set(int arg)
13.         {
14.             info = arg;
15.         }
16. //+----------------+
17.         int Get(void)
18.         {
19.             return info;
20.         }
21. //+----------------+
22. };
23. //+------------------------------------------------------------------+
24. void OnStart(void)
25. {
26.     stList list;
27. 
28.     list.Set(512);
29.     Print(list.Get());
30. };
31. //+------------------------------------------------------------------+

Код 03

Это, как видно в коде 03, пока НЕ представляет собой список. Но я хочу, чтобы вы обратили внимание на то, что написано в строке 04. Здесь ключевое слово class заменяет зарезервированное слово struct. Поэтому, пока не объясним понятие класса, следует рассматривать этот код как создание структуры, а не класса. Поскольку результат выполнения этого кода очень прост, я не буду вдаваться в подробности. Но, если мы немного изменим его, то сможем создать стек. Я предпочитаю начинать так; таким образом вы поймете, к чему я веду. Хорошо, чтобы превратить код 03 в стек, нам нужно изменить его, как показано ниже:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> class stList
05. {
06.     private:
07. //+----------------+
08.         T info[];
09. //+----------------+
10.     public:
11. //+----------------+
12.         void Push(T arg)
13.         {
14.             T loc[1];
15.             loc[0] = arg;
16.             ArrayInsert(info, loc, info.Size());
17.         }
18. //+----------------+
19.         bool Pop(T &arg)
20.         {
21.             arg = NULL;
22.             if (info.Size() == 0)
23.                 return false;
24.             arg = value[value.Size() - 1];
25.             ArrayRemove(value, value.Size() - 1, 1);
26. 
27.             return true;
28.         }
29. //+----------------+
30. };
31. //+------------------------------------------------------------------+
32. void OnStart(void)
33. {
34.     stList <char> list;
35. 
36.     list.Push(10);
37.     list.Push(84);
38.     list.Push(-6);
39. 
40.     for (char info; list.Pop(info);)
41.         Print(info);
42. 
43. };
44. //+------------------------------------------------------------------+

Код 04

Этот код 04 при выполнении выдаст тот же результат, что и на изображении 04, поскольку здесь мы создали нечто очень похожее на код 02, используя фрагмент 01, рассмотренный в этой же статье. Обратите внимание: мы ещё не создали список, потому что в строке 08 мы всё ещё используем массив. Теперь я хочу, чтобы вы обратили особое внимание на одну вещь в коде 04. Обратите внимание на то, что мы делаем в строках 16 и 25. В этих строках мы добавляем элементы в массив, а также удаляем из него элемент.

Но вот тут начинается самое интересное: что произойдет, если мы удалим массив из системы? В этом случае строки 16 и 25 больше не будут действительны, поскольку мы больше не будем работать с массивом. Однако, если мы преобразуем строку 08 из кода 04 в скалярное значение, мы вернемся к ситуации, наблюдавшейся в коде 03, где мы не могли добавить последовательность значений в память, а затем извлечь их. Вы, наверное, не поняли, что я только что сказал. Итак, давайте переведем эти слова в код. Это показано ниже:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> class stList
05. {
06.     private:
07. //+----------------+
08.         T info;
09. //+----------------+
10.     public:
11. //+----------------+
12.         void Push(T arg)
13.         {
14.             info = arg;
15.         }
16. //+----------------+
17.         bool Pop(T &arg)
18.         {
19.             arg = info;
20. 
21.             return true;
22.         }
23. //+----------------+
24. };
25. //+------------------------------------------------------------------+
26. void OnStart(void)
27. {
28.     stList <char> list;
29. 
30.     list.Push(10);
31.     list.Push(84);
32.     list.Push(-6);
33. 
34.     for (char info, c = 0; list.Pop(info) && c < 4; c++)
35.         Print(info);
36. 
37. };
38. //+------------------------------------------------------------------+

Код 05

Теперь, при выполнении кода 05, мы получим результат, показанный на следующем изображении:

Изображение 05

В данном случае потребовалось изменить строку 34, расположенную в коде 05, чтобы избежать бесконечного цикла. Но посмотрите, что произошло с кодом 05. В данном случае мы работаем с кодом, который больше не может запоминать значения, переданные нами в строках с 30 по 32, и будет возвращено только последнее значение. Вы, естественно, можете подумать, что это происходит так, потому что в строке 08 из кода 05 используется скалярная величина, а не массив. И вот в этом и кроется вся загвоздка, и именно здесь список начинает обретать смысл.

Что нам необходимо сделать здесь — это создать механизм, который каким-то образом заставит переменную в строке 08 запомнить своё значение. Это должно происходить при использовании процедур и функций доступа. Однако этот механизм НЕ ДОЛЖЕН ИСПОЛЬЗОВАТЬ МАССИВ. Итак, как мы можем это сделать? Ответ показан в приведенном ниже коде:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> class stList
05. {
06.     private:
07. //+----------------+
08.         T info;
09.         stList <T> *prev;
10. //+----------------+
11.     public:
12. //+----------------+
13.         stList(void)
14.             :prev(NULL)
15.         {}
16. //+----------------+
17.         void Push(T arg)
18.         {
19.             stList <T> *loc;
20. 
21.             loc = new stList <T>;
22.             (*loc).info = arg;
23.             (*loc).prev = prev;
24.             prev = loc;
25.         }
26. //+----------------+
27.         bool Pop(T &arg)
28.         {
29.             stList <T> *loc;
30. 
31.             if (prev == NULL)
32.                 return false;
33. 
34.             loc = prev;
35.             arg = (*loc).info;
36.             prev = (*loc).prev;
37. 
38.             delete loc;
39. 
40.             return true;
41.         }
42. //+----------------+
43. };
44. //+------------------------------------------------------------------+
45. void OnStart(void)
46. {
47.     stList <char> list;
48. 
49.     list.Push(10);
50.     list.Push(84);
51.     list.Push(-6);
52. 
53.     for (char info; list.Pop(info);)
54.         Print(info);
55. };
56. //+------------------------------------------------------------------+

Код 06

То, что вы видите в коде 06, — это очень, очень занятная вещь. И в то же время это очень интересно, поскольку при выполнении этого кода 06 вы получите тот же результат, что и на изображении 04. Обратите внимание, что здесь мы не используем массив. Но как же это возможно? Ответ заключается в том, что данный код 06 создает то, что известно как односвязный список. Однако этот список используется не в полной мере. Он смоделирован только для того, чтобы вы могли понять, что мы здесь делаем. В этой статье мы, по сути, говорим о стеке. И поскольку стек — это разновидность простой очереди, мы, скажем так, создали простой список, но с теми же операционными возможностями, которые были бы получены, если бы мы запрограммировали стек.

Теперь я хочу, чтобы вы обратили внимание на следующий факт. Этот код 06 выдаёт тот же результат, который можно было бы увидеть при использовании кода 04. Или даже код 02, но с включенным в него фрагментом 01. В данном случае полный код будет доступен в приложении, как и этот код 06.

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

То есть вы можете реализовать нечто, что изнутри работает одним образом, а пользователь вашего кода даже не догадается, какой именно механизм вы используете. В этом и заключается прелесть программирования. Можно создавать вещи таким образом, что многим они покажутся абсурдными, будь то из-за сложности или из-за предельной простоты. Это не имеет значения; важно то, какой будет конечный результат.

"Хорошо, кажется, я понял. Но не могли бы вы объяснить, как работает код 06? Я не понимаю, как можно сохранять значения, а затем восстанавливать их, как показано". Никаких проблем, уважаемый читатель. Думаю, у вас нет сомнений в том, как работает процедура OnStart, расположенная в строке 45. Ваше главное сомнение, должно быть, заключается в том, как именно нам удаётся помещать значения в стек без использования массива, что позволяет извлекать их в будущем. Чтобы это понять, необходимо, чтобы вы понимали или уже знали другую тему, которую я здесь уже затрагивал.

Речь идёт о рекурсии. Эта тема была затронута в статье От начального до среднего уровня: Рекурсия . Почему же понимание данной темы важно именно здесь? Причина заключается в том, что когда мы создаем список или начальную базу списка, как это делается в коде 06, мы создаем механизм рекурсии. Однако этот механизм несколько отличается от того, который обсуждался в вышеупомянутой статье. Поэтому будьте внимательны, чтобы понять происходящее здесь. Вы можете заметить, что в строке 04 из кода 06 мы объявляем шаблон класса. Теперь забудьте о том, что мы используем класс; думайте об этом как о структуре. Что ж, внутри структуры данных мы можем логически сгруппировать различные данные. Обычно эти данные относятся только к значениям, которыми вы, как программист, можете манипулировать и которые можете объявлять. Это основной принцип.

Поэтому в строке 08 мы имеем значение, которым мы, как программисты, можем манипулировать наиболее удобным способом. Но — и именно здесь начинает происходить магия — внутрь структуры данных мы также можем добавить один дополнительный элемент. Или элементы, в зависимости от конкретного случая. В нашем случае этот дополнительный элемент — это именно строка 09. Данная строка похожа на волшебную строку, и если вы посмотрите на нее, то увидите, что мы объявили указатель. Но на что показывает указатель? Этот указатель будет показывать на копию структуры, объявленной в строке 04. "Ого, теперь всё действительно сильно осложнилось. Как такое возможно? Находимся ли мы внутри структуры, которая будет указывать на саму себя? Это не имеет особого смысла. По крайней мере, так мне кажется". В каком-то смысле я должен с вами согласиться, уважаемый читатель. Когда я только начинал изучать программирование, мне было непросто понять то, что я пытаюсь вам объяснить.

Дело в том, что при использовании указателя, объявленного в строке 09 внутри структуры, мы можем создать рекурсию внутри самой структуры, не затрагивая при этом саму структуру. Поскольку вы, скорее всего, видите это впервые, вам это может показаться не совсем понятным. Но станет понятно, когда мы расширим функциональность кода 06 для создания связанного списка. Но прежде чем это сделать, необходимо усвоить те понятия, которые я объясняю. Иначе вы не сможете усвоить знания, необходимые для создания собственных кодов.

Хорошо, давайте вернемся к объяснению. Когда мы используем процедуру из строки 17 для добавления элемента в стек, обратите внимание, что первым делом мы объявляем в строке 19 нечто очень похожее на то, что представлено в строке 9. Иными словами, указатель. Однако здесь, в строке 19, этот указатель является локальным и временным. Обратите пристальное внимание на этот момент, потому что он важен. В строке 21 мы выделяем память для типа структуры, объявленной в указателе в строках 09 и 19.

Теперь наступает момент, когда многие теряются, пытаясь разобраться в этих списках. НЕ СЛЕДУЕТ СОХРАНЯТЬ НОВЫЙ ЭЛЕМЕНТ В ПЕРЕМЕННОЙ, ОБЪЯВЛЕННОЙ В СТРОКЕ 08. Необходимо сохранить новый элемент в выделенной нами области памяти. Помните, что эта область памяти в точности соответствует тому, что объявлено в структуре, для которой мы выделили память. Таким образом, переменная в строке 08 теперь может быть использована для хранения нового элемента. Однако самое важное — это то, что происходит в строке 23. Именно в этот момент мы создаём связь между текущей позицией и новой позицией, формируя таким образом цепную структуру, которая в определённом смысле напоминает массив, как будет показано позже.

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

Изображение 06

Здесь зеленая область указывает на содержимое, находящееся в переменной строки 08. Напротив, красная область указывает значение указателя, объявленного в строке 09. Хорошо, это происходит при выполнении строки 47. Теперь, когда выполнится строка 49, произойдет вызов процедуры Push, которую можно увидеть в строке 17 и принцип работы которой я только что кратко описал. Но чтобы значительно упростить понимание принципа работы этой процедуры Push, мы воспользуемся новым изображением. Оно показано ниже:

Изображение 07

"Хм, я не понял. Что показывает изображение 07?" Оно иллюстрирует формирование рекурсивной структуры данных. Обратите внимание, что значение 10 теперь помещено в память, но значение переменной, присутствующей в строке 09, теперь указывает на предыдущую область памяти. Это обозначено жёлтой стрелкой. После выполнения строки 51 мы получим результат, показанный на следующем изображении:

Изображение 08

Обратите внимание, что во всех случаях значение, которое будет записано в переменную в строке 09, всегда будет указывать на ранее выделенную область памяти. Это создает цепочку значений. Таким образом, когда запустится цикл в строке 53, мы пройдём по этой структуре, показанной на изображении 08, только в обратном порядке. Обратите внимание, что условие, приводящее к завершению цикла в строке 53, выполняется ровно в строке 31. Когда это условие выполняется, это означает, что мы достигли начальной базы списка. Таким образом, мы можем извлекать данные из стека очень простым и легким способом, для чего достаточно использовать механизм, обратный механизму, принятому при помещении в стек.

В данном конкретном случае мы использовали строку 34 для доступа к области памяти, которая была выделена в строке 21. Это упрощает код, поскольку мы могли бы использовать другой способ указания компилятору, что делать. Но, поскольку цель здесь — дидактическая, я решил оставить это в таком виде. Таким образом, поскольку теперь мы указываем на выделенную область памяти, мы сможем получить доступ к значению в этой области, используя для этого строку 35. И при использовании строки 36 мы обновляем текущий указатель, чтобы, наконец, в строке 38 мы могли освободить ранее выделенную память, тем самым завершая цикл.

Заключительные идеи

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

Я постарался изложить всё максимально познавательно, и считаю, что достиг этой цели. В любом случае, обязательно внимательно изучите эти коды, уважаемый читатель, поскольку в следующей статье мы немного глубже погрузимся в тему списков. Но без понимания того, что было показано и объяснено здесь, будет очень сложно понять материал, который будет рассмотрен в следующей статье. Так что усердно учитесь, и увидимся в следующей статье.

Файл	Описание
Code 01	Простая очередь
Code 02	Простая очередь