Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3812438 Sat, 12 Oct 2019 21:10:01 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3812438 У структуры данных как объекта есть базовые операции - их надо обязательно реализовывать, иначе с ней вообще работать нельзя будет. Для стека это выше названные push, pop, isempty.
И могут быть дополнительные - они просто повышают удобство работы или могут быть эффективнее, чем реализация того же функционала посредством основных операций. Это могут быть операции peek (другое название top - верхний элемент стека), size (число элементов в стеке), swap (переставляет два верхних элемента), peek(n) (выдаёт n-й элемент от вершины не меняя стека), pick(n) (вытаскивает n-й элемент, удаляя его из стека), roll(n) (циклически проворачивает n верхних элементов стека), и т.д. - дополнительных операций можно придумать столько, сколько придёт в голову. Для примера можно посмотреть список слов языка FORTH, предназначенных для работы со стеком.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3812429 Sat, 12 Oct 2019 19:32:22 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3812429 Цитата Akina @
eek:
if not isempty
pop(var)
push(var)
return var
else
return NULL


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


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

а насчет вики, ну, там ведь и норм.информация есть), т е, например, относительно того же стека, 95% вполне, а вот с базовыми операциями какая-то нестыковка, ну, ладно в общем...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811868 Fri, 04 Oct 2019 12:22:05 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811868 Цитата FasterHarder @
значит инфа из главной ссылки вики уже неточная, т к там написано, что: "Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)".

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


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


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

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

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

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

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

Ну ты прям америку открыл... да там сплошь и рядом такое написано, что хоть за голову хватайся. Никто ж за написанное там ни материальной, ни уголовной ответственности не несёт...]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811865 Fri, 04 Oct 2019 11:42:42 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811865 OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811860 Fri, 04 Oct 2019 11:15:46 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811860 Цитата Akina @
Базовых операций всего три - push, pop, isempty.

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

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

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

Или все-таки достаточно прописать
    (return top->value)
? Вот это тоже важнейший момент. Хочу понять, что при работе со стеком МОЖНО ТОЛЬКО ИСПОЛЬЗОВАТЬ БАЗОВЫЕ ОПЕРАЦИИ push, pop, isempty и ничего другого в принципе, т е ЛЮБАЯ производная операция должна состоять из комбинации базовых. В окружении при этом могут быть доп.переменные, указатели и пр, но, когда идет взаимодействие со стеком, то допустимы ТОЛЬКО базовые и все? или не так все-таки?]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811853 Fri, 04 Oct 2019 09:53:21 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811853 Цитата FasterHarder @
то в этом случае от этой структуры СТЕК нужно отказываться и использовать линейный список

Линейный список вообще редко когда нужен.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811850 Fri, 04 Oct 2019 09:13:06 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811850 Получение (элемента с вершины, всего стека для печати и пр.) не являются базовыми, ибо они легко реализуются последовательностью из нескольких базовых операций. Ну и плюс использование внешних для стека массива/коллекции/ещё чего-нить, что вообще к делу не относится.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811832 Thu, 03 Oct 2019 23:25:16 +0000 Кое-что непонятно по структуре СТЕК https://forum.sources.ru/index.php?showtopic=415904&view=findpost&p=3811832 Перечитав с 10-ок статей по стеку (и некоторые книги) начинаю сомневаться, что основательно понимаю эту АТД. Моя задача на глубочайшем уровне понять принцип работы стека, хотя это простейшая структура и кодил ее раз 200, наверное.
top - указатель на вершину стека (глобальная переменная, как пример), стек целых чисел, примеры кода будет на чистом СИ.
Реализация на динамическом списке (не статик и не динамик массив).

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


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

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


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


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


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

2-я проблема: допустим, очень часто "просят" вывести все элементы стека на экран. Раньше я делал так:
    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 и НИ КОПЕЙКИ БОЛЬШЕ! Если, при решении какой-либо задачи, требуется обработка стековых данных таким образом, что добавляет новые операции над стеком, то в этом случае от этой структуры СТЕК нужно отказываться и использовать линейный список (хотя в каком роде стек частный обрезанный случай ЛОС), например??

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

подскажите как быть-то? спс за внимание!]]> FasterHarder Алгоритмы