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;
    }
}
}

对于我的数据结构课程，我们正在使用指针和链表创​​建一个队列，但是我不知道如何指向 FIRST 值。就像现在的代码一样，它指向输入的 LAST 值，这在队列设置中没有用。我搜索了其他示例，但我只能找到使用多个链表的示例。如果有人有任何想法，将不胜感激！

编辑：这是我将东西添加到队列中的方式

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;
              }
    }

这是我的结构

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

3 回答 3

3

您应该使用头和尾指针来实现您的链表。这允许在最后插入 -并在恒定时间 (O(1)) 内完成enqueue从前面的移除。dequeue这是一个简单的队列作为开始：


template
class Queue {
  public:
    class Node {
      T val;
      Node* next;

      Node(const T& v) : val(v), next(NULL) {}
    }

    Queue() : head(NULL), tail(NULL), sz(0) {}

    void enqueue(const T& v) {
      Node* n = new Node(v);
      if(sz == 0) {
        head = tail = n;
      }
      else {
        tail->next = n;
        tail = n;
      }
      sz++;
    }

    T dequeue() {
      if(sz == 0) throw SomeException;

      Node* tmp = head;
      head = head->next;
      T v = tmp->val;
      delete tmp;
      sz--;
      return v;
    }

    const T& front() const {return tail->val;}
    size_t size() const {return sz;}
    bool empty() {return sz == 0;}

  private:
    Node* head, tail;
    size_t sz;
}
于 2013-10-29T20:01:37.357 回答
0

听起来您已经将单链表实现为更多的堆栈（即，它是 FILO，先进后出）。队列是一个 FIFO（先进先出）结构。为此，您需要通过添加指向 head 元素的指针（除了您已经有），使用双向链表实现，或者在您遍历列表以获取需要弹出的项目时将先前的指针保留在内存中（例如，您称之为尾部）。

添加头指针将允许您在恒定时间内弹出项目（O(1)），而将您的实现更改为双向链表（没有头指针）将需要线性时间（O(n)）。将前一个指针保存在内存中也可以在线性时间内完成。

于 2013-10-29T20:14:57.983 回答
0

你的单链表应该有两种方法：1）在尾部添加一个元素，2）从头部删除一个元素。所以你的单个链表类应该支持两个指针：一个指向列表的第一个元素，另一个指向列表的最后一个元素。

于 2013-10-29T20:05:24.627 回答