Хорошо, я пытаюсь написать метод pop в стеке, используя связанные списки для моей домашней работы на C ++.
Позвольте мне сначала показать вам класс узлов и список, а затем рассказать о проблеме:
class Node
{
public:
int data;
Node* next;
Node(int data, Node* next = 0)
{
this->data = data;
this->next = next;
}
};
class List
{
private:
Node* head; // no need for the tail when using the list for implementing a stack
public:
List()
{
head = 0;
}
void add_to_head(int data)
{
if(head == 0)
{
head = new Node(data);
}
else
{
head = new Node(data, head);
}
}
Node* get_head()
{
return head;
}
// this deletes the head element and makes 'head' points to the node after it.
void delete_head()
{
// storing the head so that we could delete it afterwards.
Node* temp = head;
// making the head point to the next element.
head = temp->next;
// freeing memory from the deleted head.
delete(temp);
}
};
Теперь вот стек:
class stack
{
private:
List* list;
public:
stack()
{
list = new List();
flush();
}
void push(int value)
{
list->add_to_head(value);
}
bool pop(int& value_to_fill)
{
if(is_empty())
{
return false; // underflow...
}
value_to_fill = list->get_head()->data;
// deleting the head. NOTE that head will automatically point to the next element after deletion
// (check out the delete_head definition)
list->delete_head();
return true; // popping succeed.
}
bool peek(int& value_to_fill)
{
if(is_empty())
{
return false;
}
value_to_fill = list->get_head()->data;
return true;
}
// other stuff...
};
Теперь проблема в поп-музыке, я просто не нахожу их удобными.
pop и peek не нужно давать никаких параметров, но если я сделаю это:
int peek()
{
if(is_empty())
// what should I do here?
return list->get_head()->data;
}
int pop()
{
if(is_empty())
// same thing here.
// deleting the tos then returning it.
// I know this is not what the pop in the STL stack does, but I like it this way
int tos = list->get_head()->data;
list->delete_head();
return tos;
}
Я не знаю, что делать, когда происходит переполнение.
Я не могу просто вернуть -1 или 0 или что-то в этом роде, потому что это будет выглядеть так, как будто я выскочил -1 или 0 (tos == -1 или 0)
Есть ли способ написания всплывающих окон / антипотоков без необходимости передавать что-либо по ссылке?
Это вопрос спецификации. Есть несколько возможных решений:
Сделайте это предварительным условием pop
что стек не пуст. это
ответственность клиента за это (возможно, позвонив по телефону
is_empty()
до появления) и нарушение предусловия
приводит к ошибке подтверждения.
Бросьте исключение, если стек пуст. Это самое очевидное
решение, но, вероятно, наименее общеприменимо.
Не иметь pop
вернуть значение (или сделать это вернуть ваш bool
). к
получить верхний элемент, у вас есть отдельная функция, tos()
и клиент
кто хочет сделать оба, нуждается в двух вызовах функций: x = s.tos(); s.pop();
,
Это то, что стандарт делает, например. На практике это часто
предпочтительный метод, потому что для типов, где копирование может бросить (например,
std::string
), невозможно реализовать pop для возврата значения и
дать сильное исключение гарантии. (Является ли это проблемой или нет
это еще одна проблема, но это может быть проблемой в конкретных случаях, и это
мотивация выбора в стандарте, где ни один из поп
функции возвращают значение.)
В конце концов, важно, чтобы вы определили интерфейс, поэтому
что ваш пользователь знает, чего ожидать.
И, кстати, вам не нужно if
в add_to_head
, Если head ==
, вы собираетесь вызвать конструктор со вторым аргументом
NULL
NULL
так что вы могли бы просто пройти head
в обоих случаях.
(Я пропущу тот факт, что использование связанного списка является удивительно неэффективным
способ реализовать стек, так как код, очевидно, является обучением
упражнение.)
Других решений пока нет …