[aina]

Помогите пожалуйста написать класс стек на с++, реализующий следующие возможности: добавить элемент в конец стека, извлечь последний элемент стека, проверка на то ,что стек не пуст.

[El Scorpio]

Контрольная в школе?

Код:

class cStack
{
   struct sItem // структура элемента
      {
          int Value; // значение
          sItem *Prev; // указатель на предыдущий элемент
      }

   sItem *fItem; // рабочее поле
}

Вот классическая основа для стека.
Метод Push создаёт в куче новый объект для указателя fItem, адрес старого объекта помещается в поле Prev.
Метот Pop извлекает из поля Prev адрес предыдущего объекта и удаляет текущий.
Метод IsEmpty проверяет, не равен ли указатель fItem нулевому адресу

[Nikilania]

El Scorpio, спасибо, не очень помогло, по крайней мере мне Пока разбиралась написала нечто следующее:
class AStack
{
public:
struct sItem
{
string Value;
sItem *Prev;
};

sItem *fItem;

// konstruktor
AStack()
{
fItem = new sItem;
fItem = NULL;
}

// destruktor
~AStack() {};

// dobavlenie
void Push(string v)
{
sItem *tmp = new sItem;

tmp->Value = v;
if(!fItem)
fItem = tmp;
else
{
tmp->Prev = fItem;
fItem = tmp;
}
}

// udalenie
AStack Pop()
{
sItem *s = new sItem;
if (fItem == NULL) {cout<<"Error: stek pust" << endl;}
else
{
cout << fItem->Value.c_str() << endl;
fItem = fItem->Prev;
}
AStack P;
P.fItem = fItem;

return P;
};
}

Функцию определения пустоты стека не писала - в задании такого не было (в моем)

[El Scorpio]

эээ

AStack() { fItem = new sItem; fItem = NULL; } »

Сначала создаём объект типа sItem, а потом обнуляем указатель на него?

// destruktor ~AStack() {}; »

То есть, при удалении стека его элементы из памяти удаляться не будут?

Остальных жуков просто лень перечислять

[pva]

Я бы сделал через вектор (потом бы долго спорил с преподом что использовать свободную память в задании не было):

Код:

00 <-- Указатель на начало bptr (begin)
01
02        <- при извлечении смещаем обратно
03 <-- Указатель на конец gptr (get)
04        <- при запоминании смещаем вперёд
05
06
   <-- Конец памяти (максимальная длина стека) eptr (end)

Таким образом нужно:

• Выделить кусочек памяти, достаточный чтобы поместить максимальное кол-во элементов
• Заталкивание в стек: *bptr++ = value;
• Возврат из стека: return *--bptr;

Ну и не забываем проверять границы: bptr <= gptr < eptr
Тов. программисты форума, у меня в браузере глючит перенос строчки, когда заполнишь окошко ввода ответа (удаляет перенос строки или проворачивает прокрутку обратно), IE8

[Nikilania]

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

[El Scorpio]

Nikilania, повторяю мысль - объект, в тексте которого содержится много new и ни одного delete выглядит странно
Хотя бы деструктор должен иметь код удаления объектов

Код:

AStack (void)
{
    sItem *temp;
    while ((temp = fitem) != NULL)
    {
        fitem = temp->prev;
        delete temp;
    }

}

Кроме того, delete должно вызываться и при вызове Pop

[pva]

Nikilania, я так понимаю про учебник - это в мой огород камень, по этому поводу хочу пояснить:

• Не знаю, из какого это учебника, такой принцип используется в стеке вызовов (инструкция CALL) процессора. Каюсь, названия для указателей взял общепринятые (для понятности)
• Я не указываю как делать, а лишь предлагаю рассмотреть альтернативный способ тем, кто читает эту тему, но ещё не реализовал свой алгоритм. Это не ограничивает функциональность вашего алгоритма.

Вообще есть такие варианты реализации контейнеров:

• Вектор, элементы хранятся в одной группе (требует цельный кусок памяти, но работает быстрее всех)
• Двусвязный список, элементы связаны указателями (частое обращение к диспетчеру памяти, но экономит память)
• Дека (deque) гибрид первого и второго, элементы в небольших группах, группы в 2-связных списках (сбалансированный, но сложнее код)

Ваша реализация, Nikilania - это 2-связный список который тоже есть в известных учебниках