Loading... <div class="tip share">请注意，本文编写于 2221 天前，最后修改于 2221 天前，其中某些信息可能已经过时。</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 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏