382 / 280 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
1

Вопрос о стеке в С++

09.11.2009, 17:42. Показов 2270. Ответов 10
Метки нет (Все метки)

Всем привет!!
У меня тут вопрос про стек.
Цитата из книги:

Элементы стека хранятся в векторе _stack. Переменная _top содержит индекс первой
свободной ячейки стека. Этот индекс одновременно представляет количество
заполненных ячеек. Отсюда реализация функции size(): она должна просто возвращать
текущее значение _top.
inline int iStack::size() { return _top; };
empty() возвращает true, если _top равняется 0; full() возвращает true, если _top
равен _stack.size()-1 (напомним, что индексация вектора начинается с 0, поэтому мы должны вычесть 1).
inline bool iStack::full() {return _top < _stack.size()-1 ? false : true;}
Вектор здесь статический, может хранить только элементы типа int.

С функцией empty() всё понятно. А вот как понять реализацию функции full() ?
Она же будет постоянно возвращать true. Любое число будет всегда больше, чем разность этого числа с единицей.

СПАСИБО!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.11.2009, 17:42
Ответы с готовыми решениями:

Вопрос о стеке
На сколько я знаю, подпрограмма которая выполняется рекурсивно, кидает в стек копию своих...

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

Ошибка в стеке!
template&lt;typename T&gt; class Stack { private: struct Stek { T key; Stek* next; };

Thread на стеке
Всех приветствую! Не знаю сюда надо было писать или в WinAPI, ну в общем из названия темы...

10
Эксперт С++
2924 / 1273 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
09.11.2009, 21:48 2
Не будет.
iStack::size() и _stack.size() - почувствуй разницу!
1
382 / 280 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
10.11.2009, 16:15  [ТС] 3
CheshireCat, извини, но что-то разницы я не чувствую...
Можно конкретнее?
Просто я ещё новичок!


Добавлено через 42 минуты
Подожди... Ты имеешь ввиду, что значение _top возвращает функция size() из класса iStack, а _stack.size() это функция size() из класса <vector> ? В этом заключается разница?
0
Эксперт С++
2924 / 1273 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
10.11.2009, 23:24 4
Ну, не видя реализации (или хотя бы объявления) члена _stack, трудно сказать.... Но, скорее всего, так и есть. Важно то, что это две разных функции size().
1
382 / 280 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
11.11.2009, 16:28  [ТС] 5
CheshireCat,
Определение члена _stack:
C++
1
vector<int> _stack;
Но здесь же нужно сравнить _top со _stack.size(), а не со _stack.size()-1. По-моему здесь ошибка, вычитать единицу не нужно. Так ведь?
0
Эксперт С++
2924 / 1273 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
11.11.2009, 21:39 6
Нет, не так. Как и всегда в C++, массивы индексируются с 0.
Поэтому, например, если _stack.size() == 10 (т.е. емкость стека - 10 элементов), то они будут иметь индексы: 0,1,2,3,4,5,6,7,8,9. Максимальный индекс элемента - 9, что соответствует 10-ти элементам в стеке.
1
382 / 280 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
12.11.2009, 19:28  [ТС] 7
CheshireCat,
Цитата Сообщение от gromo Посмотреть сообщение
Переменная _top содержит индекс первой
свободной ячейки стека. Этот индекс одновременно представляет количество
заполненных ячеек.
Если у нас, например, будет стек из 3 элементов, и _top будет равен _stack.size()-1 (т.е. двум), тогда третий элемент остается не заполненным. Ведь после того как _top был использован в качестве индекса в векторе (2 для третьего элемента) постфиксный инкремент увеличит его значение до 3. Сл-но стек будет полным, когда _top будет равен _stack.size(), а не _stack.size()-1.
0
Эксперт С++
2924 / 1273 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
12.11.2009, 21:54 8
Гм, а где в твоем сообщении от 09.11.2009, 17:42 хоть полсловечка про постфиксный инкремент??? Телепаты все в отпуске, а код реализации этого стека ты не привел....
1
382 / 280 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
13.11.2009, 15:17  [ТС] 9
Ну да. Извини. Вот объявление:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>
class iStack {
    public:
        iStack( int capacity )
            : _stack( capacity ), _top(0){}
 
        bool pop( int &va1ue );
        bool push( int value );
        bool full();
        bool empty();
        void display();
        int size();
    private:
        int _top;
        vector< int > _stack;       
};
Добавлено через 12 минут
Что в первых двух строчках после спецификатора public: я точно не знаю. О такой конструкции в книге еще не говорилось. Это же, наверное, инициализация членов _stack и _top ?

Добавлено через 7 минут
А вот и реализация функций pop(), push() и full() :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool iStack::pop( int &top_va1ue ) {
    if ( empty() )
        return false;
    top_value = _stack[ --_top ];
    cout << "iStack::pop(): " << top_value << endl;
    return true;
}
 
//------------------------------------------------------------------------------
 
bool iStack::push( int value ) {
    cout << "iStack::push( " << value << " )\n";
    if ( full() )
        return false;
    _stack[ _top++ ] = value;
    return true;
}
 
//------------------------------------------------------------------------------
 
inline bool iStack::full() {return _top < _stack.size()-1 ? false : true;}
0
Эксперт С++
2924 / 1273 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
15.11.2009, 21:29 10
Тогда таки да, правильная версия функции full() должна выглядеть так:
C++
1
inline bool iStack::full() {return _top < _stack.size() ? false : true;}
1
382 / 280 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
16.11.2009, 22:45  [ТС] 11
CheshireCat, спасибо большое, что потратил на меня время, теперь я хоть уверен, что в книге опечатка. Спасибо!!!!!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.11.2009, 22:45
Помогаю со студенческими работами здесь

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

Структура в стеке
Я наверное уже всех задолбал со своим стеком, но всё же мне еще нужна помощь)) Код, который ниже...

Тройки чисел в стеке
Нужен код для такого задания: Создать стек из чисел, прочитав их из текстового файла....

Задача о LIFO стеке
Есть стек типа LIFO. Над ним произвели 10 операций push и 10 операций pop в произвольном порядке....


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru