0 
int arrayQueue::takeAway() 
{
    char letter;
    if (empty())
    return -1;
    else {
    Data *p, info;
    if (top == NULL)
    {
            cout << "Error stack empty\n";
    } else {
        p = top;    //top is another Data struct instance
        info.value = p->value;  
        top = p->next;
        delete p;
        return info.value;
    }
}
}

For my data structures course we are creating a queue using pointers and linked lists, however I cannot figure out how to point to the FIRST value. As the code is now, it points to the LAST value entered, which isn't useful in a queue setting. I searched for other examples, but I can only find examples that use more than one linked list. If anyone has any ideas it would be much appreciated!

edit: Here's how I am adding things to the queue

void arrayQueue::addToQueue(char x)  
    {
        if (full())
             cout << "Error, queue full \n";
         else {
             Data *p;
             p = new Data;
             p->value = x;
             p->next = top;
             top = p;
              }
    }

and this is my struct

struct Data
{
char value;
Data *next;
};
4

3 に答える 3

0

単一リンクリストをより多くのスタックとして実装したようです (つまり、FILO、先入れ後出し)。キューは FIFO (先入れ先出し) 構造です。これを行うには、head 要素にポインターを追加して (末尾のポインターに加えて)、単一リンク リストを実際にリンク リストにする必要があります (つまり、どちらの端からでも項目をポップできます)。すでに持っている）、二重リンクリストの実装を使用するか、リストを反復処理してポップする必要があるアイテム（たとえば、テールと呼んでいるもの）に到達するときに、以前のポインターをメモリに保持します。

ヘッド ポインターを追加すると、定数時間 ( O(1)) で項目をポップすることができますが、実装を双方向リンク リスト (ヘッド ポインターなし) に変更するには線形時間 ( O(n)) が必要です。以前のポインターをメモリに保持することも、線形時間で行うことができます。

于 2013-10-29T20:14:57.983 に答える
0

単一リンク リストには、1) 末尾に要素を追加する方法と、2) 要素を先頭から削除する方法の 2 つが必要です。したがって、単一のリンク リスト クラスは 2 つのポインターをサポートする必要があります。1 つはリストの最初の要素へのポインターで、もう 1 つはリストの最後の要素へのポインターです。

于 2013-10-29T20:05:24.627 に答える