Loading... <div class="tip share">请注意,本文编写于 2078 天前,最后修改于 2078 天前,其中某些信息可能已经过时。</div> ##队列 Queue 队列也是一种线性数据结构,与数组相比,队列对应的操作是数组的子集。 只能从一端 (队尾) 添加元素,只能从另一端 (队首) 取出元素。 队列的应用可以在播放器上的播放列表,数据流对象,异步的数据传输结构(文件IO,管道通讯,套接字等)上体现,当然最直观的的就是排队了 : D ##队列的实现 ###函数说明: | 函数 | 说明 | 复杂度 | | ------------ | ------------ | ------------ | | void push(int data) | 入队 | 平均O(1) | | int pop() | 出队 | 数组O(n), 链表O(1) | | int front() | 获取队首元素 | O(1) | | int size() | 获取队列元素个数 | O(1) | | bool empty() | 判断队列是否为空 | O(1) | @> 入队是从队尾开始,有可能触发resize,因此均摊下来是O(1)。出队是在队首,数组实现每次都要挪动所有元素,O(n)。当然,链表还是O(1)。 ###代码实现: 这里我一样是用链表实现的: ```cpp #include <list> using namespace std; class Queue { private: list<int> value; public: void push(int data) { value.push_back(data); } int pop() { int tmp = front(); value.pop_front(); return tmp; } int front() { return value.front(); } int size() { return value.size(); } bool empty() { return value.empty(); } }; ``` 最后修改:2019 年 04 月 08 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏