0

わかりました。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) をポップしたように見えるので、アンチアンダーフロー ポップ/ピークを記述する方法はありますか参照で何かを渡す必要はありませんか？

4

1 に答える 1

2

仕様の問題です。考えられる解決策はいくつかあります。

  • popスタックが空でないことを前提条件にします。これを保証するのはクライアントの責任であり (おそらく pop する is_empty()前に呼び出すことによって)、前提条件に違反するとアサーションの失敗が発生します。

  • スタックが空の場合、例外をスローします。これは最も明白な解決策ですが、おそらく最も一般的ではない解決策です。

  • pop値を返さないでください(または、あなたの を返させてくださいbool)。最上位の要素を取得するには、別の関数 があり、tos()両方を実行したいクライアントには 2 つの関数呼び出しが必要ですx = s.tos(); s.pop();。たとえば、これは標準が行うことです。実際には、コピーがスローされる可能性のある型 ( など std::string) の場合、 pop を実装して値を返し、強力な例外保証を与えることは不可能であるため、多くの場合、これが推奨される方法です。(これが問題であるかどうかは別の問題ですが、特定のケースでは問題になる可能性があり、ポップ関数のいずれも値を返さない標準での選択の背後にある動機です。)

最終的に重要なことは、ユーザーが何を期待するかを理解できるように、インターフェースを定義することです。

ifちなみに、 inは必要ありませんadd_to_head。の場合head == NULL、2 番目の引数 でコンストラクターを呼び出す ので、どちらの場合でもNULL渡すだけでかまいません。head

(リンクされたリストを使用することは、スタックを実装する方法としては非常に非効率的であるという事実はスキップします。コードは明らかに学習課題であるためです。)

于 2012-11-05T20:03:20.553 に答える