Форум программистов, компьютерный форум CyberForum.ru

Стек и произвольный доступ - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
27.04.2011, 04:08     Стек и произвольный доступ #1
dederkay, то что вы делается сложно назвать стеком. Это больше похоже на список. Точнее это и есть список. Одним из главных свойств стека является то что элементы расположенных в памяти непосредственно друг за другом.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2011, 04:08     Стек и произвольный доступ
Посмотрите здесь:

C++ при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"?
C++ Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
Структура стек (: добавить элемент в стек, удалить элемент из стека, получить значение с вершины стека, размер стека...) C++
C++ Произвольный доступ к строкам
C++ Произвольный тип
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.04.2011, 04:51     Стек и произвольный доступ #2
Цитата Сообщение от dederkay Посмотреть сообщение
<тип> operator [] (int i)
Это у массивов, должно искать i-тый элмент и возвращать на него ссылку, а у тебя стек, к нему запрешён произвольный доступ по индексу.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
27.04.2011, 11:39     Стек и произвольный доступ #3
Цитата Сообщение от Overmind024 Посмотреть сообщение
Одним из главных свойств стека является то что элементы расположенных в памяти непосредственно друг за другом.
Нет. Расположение в памяти не имеет никакого значения.
fasked
27.04.2011, 11:41
  #4

Не по теме:

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

Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
27.04.2011, 22:31  [ТС]     Стек и произвольный доступ #5
Ну тогда чем же этот стек отличается от списка?? Названием методов(не add, а push)???
И я не разу не встречал стек не похожий на массив. Откуда же тогда взялось понятие переполнение стека(оперативная память что ли закончилась)??
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
27.04.2011, 22:41     Стек и произвольный доступ #6
Overmind024, стек - это структура данных, никакого отношения ни к памяти, ни к аппаратным или программным реализациям не имеющая. Она не знает, что такое память, что она может закончится и т.д. Как, впрочем, и список. Фишка стека в том, что он не имеет произвольного доступа к элементам. Как заталкивать в него элементы, так и доставать их из него можно только с одного конца. Всё, на этом особенности стека заканчиваются. Как реализуете его вы - массивом, списком или ещё как - это чисто ваш выбор. Единственное требование - должны сохраняться свойства стека, иначе стеком ваша писанина называться не будет (преподы любят давать задания типа "реализовать стек, переопределить операцию доступа по индексу". Слава Богу, у меня подобные личности предметов не вели).
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
27.04.2011, 23:52     Стек и произвольный доступ #7
silent_1991, а где это определено, что стек ни при каких обстоятельствах не может иметь произвольный доступ?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.04.2011, 00:22     Стек и произвольный доступ #8
Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
28.04.2011, 01:54     Стек и произвольный доступ #9
Это мне известно, но всетаки что мешает сделать произвольный доступ? И как тогда именовать системный стек?
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
28.04.2011, 02:05     Стек и произвольный доступ #10
Цитата Сообщение от kazak Посмотреть сообщение
Это мне известно, но всетаки что мешает сделать произвольный доступ? И как тогда именовать системный стек?
Простите, Вы шутите? Вы серьезно не знаете, что такое стек? Может мне опять картинки начать рисовать?
Какой еще произвольный доступ в стеке? Произвольный доступ предполагает, что можно обратиться к любому элементу за время O(1), то есть константа, постоянное время. В стеке же вообще обратиться можно только к одному элементу, и здесь уже не важно как устроен стек: node- или array-based или еще что-нибудь. Главное что доступ есть только к одному элементу. В стеке нельзя осуществлять поиск элемента, вставку в середину... иначе это уже не стек...
Где логика и смысл Ваших высказываний?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.04.2011, 02:11     Стек и произвольный доступ #11
kazak, на некотором уровне абстракции стек - структура данных, которая позволяет складывать элементы на стек, и снимать их с его верхушки (за один раз - один элемент). Тут просто не может быть других вариантов. Просто напросто структура данных с возможностью складывать элементы и снимать их с верхушки, но ещё и с произвольным доступом, стеком являться не будет. И даром, что лифо там тоже есть.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
28.04.2011, 05:57     Стек и произвольный доступ #12
Цитата Сообщение от fasked Посмотреть сообщение
Произвольный доступ предполагает, что можно обратиться к любому элементу за время O(1), то есть константа, постоянное время
Ничего подобного. Произвольный доступ предполагает доступ к элементу по его индексу. Всё, точка.

Цитата Сообщение от kazak Посмотреть сообщение
но всетаки что мешает сделать произвольный доступ?
Повторяю, ЭТО называется Вектор.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.04.2011, 09:24     Стек и произвольный доступ #13
Цитата Сообщение от Deviaphan Посмотреть сообщение
Произвольный доступ предполагает доступ к элементу по его индексу.
А по-моему произвольный доступ предполагает доступ к любому элементу без необходимости разрушающего доступа к другим элементам. А по индексу или путём указания какой то иной уникальной для каждого элемента информации - вопрос второстепенный. В реляционных БД для этого используется первичный ключ, в многомерных массивах - комбинация такого количества индексов, какова размерность массива. Да и иттераторы - не совсем индексы.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
28.04.2011, 10:47     Стек и произвольный доступ #14
Цитата Сообщение от taras atavin Посмотреть сообщение
А по индексу или путём указания какой то иной уникальной для каждого элемента информации - вопрос второстепенный.
Под словом "индекс" я подразумевал не переменную типа size_t, а как раз уникальный ключ. Одно это число или комбинация строк - не существенно.

Цитата Сообщение от taras atavin Посмотреть сообщение
В реляционных БД...
БД и контейнер это немного разные сущности.

Цитата Сообщение от taras atavin Посмотреть сообщение
Да и иттераторы - не совсем индексы
Итераторы - совсем не индексы. По определению. Они предназначены для последовательного обхода контейнера. Ничего общего с произвольным доступом итераторы не имеют.

Цитата Сообщение от taras atavin Посмотреть сообщение
по-моему произвольный доступ предполагает доступ к любому элементу без необходимости разрушающего доступа к другим элементам.
Нет. Доступ к элементам списка так же не вызывает разрушения других элементов списка, но ничего общего с произвольным доступом не имеет.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
28.04.2011, 11:06     Стек и произвольный доступ #15
Цитата Сообщение от Deviaphan Посмотреть сообщение
Ничего подобного. Произвольный доступ предполагает доступ к элементу по его индексу. Всё, точка.
Я могу в собственном классе связного списка завести переменную типа size_t и перегрузить operator[], но от этого random access в данной структуре не появится. То есть я конечно понимаю, что Вы хотите сказать (надеюсь, что понимаю). Но формулировка с индексом ой как не точна.
Цитата Сообщение от taras atavin Посмотреть сообщение
А по-моему произвольный доступ предполагает доступ к любому элементу без необходимости разрушающего доступа к другим элементам. А по индексу или путём указания какой то иной уникальной для каждого элемента информации - вопрос второстепенный. В реляционных БД для этого используется первичный ключ, в многомерных массивах - комбинация такого количества индексов, какова размерность массива. Да и иттераторы - не совсем индексы.
А здесь вообще полный бред написан. Итераторы - это совсем не индексы, это уж скорее указатели, чем индексы Деструктивное воздействие? Вы бы хотя бы википедию открыли прежде, чем начинать спорить..

Ужас какой-то
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
28.04.2011, 11:14     Стек и произвольный доступ #16
Цитата Сообщение от fasked Посмотреть сообщение
Произвольный доступ предполагает доступ к элементу по его индексу.
*за постоянное время
.)
fasked
28.04.2011, 11:16
  #17

Не по теме:

Цитата Сообщение от Deviaphan Посмотреть сообщение
за постоянное время
О чем я и сказал

Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
28.04.2011, 11:26     Стек и произвольный доступ #18
Цитата Сообщение от fasked Посмотреть сообщение
О чем я и сказал
Да-да, я помню. Это я как бы делаю вид, что я не тупил, а прям сразу согласен и был.)
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.04.2011, 11:29     Стек и произвольный доступ #19
Цитата Сообщение от Deviaphan Посмотреть сообщение
БД и контейнер это немного разные сущности.
Да, но понятие доступа от этого не зависит.

Добавлено через 50 секунд
Цитата Сообщение от Deviaphan Посмотреть сообщение
Итераторы - совсем не индексы. По определению. Они предназначены для последовательного обхода контейнера. Ничего общего с произвольным доступом итераторы не имеют.
Да, действительно бред сморозил.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2011, 13:05     Стек и произвольный доступ
Еще ссылки по теме:

Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? C++
Дан произвольный текст C++
Вывести на экран произвольный пятиугольник C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
28.04.2011, 13:05     Стек и произвольный доступ #20
Цитата Сообщение от silent_1991 Посмотреть сообщение
на некотором уровне абстракции
беда в том, что вы эти абстракции воспринимаете чересчур буквально, идеализированно.
Возьмем системный стек, с которым работает процессор. Процессор использует две команды для работы со стеком: push/pop - поместить в стек/вытолкнуть из стека. Поиска как такового нет, вставить в середину стека тоже нельзя, как и удалить из середины. Вроде как все по определению, но при работе со стеком используются два указателя: регистр ESP (текущая вершина стека) с которым непосредственно работают push/pop и регистр EBP (так называемый указатель кадра стека), который используется в частности для обращения к аргументам и локальным переменным вызываемых функций, причем эти переменные могут находится довольно далеко от текущей вершины стека. Т.е. фактически имеем стек с возможностью произвольного доступа, но даже с этой возможностью вся эта "система" остается "стеком" в том числе и в понятии вашего уровня абстракции.

Цитата Сообщение от fasked Посмотреть сообщение
Вы бы хотя бы википедию открыли
википедия конечно довольно познавательный ресурс, но на роль "авторитетного источника" не тянет.
Yandex
Объявления
28.04.2011, 13:05     Стек и произвольный доступ
Ответ Создать тему
Опции темы

Текущее время: 13:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru