Проблема с реализацией правильного (защищенного от переполнения) метода pop / peek в стеке с использованием списков избранного

Хорошо, я пытаюсь написать метод 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)
Есть ли способ написания всплывающих окон / антипотоков без необходимости передавать что-либо по ссылке?

0

Решение

Это вопрос спецификации. Есть несколько возможных решений:

  • Сделайте это предварительным условием pop что стек не пуст. это
    ответственность клиента за это (возможно, позвонив по телефону
    is_empty() до появления) и нарушение предусловия
    приводит к ошибке подтверждения.

  • Бросьте исключение, если стек пуст. Это самое очевидное
    решение, но, вероятно, наименее общеприменимо.

  • Не иметь pop вернуть значение (или сделать это вернуть ваш bool). к
    получить верхний элемент, у вас есть отдельная функция, tos()и клиент
    кто хочет сделать оба, нуждается в двух вызовах функций: x = s.tos(); s.pop();,
    Это то, что стандарт делает, например. На практике это часто
    предпочтительный метод, потому что для типов, где копирование может бросить (например,
    std::string), невозможно реализовать pop для возврата значения и
    дать сильное исключение гарантии. (Является ли это проблемой или нет
    это еще одна проблема, но это может быть проблемой в конкретных случаях, и это
    мотивация выбора в стандарте, где ни один из поп
    функции возвращают значение.)

В конце концов, важно, чтобы вы определили интерфейс, поэтому
что ваш пользователь знает, чего ожидать.

И, кстати, вам не нужно if в add_to_head, Если head ==
NULL
, вы собираетесь вызвать конструктор со вторым аргументом
NULLтак что вы могли бы просто пройти head в обоих случаях.

(Я пропущу тот факт, что использование связанного списка является удивительно неэффективным
способ реализовать стек, так как код, очевидно, является обучением
упражнение.)

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]