请注意,本文编写于 1636 天前,最后修改于 1636 天前,其中某些信息可能已经过时。
队列 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)。
代码实现:
这里我一样是用链表实现的:
#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(); }
};