Определить класс стек

[eval]

если и ограничен, то особенностями среды выполнения

это максимум, грубо говоря, но никто не мешает его ограничивать так как этого требует логика.

про О(1)

поясните мне серому что такое о(1)

но когда я беру класс стека, я от него кое что ожидаю (я описал что я от него хочу). И именно этого от него ожидают те, кто знает что такое стек.

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

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

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

что же такое "сайз"?

size, типа ограничение на возможное макс. кол-во данных в стеке.

[Utkin]

size, типа ограничение на возможное макс. кол-во данных в стеке.

По-русски сказать размер нельзя? И если нет, то почему?

[rrrFer]

поясните мне серому что такое о(1)

не о(1), а О(1) - это разные понятия xD
Открой любую книжку по алгоритмам, ты обязательно встретишь там где-то в начале эти обозначения. О(1) означает, что время выполнения операции не зависит от размера твоего стека, в данном случае

это максимум, грубо говоря, но никто не мешает его ограничивать так как этого требует логика.

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

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

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

По-русски сказать размер нельзя? И если нет, то почему?

можно, я так и делаю )

[still_alive]

что это она самая быстрая?

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

к твоему массиву доступ/удаление - О(1), а вставка - О(1), НО ИНОГДА О(N) - это вообще не стек, т.е., оно не стабильно себя ведет и ненужно.

Мы живем не в идеальном мире. Если память будет перераспределяться раз в очень долгое время, то почему бы мне не увеличить скорость вставки и удаления в 99% случаев?

Я уже не говорю, что под твоими массивами памяти может быть выделено больше чем надо (но чем больше - тем реже ты получишь О(N) при вставке).

Между памятью и быстродействием почти всегда выбирают второе.

И еще раз, какой из этого профит? - я красным уже выделял. Массивы могут дать хорошее время произвольного доступа, но оно от стека не требуется. Что-то еще?

Не надо каждый раз выделять/освобождать память узла.

Если ты не заметил, still_alive, предлагает стек реализовывать на массивах

Я не предлагаю, я утверждаю, что такая возможность есть и может использоваться. В любом решении есть свои плюсы и минусы. Тот же STL позволяет сделать stack на векторе, списке или деке (он по умолчанию).

[eval]

По-русски сказать размер нельзя? И если нет, то почему?

переключать клаву иногда лениво а что, напрягает сильно?

если логика требует ограничить размер стека сверху - не используй стек - используй массив - это гораздо оптимальнее.

с какого перепуга? мне нужен именно стек, тобишь те самые поп и пуш, и все втикающее и вытекающее.

Стек, очередь, дек, ... имееет смысл применять только если объем данных заранее не известен. И не надо тут воду мутить.

не надо за всех говорить, ку? вот преподаватель тоже не того-же мнения.

и ты тоже предлагал именно это

игде? вы определенно, любитель за других додумать, чревато это

[rrrFer]

still_alive, более чем убедил, вот этим: "Не надо каждый раз выделять/освобождать память узла."
хотя...

Мы живем не в идеальном мире. Если память будет перераспределяться раз в очень долгое время, то почему бы мне не увеличить скорость вставки и удаления в 99% случаев?

может быть потому, что в 1% случаев память будет распределяться 99% времени? ))
Наверное поэтому, чтобы ваша программа в 1% случаев не вставала всерьез и надолго, по умолчанию в STL стек таки использует deque? )

eval

не надо за всех говорить, ку? вот преподаватель тоже не того-же мнения.

обоснуй. Ссылка на неизвестного преподавателя не канает, ку?
Т.е. я жду любой пример, когда использование стека будет лучше чем использование массива при условии, что количество элементов заранее известно.
Я могу придумать пример, но он из древности (и уже лет 20 не актуален).

И еще, я ж с 25 поста жду код, который решает все проблемы при помощи эксепшна или какой-то там проверки.

игде? вы определенно, любитель за других додумать, чревато это

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

Кстати, я внимательно прочитал цитату:

В некоторых языках(например, Lisp, Python[3]) стеком можно назвать любой список, так как для них доступны операции pop и push.

Бред какой-то. Причем тут "некоторые языки" и "лисп" в частности? - по определению "стек - это список". (по определению с вашей любимой вики, но still_alive таки пояснил нам, что так не всегда). А как там список устроен в лиспе ИМХО вообще нельзя быть уверенным, может быть он там на массивах? (а вдруг?) - а может быть, "иногда на массивах", мы же не знаем какое решение примет оптимизатор лиспопрограмм (а мы всегда на него надеемся).

[still_alive]

Сообщение от rrrFer

still_alive, более чем убедил, вот этим: "Не надо каждый раз выделять/освобождать память узла."
хотя...
может быть потому, что в 1% случаев память будет распределяться 99% времени? ))
Наверное поэтому, чтобы ваша программа в 1% случаев не вставала всерьез и надолго, по умолчанию в STL стек таки использует deque? )

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

Upd
Так сказать, дек - это компромиссное решение.
По сравнению с вектором - куда быстрее перераспределение, чуть медленнее вставка/удаление (за счет переходов между блоками и немногих дополнительных выделений памяти).
По сравнению со списком - больше памяти (если размером указателей в списке можно пренебречь), быстрее вставка/удаление, но часть памяти иногда перераспределяется.

[simples]

Сообщение от rrrFer

ты пнимаешь, что стек - это не массив. Какой смысл в него сайз передавать?

Передаю секретные данные. После прочтения - сжечь.

    public class Stack : ICollection, IEnumerable, ICloneable
    {
        private object[] _array;
        private const int _defaultCapacity = 10;

        public Stack()
        {
            this._array = new object[10];
            this._size = 0;
        }
        
        public Stack(int initialCapacity)
        {
            if (initialCapacity < 10)
            {
                initialCapacity = 10;
            }
            this._array = new object[initialCapacity];
            this._size = 0;
        }

это все выдержки из МС реализации стэка в НЕТ.

Сообщение от rrrFer

довай кодом, я не представляю как ты в массив будешь за О(1) элементы добавлять.

Гм... а с каких пор добавление нового элемента в массив - НЕ О(1) операция?
На примере того же кода от МС если не трудно объясните.

[Utkin]

переключать клаву иногда лениво а что, напрягает сильно?

Конечно, чтобы писать по-русски и далее писать слово "размер" нужно переключить регистр. Не просто напрягает - режет слух. Я понимаю когда имеется специфический термин, который сложно выразить на русском одним-двумя словами. Но размер-то чем не угодил?

[still_alive]

simples

Прочитал. Увы, сжечь майкрософт не могу. Хотя давно пора.
Во-первых, причем тут Net? Мне на него физически больно смотреть. Я тогда сейчас хаскелл запилю в тред.

Во-вторых, тут передается емкость, по умолчанию равная 10 (а почему 10, а не 9? или 8? или 666?) Емкость - это ни разу не максимальный размер стека и тем более не размер стека. Емкость - это сколько элементов может находиться в стеке при текущем объеме выделенной памяти.

В-третьих, добавление элемента в стек, когда массив уже заполнен, требует выделения нового куска памяти и копирования туда всех элементов - длительность этой операции зависит от кол-ва элементов в стеке.