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

В этот раз я опишу создание стека.

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

Часто стек сравнивают с ящиком, в который например складывают кирпичи, часто со стопкой тарелок. Кроме проведения аналогий стек часто называют структурой LIFO, что обозначает последним пришел, первым ушел.

Наверное это может быть непонятно, поэтому поясню на цифрах.

  • Вводим: 1,2,3,4,5
  • На выходе 5,4,3,2,1

При этом голова у нас наша единица.
Стек

При каждом новом добавлении элемента в стек, мы должны запомнить адрес текущего элемента, после чего сместить голову и указателем указать на тот запомненный адрес. Ниже в коде этот указатель обозначен как Next (следующий). Но если смотреть человеческими глазами, то этот следующий элемент является предыдущим текущему. Если вы видите картинку, то видите, что голова стека уходит вправо. Компьютер будет читать справа налево, поэтому следующий элемент стека — это тот, что слева от головы.

Для стека определены следующие операции:

  • Проверка стека на пустоту
  • Добавление элемента в стек
  • Считывание головного элемента
  • Удаление головного элемента
  • Очистка стека

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

Я не буду разбивать код на этапы создания. Для создания стека (или динамического списка LIFO) будем использовать 4 функции (main, Добавить в список, Показать список, Удалить список из памяти)

Код C++ Создать Стек (или список LIFO)

Я смотрю на свой первоначальный код (LIFO Первое знакомство), там с классами и меня посещают мысли: «Неужели так сложно дать то, что так просто?» Я ведь много страниц тогда перерыл и не нашел этого.

Чтобы привести этот код к классическому пониманию стека, достаточно заменить мои temp -переменные на (*MyList) и тогда даже при простом просмотре просмотренные данные будут сразу теряться. Удаляться не будут, но связь потеряется. И если так сделаете, то будут паразитировать эти призраки стека и пожирать вашу память отныне и вовеки веков. При работе с динамическими данными надо быть очень внимательным к памяти и не нужно этого забывать.

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

Для стека можно выполнить и другие нетипичные для него операции, но кроме как для лучшего понимания материала это вряд ли стоит делать

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

==============================================================
Еще один пример стека

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

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

  • Аноним говорит:

    Малочик!

  • Qasta говорит:

    Спасибо!!!

  • Den4ik говорит:

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

  • Ксю и Даша говорит:

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

  • Аноним говорит:

    😳 🙂 👿 😛 ❓ 😛 🙁

  • Аноним говорит:

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

    Автор сайта отвечает:
    От перестановки мест слагаемых, сумма не изменяется. (Я написал, что означает, а не как переводится)
    В переводе действительно так звучит, но менять мне не обязательно.
    спасибо за комментарий.

    есть стек LIFO и еще есть стек FILO/ вот моими словами я назвал FILO, но в примере же LIFO (в этом вы правы)/ исправил

  • Andrey говорит:

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

  • вывыаа говорит:

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

  • Аноним говорит:

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

  • глупый анон говорит:

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

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

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

  • Аноним говорит:

    Здрааасьте)

  • Игорь говорит:

    Что означает stek *p=0;?
    int pop(stek* &next) принимает в качестве аргумента адрес переменной, которая указывает на структурную переменную?

    Автор сайта отвечает:
    1) stek *p=0; Инициализация указателя тем, что он показывает в ноль. (В Windows это вникуда)
    2) Передача параметра по ссылке, в результате чего работа с переменной идет напрямую. Без этого бы внутри функции создавалась локальная копия принимаемого аргумента. А так работа идет непосредственно с самим параметром, переданным в функцию. А этот параметр да, представляет собой переменную-указатель на начало структуры..

  • Игорь говорит:

    Спасибо за ответы)
    А можно так записать: stek *p=NULL;?

    Автор сайта отвечает:
    Да. Это правильнее выглядит. Так лучше для указателей писать, т.к. видно сразу, что это для указателя. И некоторых операционных системах ноль не равен NULL
    еще лучше nullptr (просто его раньше не было, в с++11 появился)

    )

  • Ann говорит:

    А что означают эти строки:

    и

    ?

    Автор сайта отвечает:
    Глупую корявость моего сайта. я исправил.

  • Александр говорит:

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

  • Андрей говорит:

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

    • admin говорит:

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

      • Андрей говорит:

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

        • admin говорит:

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

          • Андрей говорит:

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

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

            void func (int *arg);

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

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

            func (p_a);

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

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

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

            • admin говорит:

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

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

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

        • admin говорит:

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

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

  • Андрей говорит:

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

  • Алексей говорит:

    А подскажите как можно этот алгоритм заточить чтоб он выполнял арифметические действия записанный в инфиксной записи например +45++555

    Автор сайта отвечает:
    Не знаю

  • Freerider говорит:

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

  • Аноним говорит:

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

  • Дима говорит:

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

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

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

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

  • Дима говорит:

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

    • admin говорит:

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

  • Дима говорит:

    Если не трудно, объясните ещё — — почему на “Next” указывает указатель “temp”, а на ” Head ” указатель “MyList”? — потом указателю “Head” на который указывает ” MyList ” приравнивается значение указателя ” temp” ? в этом фрагменте

    Автор сайта отвечает:
    Я немного не понял.
    temp->Next не обозначает, что temp указывает на Next, это обозначает разыменовывание temp и обращение к Next из него. Другими словами это вот что:
    temp->Next === (*temp).Next
    А так как Next это сам по себе указатель, то мы в него и присваиваем указатель такого же типа как и он сам. В данном случае temp->Next=MyList->Head
    это можно было бы записать и как
    (*temp).Next=(*MyList).Head //Присваивание в указатель указателя.

  • Алексей говорит:

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

  • Дима говорит:

    Сорри, глючит чёт…..

    С присвоением указателей немного понял, не ясно другое, почему к Next обращение от temp, а к  Head обращение от  MyList? может я чё-то не то спрашиваю…….

     

    Автор сайта отвечает:
    Потому что MyList данные заполнены, а в temp что угодно, поэтому в части temp копируются известные данные. Копируются по кусочкам,
    temp->Next = MyList->Head; //Резервирую известные данные в temp.
    Мне трудно это объяснить. В общих чертах когда выделяется память под класс, то в этой памяти лежит что угодно (информационный мусор), я скопировал в поле этого класса известную часть. Теперь поле Next у класса temp не информационный мусор, а MyList->Head, а остальные поля у temp информационный мусор и их тоже надо заполнить из известных данных.
    Так как у стека сама по себе голова сдвигается немного в непривычном для нас виде (анимированную картинку же видели), то каждый раз голова — это последний элемент стека, она же начало. Поэтому в temp->Next сначала присваивается именно она. А она как раз и хранится в MyList->Head. Получается, что следующий элемент сейчас создаваемого звена стека будет указывать на последний существующий элемент стека, что и есть temp->Next=MyList->Head

  • Дима говорит:

    спасибо!

  • Богдан говорит:

    А если мне надо структуру в стек запихнуть, то как надо? Например мне нужно номер в списке, имя, сумму и процент депозита?

    Автор сайта отвечает:
    Вместо int x делать структуру.

  • ДМ говорит:

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

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

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

Ваш e-mail не будет опубликован.

Поиск

 
     

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

Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Отец перед сном рассказывает сыну сказку: - Жил на свете богатый человек. Купил он себе самый лучший компьютер и кучу лицензионных программ. - Пап, а как это - лицензионных? - Спи, сынок, я же сказал - это сказка! . .

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок