数据结构——线性结构

程序员文章站 2022-03-24 17:26:56

...

线性结构区别于非线性结构，通常这种数据结构中的数据元素呈现一种线性关系。
主要包括数组、链表、栈和队列这四种。

数组

数组是一组有序定长的元素集合。
如int array[] = {0,1,2,3,4,5,6};
由于数组的元素在内存中的地址是连续的，因此它的特点是随机访问速度快。

多维数组

多维数组可以多下标表示类似平面甚至空间这种概念，其本质也是一维数组来实现。
如int array[2][3] = {1,2,3,4,5,6};

动态数组

数组长度通常是固定的，在元素个数未知或需要改变的时候，我们需要动态数组，即容量可以动态增长的数组。
C++中的STL提供了一种容器vector可以实现非定长的数组。

#include <vector>
using namespace std;

vector<int> vec;

声明了vector容器变量vec后，可以进行以下操作：
1、通过push_back()和pop_back()分别向容器中添加元素和删除元素；
2、通过empty()判断容器是否为空；
3、通过size()获取当前容器中实际元素个数；
4、通过capacity()获取为当前容器分配的大小；
5、通过max_size()返回容器可以容纳的最大元素个数；

看下面一段代码，判断容器是否为空，以及依次插入数据看max_size、size和capacity。

    if(vec.empty())
        cout<<"vec is empty"<<endl;
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;
    vec.push_back(1);
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;
    vec.push_back(2);
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;
    vec.push_back(3);
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;
    vec.push_back(4);
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;
    vec.push_back(5);
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;
    vec.push_back(6);
    cout<<vec.max_size()<<" "<<vec.size()<<" "<<vec.capacity()<<endl;

输出结果为：

vec is empty
1073741823 0 0
1073741823 1 1
1073741823 2 2
1073741823 3 4
1073741823 4 4
1073741823 5 8
1073741823 6 8

可见，容器是有一个固定的最大值max_size，为1073741823，只要不超过这个值，你可以随意添加元素。
size为当前容器元素个数，capacity为容器可容纳元素个数，不小于size。
其实，容器内部有一套内存分配的规律，当分配的内存不够而此时又有新元素插入，会发生重新分配（包括新内存的分配，原始内存的回收，对象拷贝析构等等）。（重新分配通常将当前容量翻倍）
考虑容器重新分配过程中性能下降问题，如果有大量插入操作，最好提前设定容量大小，避免多次扩容操作带来的效率低下。

6、通过reserve()改变当前容器所分配空间的大小，为其申请特定容量；

如我们要循环插入数据时，使用reserve可以避免重新分配。

vec.reserve(1000);

7、通过resize(n)强制修改容器元素个数；
若n小于size，尾部元素会被销毁；若n大于size，则填充默认元素；若n大于capacity，则加入元素前重新分配。

举一个例子：

    for(int i = 0; i < 5; i++)
        vec.push_back(i);
    cout<<"size = "<<vec.size()<<" capacity = "<<vec.capacity()<<endl;
    vec.resize(n);
    cout<<"size = "<<vec.size()<<" capacity = "<<vec.capacity()<<endl;
    vec.push_back(6);
    cout<<"size = "<<vec.size()<<" capacity = "<<vec.capacity()<<endl;

输出结果为：

// n = 3时
size = 5 capacity = 8
size = 3 capacity = 8
size = 4 capacity = 8

// n = 7时
size = 5 capacity = 8
size = 7 capacity = 8
size = 8 capacity = 8

// n = 10时
size = 5 capacity = 8
size = 10 capacity = 10
size = 11 capacity = 20

8、通过at(n)访问下标为n的元素，同数组的下标访问；

    for(int i = 0; i < vec.size(); i++)
        cout<<vec.at(i)<<" ";

这句话是依次输出容器的所有元素，同vec[i]。

9、通过begin()和end()返回容器起止元素的迭代器；
其中，begin()返回当前容器中起始位置的迭代器，end()返回当前容器中末尾位置的迭代器。
上面的依次输出可以写成这个样子：

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

10、通过front()和back()返回容器起止元素的引用；
区别于上面的begin()和end()，是指向元素的指针；front()和back()返回元素的引用，因此可以直接访问元素。
注意：通过迭代器访问最后一个元素，需将end()迭代器减一。
如输出首位元素：

    vector<int>::iterator begin = vec.begin();
    vector<int>::iterator end = vec.end();
    cout<<*begin<<" "<<*(end-1)<<endl;

    int front = vec.front();
    int back = vec.back();
    cout<<front<<" "<<back<<endl;

结果是一样的：

0 6
0 6

11、通过assign()向容器集体赋值；
assign(beg,end)会将[beg，end)前开后闭区间中的数据赋值给容器，assign(n,elem)则将n个elem的拷贝赋值给容器。
注意：元素会进行覆盖。
举例说明，直接赋值，assign拷贝和assign赋值：

    vec = {1, 2, 3, 4, 5, 6};
    vecvec = {10, 20, 30};

    vec = vecvec;
    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

    vec.assign(vecvec.begin(), vecvec.end());
    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

    vec.assign(10, 0);
    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

三次输出分别是：

10 20 30
10 20 30
0 0 0 0 0 0 0 0 0 0

12、通过insert()进行元素插入，通过erase()进行元素删除；
两者都是通过迭代器操作的，insert会向迭代器所指的位置插入数据，原始数据后移；erase会删除迭代器指向的数据，后面的数据前移。
看一个插入的例子：

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

    //在指定位置插入值为3的元素 
    vec.insert(vec.begin()+1, 3);

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

    //在指定位置插入4个值为2的元素 
    vec.insert(vec.begin()+5, 4, 2);

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

    //在指定位置插入区间[begin, end)的所有元素
    vec.insert(vec.begin()+10, vecvec.begin(),vecvec.end());

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

输出结果为：

1 1 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1 1 1
1 3 1 1 1 2 2 2 2 1 1 1 1 1 1
1 3 1 1 1 2 2 2 2 1 10 20 30 1 1 1 1 1

再看一个删除的例子：

    //删除某个位置的元素
    vec.erase(vec.begin());

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

    //删除指定位置区间[begin, end)的所有元素
    vec.erase(vec.begin()+5, vec.begin()+8);

    for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
        cout<<*i<<" ";
    cout<<endl;

输出结果为：

3 1 1 1 2 2 2 2 1 10 20 30 1 1 1 1 1
3 1 1 1 2 1 10 20 30 1 1 1 1 1

13、通过clear()清空当前容器；

    vec.clear();
    if(vec.empty())
        cout<<"vec is empty"<<endl;

输出为：

vec is empty

14、通过swap()实现交换数据；
如交换两个元素：

    vector<int> v1 = {1,2,3,4,5,6};

    swap(v1[1], v1[3]);

    for(vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
        cout<<*it<<" ";
    cout<<endl;

交换后结果对比为：

1 4 3 2 5 6

交换两个容器：

    vector<int> v1 = {1,2,3,4,5,6};
    vector<int> v2 = {10,20,30,40};

    swap(v1, v2);

    cout<<"v1 = ";
    for(vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
        cout<<*it<<" ";
    cout<<endl;
    cout<<"v2 = ";
    for(vector<int>::iterator it = v2.begin(); it != v2.end(); it++)
        cout<<*it<<" ";
    cout<<endl;

结果为：

v1 = 10 20 30 40
v2 = 1 2 3 4 5 6

swap还可以用来调整内存。当为容器分配的内存过大而出现剩余时，通过vector<int>(vec).swap(vec)；将容器的最大容量减少到目前所需的容量。
这条语句首先会建立一个临时容器，它是原始容器vec的一份拷贝，通过容器的拷贝构造函数来实现，因此只分配拷贝的元素所需要的内存，然后使用swap交换两个容器，最后销毁临时容器，实现将原始容器收缩到合适容量。

    cout<<"size = "<<vec.size()<<" capacity = "<<vec.capacity()<<endl;
    vector<int>(vec).swap(vec);
    cout<<"size = "<<vec.size()<<" capacity = "<<vec.capacity()<<endl;

收缩后的capacity等于size的值。

size = 5 capacity = 8
size = 5 capacity = 5

15、通过rbegin()和rend()获取反转后的容器的起止位置指针。
也即vec.begin() = vec.rend()-1，vec.end() = vec.rbegin()-1，见下面的例子：

    vector<int> vec = {1,2,3,4,5,6};

    cout<<*vec .begin()<<" "<<*(vec .end()-1)<<endl;
    cout<<*vec .rbegin()<<" "<<*(vec .rend()-1)<<endl;

输出结果为：

1 6
6 1

16、最后加一点，用vector实现多维数组。其实就是相当于容器中的元素不再为简单的变量，而是数组或者容器。
看一个例子：

    vector<vector<int>> matrix;
    vector<int> row1 = {1,2,3,4,5};
    vector<int> row2 = {2,3,4,5,6};
    vector<int> row3 = {3,4,5,6,7};
    matrix.push_back(row1);
    matrix.push_back(row2);
    matrix.push_back(row3);
    cout<<"matrix = "<<endl;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 5; j++)
            cout<<matrix[i][j]<<" ";
        cout<<endl;
    }

输出结果为一个二维数组：

注意：通过数组来实现线性表在内存中是连续存储的，因此可以通过通过下标来实现快速访问或者修改元素，高效便捷，但是插入和删除元素的开销太大。

为了提高在任意位置添加或者删除元素的效率，可以采用链式结构来实现线性表。

链表

链表区别于数组，它是一种物理存储非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接顺序实现的。
链表由一系列节点组成，每个节点包括数据部分和链部分，链指向另外的节点来实现逻辑顺序。当增删链表元素时，只需要修改链部分的指向，可以达到很高的效率。
根据链部分，可以将链表分为单向链表（单链表）和双向链表（双链表）。

单链表：每个节点包含指向下一个节点的指针，为单向的；
双链表：每个节点包含指向前一个节点和下一个节点的指针，为双向的；
循环链表：链表的最后一个节点指向第一个节点，为一个环；

首先看一个链表元素的数据结构，以int类型为例。

struct Node
{
    int data;
    Node *pre;
    Node *next;
};

这是一个有三个元素组成的结构体，为链表中的一个节点。data为数据域，也可以为其他类型甚至更复杂的数据结构；pre为指向上一个节点的指针，next为指向下一个节点的指针。

然后我们创建一个NodeList的类，里面实现了利用上面Node数据结构创建链表以及对这个链表增删等各种方法。这个类有两个私有成员，分别为一个int类型的count，表示链表的节点个数，一个指向Node类型的指针head，为这个链表的头节点。

class NodeList
{
    public:
        NodeList();
        ~NodeList();

        int getSize();
        Node* getNode(int i);
        bool insertNode(int i, int data);
        bool deleteNode(int i);
        void print();
    protected:
    private:
        int count;
        Node *head;
};

1.创建链表和删除链表

首先看下这个类的构造函数和析构函数。

    //ctor
    cout<<"this is a constructor of NodeList"<<endl;
    head = new Node();
    head->pre = head->next = NULL;
    count = 0;

    //dtor
    cout<<"this is a constructor of NodeList"<<endl;
    while(head->next)
    {
        Node *tmp = head->next;
        head->next = tmp->next;
        delete tmp;
        tmp = NULL;
        count--;
    }
    delete head;
    head = NULL;

构造函数很简单，就是初始化head节点（注意这里的head节点不存放数据，只是作为一个链表头存在），它的pre和next在初始化时都为空；
析构函数在最后退出时调用，需要释放链表的所有节点，我们首先会删除head后面的节点，最后删除head节点。

2.增加节点

增加节点需要输入两个参数，插入的位置和插入的数据内容。

    Node *tmp = head;
    if(i < 0 || i > count)
    {
        cout<<"out of range"<<endl;
        return false;
    }
    while(i != 0)
    {
        tmp = tmp->next;
        i--;
    }
    Node *node = new Node();
    node->data = data;
    node->next = tmp->next;
    node->pre = tmp;
    tmp->next = node;
    if(node->next)
        node->next->pre = node;
    count++;
    return true;

首先判断插入范围，然后找到对应的位置（从0开始），然后将节点插入到两个节点之间，注意这里修改原始链表指针的顺序。
比如，我们要插入到tmp后面。
链表原始的结构是：··· ··· -> tmp -> tmp1 -> ··· ···
插入后的结构变成：··· ··· -> tmp -> node -> tmp1 -> ··· ···

3.删除节点

删除节点只需要输入删除的位置即可。

    Node *tmp = head;
    if(i < 0 || i > count)
    {
        cout<<"out of range"<<endl;
        return false;
    }
    while(i != 0)
    {
        tmp = tmp->next;
        i--;
    }
    Node *node = tmp->next;
    tmp->next = node->next;
    tmp->next->pre = tmp;
    delete node;
    node = NULL;
    count--;
    return true;

跟插入一样，先判断插入范围，然后找到要删除的节点，整个过程跟插入是互逆的。

4.查找节点

查找节点允许我们根据位置查找相应的节点，这个查找过程的复杂度是O(n)，因为需要遍历整个链表。

    Node *node = head->next;
    if(i < 0 || i > count)
    {
        cout<<"out of range"<<endl;
        return NULL;
    }
    while(i != 0)
    {
        node = node->next;
        i--;
    }
    return node;

5.获取链表节点数

这个很简单，就是返回一个成员变量。

    return count;

6.输出链表

依次打印出链表的内容。

    Node *tmp = head->next;
    cout<<"NodeList : ";
    while(tmp)
    {
        cout<<tmp->data<<" ";
        tmp = tmp->next;
    }
    cout<<endl;

看几个测试例子。

    NodeList nodelist;
    cout<<"size = "<<nodelist.getSize()<<endl;
    nodelist.insertNode(0, 0);
    nodelist.insertNode(1, 1);
    nodelist.insertNode(2, 2);
    nodelist.insertNode(3, 3);
    nodelist.insertNode(4, 4);
    cout<<"size = "<<nodelist.getSize()<<endl;
    nodelist.print();

输出为：

this is a constructor of NodeList
size = 0
size = 5
NodeList : 0 1 2 3 4
this is a constructor of NodeList

查找某个位置的节点：

    cout<<"i = 0 : "<<nodelist.getNode(0)->data<<endl;
    cout<<"i = 3 : "<<nodelist.getNode(3)->data<<endl;
    cout<<"i = 6 : "<<nodelist.getNode(6)<<endl;

输出：

i = 0 : 0
i = 3 : 3
out of range
i = 6 : 0

删除操作：

    nodelist.deleteNode(0);
    nodelist.print();

    nodelist.insertNode(3, 5);
    nodelist.print();

    nodelist.deleteNode(2);
    nodelist.print();

输出：

NodeList : 1 2 3 4
NodeList : 1 2 3 5 4
NodeList : 1 2 5 4

将该链表看作单链表进行逆序：

    NodeList reverse;
    for(int i = 0; i < nodelist.getSize(); i++)
    {
        reverse.insertNode(0, nodelist.getNode(i)->data);
    }
    reverse.print();

输出：

NodeList : 4 3 2 1 0

除了数组和链表，还有两种特殊的线性表，分别为栈和队列。

栈

栈（stack）是一端封闭的的线性表，对于元素的插入、删除、访问都只能在栈顶进行。因此栈的特点是LIFO（Last In First Out），即后进先出。

栈的操作主要包括三种：

push：压栈，向栈中添加元素；
pop：出栈，返回并删除栈顶元素；
peek：返回栈顶元素。

这里给出栈的三种实现方式。

1.数组实现栈

定义一个Stack的类，成员变量为int类型的容器m_stack，存放栈元素，int类型的变量count，为栈元素个数。然后我们需要去实现push、pop、peek等操作栈的方法。

class Stack
{
    public:
        Stack();
        ~Stack();

        void push(int data);
        int pop();
        int peek();
        int getSize();
        void print();

    protected:
    private:
        vector<int> m_stack;
        int count;
};

实现起来比较简单，分别看下。

1.1 创建和销毁

没什么内容，就是为count赋个初值。

Stack::Stack()
{
    //ctor
    cout<<"this is a ctor of stack"<<endl;
    count = 0;
}

Stack::~Stack()
{
    //dtor
    cout<<"this is a dtor of stack"<<endl;
}

1.2 入栈

直接用vector的push_back函数，然后count加一。

void Stack::push(int data)
{
    m_stack.push_back(data);
    count++;
}

1.3 出栈

保留栈顶元素，调用vector的pop_back函数，然后count减一。

int Stack::pop()
{
    count--;
    int res = m_stack.at(count);
    m_stack.pop_back();
    return res;
}

1.4 取栈顶元素

直接返回最后一个元素。

int Stack::peek()
{
    return m_stack.at(count-1);
}

1.5 获取栈大小

直接返回count。

int Stack::getSize()
{
    return m_stack.size();
}

1.6 打印栈

遍历数组即可。

void Stack::print()
{
    cout<<"m_stack : ";
    for(vector<int>::iterator i = m_stack.begin(); i != m_stack.end(); i++)
    {
        cout<<*i<<" ";
    }
    cout<<endl;
}

看一下测试代码：

    Stack stack;
    stack.push(0);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    stack.push(6);

    cout<<"size = "<<stack.getSize()<<endl;
    stack.print();

输出：

this is a ctor of stack
size = 7
m_stack : 0 1 2 3 4 5 6
this is a dtor of stack

注意区别一下pop和peek，返回栈顶元素，一个会删除元素，另一个则不做其他操作。

    stack.print();
    cout<<"peek : "<<stack.peek()<<endl;
    stack.print();
    cout<<"pop : "<<stack.pop()<<endl;
    stack.print();
    cout<<"peek : "<<stack.peek()<<endl;
    stack.print();

输出：

m_stack : 0 1 2 3 4 5 6
peek : 6
m_stack : 0 1 2 3 4 5 6
pop : 6
m_stack : 0 1 2 3 4 5
peek : 5
m_stack : 0 1 2 3 4 5

2.单向链表实现栈

定义一个Stack1的类，成员变量为sNode 类型的指针head，int类型的变量count，为栈元素个数。

class Stack1
{
    public:
        Stack1();
        ~Stack1();

        void push(int data);
        int pop();
        int peek();
        int getSize();
        void print();

    protected:
    private:
        sNode *head;
        int count;
};

具体实现跟数组差不多，给出代码就不详细说了。

Stack1::Stack1()
{
    //ctor
    cout<<"this is a ctor of stack1"<<endl;
    head = new sNode();
    head->next = NULL;
    count = 0;
}

Stack1::~Stack1()
{
    //dtor
    cout<<"this is a dtor of stack1"<<endl;
    while(head->next)
    {
        sNode *tmp = head->next;
        head->next = tmp->next;
        delete tmp;
        tmp = NULL;
        count--;
    }
    delete head;
    head = NULL;
}

void Stack1::push(int data)
{
    sNode *node = new sNode();
    node->data = data;
    node->next = head->next;
    head->next = node;
    count++;
}

int Stack1::pop()
{
    int res;
    if(head->next)
        res = head->next->data;
    head->next = head->next->next;
    count--;
    return res;
}

int Stack1::peek()
{
    int res = 0;
    if(head->next)
        res = head->next->data;
    return res;
}

int Stack1::getSize()
{
    return count;
}

void Stack1::print()
{
    cout<<"m_stack : ";
    sNode *tmp = head->next;
    while(tmp)
    {
        cout<<tmp->data<<" ";
        tmp = tmp->next;
    }
    cout<<endl;
}

测试代码和结果跟数组也是一样的，就不贴了。

3.STL标准库

如果我们使用C++标准库，用不着费那么大劲去实现栈，它已经给我们封装好了，跟vector一样直接使用，十分方便。

只需要加这么一句：#include <stack>。

看下测试代码：

    stack<int> istack;
    istack.push(0);
    istack.push(1);
    istack.push(2);
    istack.push(3);
    istack.push(4);
    istack.push(5);

    cout<<"size = "<<istack.size()<<endl;

    cout<<"istack : ";
    while(!istack.empty())
    {
        cout<<istack.top()<<" ";
        istack.pop();
    }
    cout<<endl;

    if(istack.empty())
        cout<<"now stack is empty"<<endl;

输出结果为：

size = 6
top : 5
istack : 5 4 3 2 1 0
now stack is empty

队列

队列（queue）是一种两端开方的线性结构。它在线性表的前端（front），即队首进行删除操作，在表的后端（rear），队尾进行插入操作。因此，它遵循先进先出（First In First Out， FIFO）的方式。

队列的操作主要也是三种：

push：入队，向队列末尾添加元素；
pop：出队，删除队列开始位置的元素；
front：返回队列开始位置的元素。

还是给出队列的几种实现形式。

1.数组实现

在Queue这个类中，主要还是实现下面操作队列的几个方法，大部分跟栈的实现是一样的。

class Queue
{
    public:
        Queue();
        ~Queue();

        void push(int data);
        int pop();
        int front();
        int getSize();
        void print();

    protected:
    private:
        vector<int> m_queue;
        int count;
};

实现：

Queue::Queue()
{
    //ctor
    cout<<"this is a ctor of queue"<<endl;
    count = 0;
}

Queue::~Queue()
{
    //dtor
    cout<<"this is a dtor of queue"<<endl;
}

void Queue::push(int data)
{
    m_queue.push_back(data);
    count++;
}

int Queue::pop()
{
    int res = m_queue.at(0);
    int i = 1;
    while(i < count)
    {
        m_queue[i-1] = m_queue[i];
        i++;
    }
    count--;
    m_queue.pop_back();
    return res;
}

int Queue::front()
{
    return m_queue.at(0);
}

int Queue::getSize()
{
    return m_queue.size();
}

void Queue::print()
{
    cout<<"m_queue : ";
    for(vector<int>::iterator i = m_queue.begin(); i != m_queue.end(); i++)
    {
        cout<<*i<<" ";
    }
    cout<<endl;
}

注意这里的push是添加到数组的末尾，因此pop就要从数组开始进行，因此是m_queue.at(0)，然后要将后面的元素依次前移一位，然后删除最后一个元素。

测试：

    Queue queue;
    for(int i = 0; i < 6; i++)
        queue.push(i);

    cout<<"size = "<<queue.getSize()<<endl;
    queue.print();
    cout<<"front : "<<queue.front()<<endl;
    queue.print();
    cout<<"pop : "<<queue.pop()<<endl;
    queue.print();
    cout<<"front : "<<queue.front()<<endl;
    queue.print();
    cout<<"push : "<<endl;
    queue.push(7);
    queue.print();

输出：

this is a ctor of queue
size = 6
m_queue : 0 1 2 3 4 5
front : 0
m_queue : 0 1 2 3 4 5
pop : 0
m_queue : 1 2 3 4 5
front : 1
m_queue : 1 2 3 4 5
push :
m_queue : 1 2 3 4 5 7
this is a dtor of queue

2.链表实现

链表实现也差不多，代码如下：

struct qNode
{
    int data;
    qNode *next;
};

class Queue1
{
    public:
        Queue1();
        ~Queue1();

        void push(int data);
        int pop();
        int front();
        int getSize();
        void print();

    protected:
    private:
        qNode *head;
        int count;
};

方法的实现：

Queue1::Queue1()
{
    //ctor
    cout<<"this is a ctor of queue1"<<endl;
    head = new qNode();
    head->next = NULL;
    count = 0;
}

Queue1::~Queue1()
{
    //dtor
    cout<<"this is a dtor of queue1"<<endl;
    while(head->next)
    {
        qNode *tmp = head->next;
        head->next = tmp->next;
        delete tmp;
        tmp = NULL;
        count--;
    }
    delete head;
    head = NULL;
}

void Queue1::push(int data)
{
    qNode *node = new qNode();
    node->data = data;
    node->next = NULL;
    qNode *tmp = head;
    while(tmp->next)
        tmp = tmp->next;
    tmp->next = node;
    count++;
}

int Queue1::pop()
{
    int res = 0;
    if(head->next)
        res = head->next->data;
    head->next = head->next->next;
    count--;
    return res;
}

int Queue1::front()
{
    int res = 0;
    if(head->next)
        res = head->next->data;
    return res;
}

int Queue1::getSize()
{
    return count;
}

void Queue1::print()
{
    cout<<"m_queue : ";
    qNode *tmp = head->next;
    while(tmp)
    {
        cout<<tmp->data<<" ";
        tmp = tmp->next;
    }
    cout<<endl;
}

为了操作方便，我们以链表末尾为队列开始位置，链表起始位置为队列开头。这样，需要入队时，需要找到队列的最后一个节点，然后将该节点的next指针指向新增加的节点即可；出队或者输出队首元素时，取head->next的节点就可以了。

测试代码和结果跟数组实现的是一样的。

3.STL标准库

同样，如果我们使用C++标准库，也无需实现队列，而是通过#include <queue>，直接去使用。

测试代码：

    queue<int> iqueue;
    for(int i = 0; i < 6; i++)
        iqueue.push(i);

    cout<<"size = "<<iqueue.size()<<endl;

    cout<<"iqueue : ";
    while(!iqueue.empty())
    {
        cout<<iqueue.front()<<" ";
        iqueue.pop();
    }
    cout<<endl;

    if(iqueue.empty())
        cout<<"now queue is empty"<<endl;

输出：

size = 6
iqueue : 0 1 2 3 4 5
now queue is empty

本文所有例子见github：下载测试代码

上一篇：并查集总结

下一篇： TopK 问题

数据结构——线性结构

数组

多维数组

动态数组

链表

栈

队列

从数据结构分析看：用for each...in 比 for...in 要快些_基础知识

javascript - 关于页面跳转，如何不在地址栏显示目录结构

html5主体结构元素有哪些

thinksns 核心架构及目录结构

Oracle数据库开发结构设计技巧

Ecshop文件结构，二次开发

PHP SPL标准库之数据结构栈(SplStack)介绍_PHP

树型结构列出目录中所有文件的php代码

WordPress目录文件结构详细说明，wordpress详细说明

[视频教程]PHP100视频教程59：关于BIWEB常见问题和结构分析