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

@gromo · Регистрация: 04.09.2009

Студворк — интернет-сервис помощи студентам

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

Элементы стека хранятся в векторе _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. Любое число будет всегда больше, чем разность этого числа с единицей.

СПАСИБО!

@CheshireCat · 09.11.2009, 21:48

Не будет.
iStack::size() и _stack.size() - почувствуй разницу!

@gromo · 10.11.2009, 16:15 **[ТС]**

CheshireCat, извини, но что-то разницы я не чувствую...
Можно конкретнее?
Просто я ещё новичок!

Добавлено через 42 минуты
Подожди... Ты имеешь ввиду, что значение _top возвращает функция size() из класса iStack, а _stack.size() это функция size() из класса <vector> ? В этом заключается разница?

@CheshireCat · 10.11.2009, 23:24

Ну, не видя реализации (или хотя бы объявления) члена _stack, трудно сказать.... Но, скорее всего, так и есть. Важно то, что это две разных функции size().

@gromo · 11.11.2009, 16:28 **[ТС]**

CheshireCat,
Определение члена _stack:

C++
1
vector<int> _stack;

Но здесь же нужно сравнить _top со _stack.size(), а не со _stack.size()-1. По-моему здесь ошибка, вычитать единицу не нужно. Так ведь?

@CheshireCat · 11.11.2009, 21:39

Нет, не так. Как и всегда в C++, массивы индексируются с 0.
Поэтому, например, если _stack.size() == 10 (т.е. емкость стека - 10 элементов), то они будут иметь индексы: 0,1,2,3,4,5,6,7,8,9. Максимальный индекс элемента - 9, что соответствует 10-ти элементам в стеке.

@gromo · 12.11.2009, 19:28 **[ТС]**

CheshireCat,

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

Переменная _top содержит индекс первой
свободной ячейки стека. Этот индекс одновременно представляет количество
заполненных ячеек.

Если у нас, например, будет стек из 3 элементов, и _top будет равен _stack.size()-1 (т.е. двум), тогда третий элемент остается не заполненным. Ведь после того как _top был использован в качестве индекса в векторе (2 для третьего элемента) постфиксный инкремент увеличит его значение до 3. Сл-но стек будет полным, когда _top будет равен _stack.size(), а не _stack.size()-1.

@CheshireCat · 12.11.2009, 21:54

Гм, а где в твоем сообщении от 09.11.2009, 17:42 хоть полсловечка про постфиксный инкремент??? Телепаты все в отпуске, а код реализации этого стека ты не привел....

@gromo · 13.11.2009, 15:17 **[ТС]**

Ну да. Извини. Вот объявление:

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;}

@CheshireCat · 15.11.2009, 21:29

Тогда таки да, правильная версия функции full() должна выглядеть так:

C++
1
inline bool iStack::full() {return _top < _stack.size() ? false : true;}

@gromo · 16.11.2009, 22:45 **[ТС]**

CheshireCat, спасибо большое, что потратил на меня время, теперь я хоть уверен, что в книге опечатка. Спасибо!!!!!

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	09.11.2009, 21:48
	Не будет. iStack::size() и _stack.size() - почувствуй разницу! 1

@gromo 383 / 281 / 31 Регистрация: 04.09.2009 Сообщений: 1,225
	10.11.2009, 16:15 [ТС]
	CheshireCat, извини, но что-то разницы я не чувствую... Можно конкретнее? Просто я ещё новичок! Добавлено через 42 минуты Подожди... Ты имеешь ввиду, что значение _top возвращает функция size() из класса iStack, а _stack.size() это функция size() из класса <vector> ? В этом заключается разница? 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	10.11.2009, 23:24
	Ну, не видя реализации (или хотя бы объявления) члена _stack, трудно сказать.... Но, скорее всего, так и есть. Важно то, что это две разных функции size(). 1

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	11.11.2009, 21:39
	Нет, не так. Как и всегда в C++, массивы индексируются с 0. Поэтому, например, если _stack.size() == 10 (т.е. емкость стека - 10 элементов), то они будут иметь индексы: 0,1,2,3,4,5,6,7,8,9. Максимальный индекс элемента - 9, что соответствует 10-ти элементам в стеке. 1

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	12.11.2009, 21:54
	Гм, а где в твоем сообщении от 09.11.2009, 17:42 хоть полсловечка про постфиксный инкремент??? Телепаты все в отпуске, а код реализации этого стека ты не привел.... 1

@gromo 383 / 281 / 31 Регистрация: 04.09.2009 Сообщений: 1,225
	16.11.2009, 22:45 [ТС]
	CheshireCat, спасибо большое, что потратил на меня время, теперь я хоть уверен, что в книге опечатка. Спасибо!!!!! 0