如何实现具有单链接列表的队列，使其ENQUEUE和DEQUEUE取O(1)？

Question

这是CLRS 3的一个练习

10.2-3通过单链列表L实现队列。ENQUEUE和DEQUEUE操作仍然需要O(1)时间。

使用单链接列表实现队列并不难。我的问题是时间的复杂性。如何实现采用O(1)的ENQUEUE和DEQUEQUE？

我在google上发现的，就像使用指针来跟踪头尾一样。现在的问题是，如何使用O(1)时间跟踪单链列表上的头尾？跟踪尾部需要O(n)。我说的对吗？

Answer 1

管理头尾指针需要O(1)时间。

进入队列：

tail -> next = newNode;
newNode -> next = NULL;
tail = newNode;

Dequeue：

output_node = head;
head = head -> next;
// do whatever with output_node;

注意:在执行指针赋值之前，您还必须执行边界检查和内存分配/去分配。

Answer 2

它是简单的，简单地在结尾和deque在前面，和设置2指针(或unique_ptrs)指向结束和前面，这就可以了。就像这样：

struct queue{
    Node *head;
    Node *tail;
    int node_cnt; // well, you can put this in if you like
};

Node *enque(Node *head, int data)
{
    Node *p = new Node(Node data);
    if (head)
    {
        head->next = p;
        head = p;
    }
    else
        head = p;
    ++ q.node_cnt;
    return head;
}

int deque(Node *tail)
{
    Node *p = tail;
    int x = tail->data;
    tail = tail.next();
    delete p;
    -- q.node_cnt;
    return x;
}

上面只是一个演示代码，但是您可以看到，您不需要遍历整个列表来进行enque或deque。

Answer 3

如果允许使用std::list容器，则需要使用std。

如果没有(我假设是这样的)，尝试回答以下问题:为什么需要执行n个操作？你能把指向终点的指针存起来吗？

比方说，您有一个单独链接的列表和一个指针( head和tail )--列表项有next指针。

• 如果将一个新项排队，只需添加一个新项，修改前一个“第一个”项的next指针，并将head指针重新指向新项。这是3个操作= O(1)
• 如果将一个项排出队列，则将last指针移动到上一项的next pointer‘所指向的指针，并删除项-2操作= O(1)