链式队列.md

通过链表实现队列

问题描述

通过链表实现队列，包括push, pop, empty, size, front, back等函数

解决方案

算法代码如下：

class LinkQueue {
private:
    Node *head, *tail;
    int count;
public:
    LinkQueue() {
        head = tail = new Node;
        head->next = nullptr;
        count = 0;
    }

    void push(int data) {
        tail->next = new Node {data, nullptr};
        tail = tail->next;
        ++count;
    }

    void pop() {
        if (head->next != nullptr) {
            if (head->next == tail) {
                tail = head;
            }
            Node *tmp = head->next;
            head->next = head->next->next;
            delete tmp;
            --count;
        }
    }

    bool empty() const {
        return (head->next == nullptr);
    }

    int size() const {
        return count;
    }

    int& front() const {
        if (head->next == nullptr)
            throw "No data";
        return head->next->value;
    }

    int& back() const {
        if (head->next == nullptr)
            throw "No data";
        return tail->value;
    }
};

测试用例如下：

TEST(StackFifo, Class_Queue) {
    LinkQueue q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    EXPECT_EQ(1, q.front());
    EXPECT_EQ(4, q.back());
    EXPECT_EQ(4, q.size());
    EXPECT_FALSE(q.empty());

    q.pop();
    EXPECT_EQ(2, q.front());
    EXPECT_EQ(4, q.back());
    EXPECT_EQ(3, q.size());
    EXPECT_FALSE(q.empty());
    q.pop();
    q.pop();
    q.pop();
    q.pop();
    EXPECT_TRUE(q.empty());
    EXPECT_EQ(0, q.size());
    ASSERT_ANY_THROW(q.front());
    ASSERT_ANY_THROW(q.back());

    q.push(1);
    q.push(2);
    EXPECT_EQ(1, q.front());
    EXPECT_EQ(2, q.back());
    EXPECT_EQ(2, q.size());
    EXPECT_FALSE(q.empty());
}