数据结构

Queues  队列

队列是一种先进先出 First In First Out（FIFO）的数据结构，支持三种操作，所有操作的时间复杂度均为 𝒪(1) 。

std::queue

• push: 在队列的末尾插入

• pop: 从队列的前端删除

• front: 获取前端元素但不将其移除

queue<int> q;
q.push(1);                  // [1]
q.push(3);                  // [1, 3]
q.push(4);                  // [1, 3, 4]
q.pop();                    // [3, 4]
cout << q.front() << endl;  // 3

from queue import Queue

q = Queue()           # []
q.put(1)              # [1]
q.put(2)              # [1, 2]
v = q.queue[0]        # v = 1, q = [1, 2]
v = q.get()           # v = 1, q = [2]
v = q.get()           # v = 2, q = []
v = q.get()           # 代码会一直等待，导致TLE错误

Deques  双端队列

一个双端队列（通常发音为“deck”）代表双端队列，它是栈和队列的结合，支持在双端队列的前后两端进行插入和删除操作。

std::deque

添加和删除的四种方法是 push_back , pop_back , push_front , 和 pop_front 。

deque<int> d;

d.push_front(3);  // [3]
d.push_front(4);  // [4, 3]
d.push_back(7);   // [4, 3, 7]
d.pop_front();    // [3, 7]
d.push_front(1);  // [1, 3, 7]
d.pop_back();     // [1, 3]

d = collections.deque()
d.appendleft(3)  # [3]
d.appendleft(4)  # [4, 3]
d.append(7)  # [4, 3, 7]
d.popleft()  # [3, 7]
d.appendleft(1)  # [1, 3, 7]
d.pop()  # [1, 3]

你也可以像用数组的 [] 运算符一样，以常数时间访问双端队列中的元素。例如，要访问双端队列 dq 中的 i 个元素，可以使用 dq[i] 。