Класс стек и очередь на с++

[aina]

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

[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-связный список который тоже есть в известных учебниках