C++ для начинающих. Динамические структуры данных. СТЕК

В этот раз я опишу создание стека. На самом деле стек уже описывался на странице: С++ для начинающих. Однонаправленный список LIFO. Но первое время я не различал, что есть стек, а что есть список и не понимал, что тот стек — это тот же список. Поэтому получилось две темы: одна расписывает наиболее полно, вторая коротко обозначает понятие стека как динамической структуры данных.
  • Стек — это такой линейный список, в котором и добавление новых и удаление существующих элементов возможно только с головного элемента.
Часто стек сравнивают с ящиком, в который, например, складывают кирпичи; часто — со стопкой тарелок. Также стек часто называют LIFO, что обозначает "последним пришёл, первым ушёл". Наверное, последнее может быть непонятно, поэтому поясню на цифрах.
  • Вводим: 1,2,3,4,5
  • На выходе 5,4,3,2,1

Организацию стека можно представлять следующим образом: (см. картинку-анимашку)
  • При каждом новом добавлении элемента в стек мы должны запомнить адрес текущего элемента, после чего сместить голову, и указателем указать на тот запомненный адрес.
Указатель, который сохраняет адреса объектов, ниже в коде назван Next. Несмотря на то, что он переводится как следующий, фактически мы направляем его на элемент, уходящий в прошлое. Т. е. если пытаться воспринять его самым привычным образом, то он как указатель на предыдущий элемент. Поскольку началом постоянно обозначается самый последний сцепленный элемент, то следующим для него (при обходе всех его элементов) будет предпоследний, а следующий для предпоследнего идущий перед ним. Это как обход в обратном направлении. Отправная точка — последний элемент.
Как правило, для стека определены следующие операции:

  • Проверка стека на пустоту
  • Добавление элемента в стек
  • Считывание головного элемента
  • Удаление головного элемента
  • Очистка стека
Классическая реализация стека предполагает, что просмотреть данные стека без удаления его элементов невозможно. Но я приведу пример, в котором содержимое стека просматривается без удаления его элементов.
Не буду описывать код слишком подробно, ограничусь описанием в комментариях. Для создания и использования стека (или динамического списка LIFO) будем использовать 4 функции: (main(), Добавить в список, Показать список, Удалить список из памяти).

Я смотрю на свой первоначальный код (LIFO Первое знакомство), там с классами. И меня посещают мысли: "Неужели так сложно дать то, что так просто?" Я ведь много страниц тогда перерыл и не нашел этого.
Чтобы привести этот код к классическому пониманию стека, достаточно заменить мои temp -переменные на (*MyList) и тогда даже при простом просмотре просмотренные данные будут сразу теряться. Удаляться не будут, но связь потеряется. И если так сделаете, то будут паразитировать эти призраки стека и пожирать вашу память отныне и вовеки веков. При работе с динамическими данными надо быть очень внимательным к памяти и не нужно этого забывать.
Стек можно обсмотреть с противоположной стороны голове, но это требует очень многого с точки зрения затрат памяти, потому что каждый раз придется проходить от головы до последнего элемента ровно столько раз, сколько в стеке элементов. А это чтобы два элемента считать, надо два раза по всему стеку пройтись. Для стека можно выполнить и другие нетипичные для него операции, но кроме как для лучшего понимания материала это вряд ли стоит делать.
В моем примере стек был построен на основе линейного связного списка, но стеки могут реализовываться на различных структурах данных: на одномерных статических и динамических массивах, на линейных списках, с помощью файлов… В общем, стек можно реализовать на любой структуре, в которой есть возможность хранить несколько элементов и если есть то, куда можно сохранять данные.
==============================================================
Ещё один пример стека:


36 комментариев на «“C++ для начинающих. Динамические структуры данных. СТЕК”»

  1. Аноним:

    Малочик!

    7
    6
  2. Qasta:

    Спасибо!!!

  3. Den4ik:

    Спасибо, большое.

  4. Ксю и Даша:

    СПАСИБО огромное!
    благодаря тебе мы сдадим лабу!!! :****

  5. Аноним:

    😳 🙂 👿 😛 ❓ 😛 🙁

  6. Аноним:

    LIFO (Last In, First Out) — последний пришел, первый ушел. Смотрите абзац: Часто стек сравнивают с ящиком…

    4
    7
  7. Andrey:

    спасибо огромное!!!!!

  8. вывыаа:

    пасиба памагли

  9. Аноним:

    Это самый лучший стек который я видел, огромный респект автору,кратко,четко, по существу, очень помог, спасибо!

  10. глупый анон:

    ОГРОМНОЕ СПАСИБО АВТОРУ!!! ВСЕ ЗДОРОВО ВСЕ ПОНЯТНО теперь получу допуск к экзамену)

    только вот компилятор ругался на эти строки

    я заменил так и все заработало)

  11. Аноним:

    Здрааасьте)

  12. Александр:

    Только что попробовал запустить программу, компилятор выдал ошибку, что Х не объявлен в функции добавления. Я исправил немного код, необходимо было еще добавить (temp->x). Я просто подумал может кому-то понадобиться.

  13. Андрей:

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

    • Да, есть утечка, исправлю. Чем кроме этого вас такое написание не устраивает?

      • Андрей:

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

        • Почему она должна создаваться и чем это отличается от создаётся локальная копия адреса внутри функции, мне кажется тут вы заблуждаетесь. Происходит обычная передача указателя по ссылке.

          9
          5
          • Андрей:

            Может быть заблуждаюсь, однако по Стивену Прата и Страуструпу:

            Там говорится о том, что сама переменная-аргумент, даже в таком виде:

            void func (int *arg);

            Так вот адрес попеёод переменную arg также выделяется память для хранения копии адреса переданного ууеазателя.
            т.е

            int a = 5;
            int *p_a = &a;

            func (p_a);

            В данном случае действительно данные из а не копируются, а вот значение переменной p_a, то есть адрес переменной а передается в новый указатель arg. Если бы этого не происходило, то Вы могли бы в функции func написать такое:

            arg = какой-какой-то адрес;

            И указатель p_a поменял бы свое значение и указывал бы на что-то другое и пятерка бы не вывелась. Этого не происходит так как в действительности мы все равно работаем с копией, только уже копией адреса. В общем проверьте пример, посиотрите что Стивен Прата пишет, Вы поймете.

            • Есть более простой пример доказать мне мою неправоту.

              И все встает на свои места. Я ошибся. Надо не **, а *&
              Спасибо, что указали на этот момент. Я считал, что ** то же, что и *&, а оно вон он какое хитрое оказывается.

              Если на что еще наткнетесь, дайте знать. Спасибо за помощь.

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

          (Я могу ошибаться, но по моей логике так)

  14. Андрей:

    Для очистки стека кстати можно было бы просто while звзаменить на do — while и перед циклом проверку на непостоту текущего элемента вставить.

  15. Freerider:

    Накатал свой вариант стека совместил несколько программ может кому-нибудь понадобится

  16. Аноним:

    помогите)) где нужно прописать этот код класса со стеком!? я его прописывала в
    Microsoft Visual Studio, c расширением «.с» где найти как поэтапно создать эту программу с правильным расширением и настройками

  17. Дима:

    Объясните, пожалст — в 1-й строчке:

    каким образом работают эти строчки? указателю «Next» становится равен указатель » Head». Почему на «Next» указывает указатель «temp», а на » Head » указатель «MyList»?

    во 2-й строчке:

    указателю «Head» на который указывает » MyList » приравнивается значение указателя » temp» ?

  18. Дима:

    А чему тогда равно значение указателя  ” temp” ?

    • temp Просто указывает на область памяти, которая хранит блок стека. Для удобства можно воспринимать этот temp блоком памяти, хотя он блоком памяти не является. А из этого блока памяти нам доступны отдельные кусочки этого блока, эти кусочки нам и нужны. Их я в примере и задействываю. temp — это указатель на начало такого блока памяти.

  19. Алексей:

    Есть предложение заменить во втором примере аргументы d и next на другие переменные, а то так запутаться можно.

  20. ДМ:

    Если нужно сначала ввести число в стек (диалог с пользователем), после ввода числа вывести массив из чисел.

    К примеру ввели число с клавиатуры 1, после это он вывел само число 1 и остальные числа. Как реализовать с помощью ввода, чтобы сначала число вводить потом вывод всех чисел на экран?

  21. igor:

    а почему тут копия указателя, а не *& для изменений
    /*ФУНКЦИЯ УДАЛЕНИЯ СТЕКА ИЗ ПАМЯТИ*/
    void ClearList(List *MyList)

    • Я так делал, чтобы не повредить внешний для функции указатель. Ни к чему его изменять, незачем его смещать.

      Почистить память можно и внутренним обходительством.

  22. апвпв:

    До чего уродливое оформление! Автору кол в сердце!

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/nikolay-poleschuk/programmirovanie-dlya-autocad-2013-2015/?lfrom=15589587
Яндекс.Метрика