На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Кое-что непонятно по структуре СТЕК , АТД: стек
    Всем хай! Сходу к делу!
    Перечитав с 10-ок статей по стеку (и некоторые книги) начинаю сомневаться, что основательно понимаю эту АТД. Моя задача на глубочайшем уровне понять принцип работы стека, хотя это простейшая структура и кодил ее раз 200, наверное.
    top - указатель на вершину стека (глобальная переменная, как пример), стек целых чисел, примеры кода будет на чистом СИ.
    Реализация на динамическом списке (не статик и не динамик массив).

    ExpandedWrap disabled
      struct TElem
      {
        int value;
        struct TElem* next;
      };


    1-я проблема: разные источники называют РАЗНЫЕ БАЗОВЫЕ ОПЕРАЦИИ над стеком. 100%, что нужна операция push (добавление элемента на вершину стека) и pop (удаление элемента из вершины стека). Дальше начинаются разночтения. Где-то говорится об операции peek (получение значения верхнего элемента стека без удаления самого элемента), empty (проверка стека на пустоту), print(печать элементов стека). На мой взгляд, это наиважнейший момент в понимании стека - нужно определить БАЗОВЫЕ ОПЕРАЦИИ, т к любые производные операции должны основываться на базовых. Вот какие операции допустимы над классическим стеком?? push, pop, peek? и ВСЕ?? НИЧЕГО ДРУГОГО НЕЛЬЗЯ ни при каких условиях??

    ExpandedWrap disabled
      // добавление элемента в вершину стека
      void push(int pvalue)
      {
        struct TElem* add = <вызывается функция создания элемента>;
        add->next = top;
        top = add;
      }


    ExpandedWrap disabled
      // удаление элемента из вершины стека
      void pop(void)
      {
        struct TElem* del = top;
        top = del->next;
        free(del);
      }


    ExpandedWrap disabled
      // получение значения верхнего элемента стека
      int peek(void)
      {
        return (top->value);
      }


    понятно, что функции peek, pop вызываются только тогда, когда в стеке есть хотя бы 1 элемент, т е перед вызовом придется делать проверку аля
    ExpandedWrap disabled
      if(top != NULL)
    , иначе крах прожки в процессе работы.

    2-я проблема: допустим, очень часто "просят" вывести все элементы стека на экран. Раньше я делал так:
    ExpandedWrap disabled
      void print(void)
      {
        struct TElem* print = top;
        printf("Элементы стека: ");
        while(print != NULL)
        {
          printf("\t%d", print->value);
          print = print->next;
        }
      }


    но ведь так делать нельзя, т к изначально СТЕК не позволяет операцию движения вдоль стека. Стек говорит, ты можешь печатать, что хочешь, но использовать можешь лишь набор базовых операций: push, pop, peek(?).
    Означает ли это, что такая функция print недопустима? Придется делать так:
    1. взяли peek, запомнили в переменную и вывели на экран
    2. вызываем push, куда добавляется элемент во вспомогательный стек. На самом деле push должен иметь параметром указатель на начало стека, чтобы можно быдо добавлять в разные стеки.
    3. вызываем pop из первоначального стека.
    и в цикле крутим эти 3 операции, пока первоначальный стек не будет удален ПОЛНОСТЬЮ. при этом рядом образуется вспомогательный перевернутый стек. Потом нужно сделать обратный переворот вспомогательного стека (уже без печати элементов), чтобы восстановить первоначальный. Все это геморрно, но зато это полностью соот-ет базовым операциям стека.

    Или, допустим, потребуется удалить лишь четные элементы из стека. Базовой операции такой не предусмотрено, поэтому, если и пытаться ее реализовывать, то только, используя базовые. Ведь так, да?

    3-я проблема: я правильно понимаю, что стек нужно применять лишь в тех алгоритмах, которые будут использовать стек по классическому назначению? Например, я помню, что в некоторых графовых алгоритмах задействуют стек/очередь, при этом не требуют никаких переворотов, печатей всех элементов, а используют лишь push, pop, peek и НИ КОПЕЙКИ БОЛЬШЕ! Если, при решении какой-либо задачи, требуется обработка стековых данных таким образом, что добавляет новые операции над стеком, то в этом случае от этой структуры СТЕК нужно отказываться и использовать линейный список (хотя в каком роде стек частный обрезанный случай ЛОС), например??

    Вообще, чем больше это все изучаю, тем больше понимаю, что тонкостей миллион. Не нужно мне писать про природу данных, которые хранятся в стеке. ЧТо разные данные требуют различной обработки. Это понятно, меня интересует стек как контейнер для ОДНОЗНАЧНОЙ обработки ЛЮБЫХ данных (абстрактность в этом ведь проявляется)

    подскажите как быть-то? спс за внимание!
      Базовых операций всего три - push, pop, isempty.
      Получение (элемента с вершины, всего стека для печати и пр.) не являются базовыми, ибо они легко реализуются последовательностью из нескольких базовых операций. Ну и плюс использование внешних для стека массива/коллекции/ещё чего-нить, что вообще к делу не относится.
      Сообщение отредактировано: Akina -
        Цитата FasterHarder @
        то в этом случае от этой структуры СТЕК нужно отказываться и использовать линейный список

        Линейный список вообще редко когда нужен.
          Цитата Akina @
          Базовых операций всего три - push, pop, isempty.

          допустим, значит инфа из главной ссылки вики уже неточная, т к там написано, что: "Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)".

          Как видишь, нет ни слова про isempty. Нет, я не утверждаю, что ты не прав, ни в коем случае, а лишь то, что в вики уже не достоверная инфа относительно стека. Так получается, да? Кстати, в некоторых др.источниках (не таких авторитетных, как вики в области КОМПЬЮТЕР САЙНС), как раз за 3-ю базовую операцию брали isempty, а peek-а там не было.

          Допустим, всего 3 базовых операции: push, pop, isempty. Сразу договоримся, что pop удаляет и ВОЗВРАЩАЕТ ЗНАЧЕНИЕ УДАЛЕННОГО элемента (в примере кода выше у меня не так). А как тогда получить значение ВЕРХНЕГО ЭЛЕМЕНТА, через эти 3 базовые?? Придется удалять верхний элемент, при этом запомнив занчение, потом его распечатать и добавить обратно в стек? Т е последовательно вызываем pop, а затем push??

          Или все-таки достаточно прописать
          ExpandedWrap disabled
            (return top->value)
          ? Вот это тоже важнейший момент. Хочу понять, что при работе со стеком МОЖНО ТОЛЬКО ИСПОЛЬЗОВАТЬ БАЗОВЫЕ ОПЕРАЦИИ push, pop, isempty и ничего другого в принципе, т е ЛЮБАЯ производная операция должна состоять из комбинации базовых. В окружении при этом могут быть доп.переменные, указатели и пр, но, когда идет взаимодействие со стеком, то допустимы ТОЛЬКО базовые и все? или не так все-таки?
            По-моему ты на каких-то мелочах концентрируешься.
              Цитата FasterHarder @
              значит инфа из главной ссылки вики уже неточная, т к там написано, что: "Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)".

              как тогда получить значение ВЕРХНЕГО ЭЛЕМЕНТА, через эти 3 базовые??


              ExpandedWrap disabled
                peek:
                    if not isempty
                        pop(var)
                        push(var)
                        return var
                    else
                        return NULL


              Цитата FasterHarder @
              там написано, что: "Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)".

              Ага-ага... ну-ка, реализуй через эти "базовые" операции проверку, что стек непуст. Обязательное условие - в процессе выполнения кода не должно возникнуть ошибки. Скрытое обязательное условие - состояние стека в принципе неизвестно, известно только, что он существует, и что он именно стек.

              Цитата FasterHarder @
              при работе со стеком МОЖНО ТОЛЬКО ИСПОЛЬЗОВАТЬ БАЗОВЫЕ ОПЕРАЦИИ push, pop, isempty и ничего другого в принципе, т е ЛЮБАЯ производная операция должна состоять из комбинации базовых. В окружении при этом могут быть доп.переменные, указатели и пр, но, когда идет взаимодействие со стеком, то допустимы ТОЛЬКО базовые и все?

              Именно так. Суть базовых операций в том, что ЛЮБАЯ мыслимая операция может быть выполнена с использованием ТОЛЬКО базовых операций.

              Цитата FasterHarder @
              в вики уже не достоверная инфа относительно стека.

              Ну ты прям америку открыл... да там сплошь и рядом такое написано, что хоть за голову хватайся. Никто ж за написанное там ни материальной, ни уголовной ответственности не несёт...
              Сообщение отредактировано: Akina -
                Цитата Akina @
                eek:
                if not isempty
                pop(var)
                push(var)
                return var
                else
                return NULL


                ну, я это и имел в виду, когда писал, что:
                Цитата FasterHarder @
                Придется удалять верхний элемент, при этом запомнив занчение, потом его распечатать и добавить обратно в стек? Т е последовательно вызываем pop, а затем push??


                в общем, ладно, спс Akina, но все равно, какая-то недосказанность в моем понимании по стеку есть в принципе)

                а насчет вики, ну, там ведь и норм.информация есть), т е, например, относительно того же стека, 95% вполне, а вот с базовыми операциями какая-то нестыковка, ну, ладно в общем...
                  Вики пишут такие же люди, как и присутствующие здесь. И авторы статьи не всегда досконально разбираются в вопросе. Причём бывают ситуации, когда разбирающийся специалист исправляет статью, а потом приходит модератор и правит всё обратно к неправильному виду.
                  У структуры данных как объекта есть базовые операции - их надо обязательно реализовывать, иначе с ней вообще работать нельзя будет. Для стека это выше названные push, pop, isempty.
                  И могут быть дополнительные - они просто повышают удобство работы или могут быть эффективнее, чем реализация того же функционала посредством основных операций. Это могут быть операции peek (другое название top - верхний элемент стека), size (число элементов в стеке), swap (переставляет два верхних элемента), peek(n) (выдаёт n-й элемент от вершины не меняя стека), pick(n) (вытаскивает n-й элемент, удаляя его из стека), roll(n) (циклически проворачивает n верхних элементов стека), и т.д. - дополнительных операций можно придумать столько, сколько придёт в голову. Для примера можно посмотреть список слов языка FORTH, предназначенных для работы со стеком.
                  Сообщение отредактировано: amk -
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script execution time: 0,0877 ]   [ 16 queries used ]   [ Generated: 19.03.24, 02:14 GMT ]