队列（queue）是一种先进先出的线性数据结构，它模拟了排队现象，新加入元素在队尾，率先处理的元素在队头。

队列的常用操作

// 初始化
queue<queue> queue;

// 入队
queue.push(1);
queue.push(2);

// 访问队首元素
int front = queue.front(); 

// 出队
queue.pop();

// 获取队列长度
int size = queue.size();

// 判空
bool empty = queue.empty();

队列实现

基于链表的实现

class LinkedListQueue {
private:
  ListNode* front;
  ListNode* rear;
  int queSize;
public:
  LinkedListQueue() {
    front = nullptr;
    rear = nullptr;
    queSize = 0;
  }
  
  ~LinkedListQueue() {
    freeMemoryLinkedList(front);
  }
  
  int size() {
    return queSize;
  }
  
  bool isEmpty() {
    return queSize == 0;
  }
  
  void push(int num) {
    ListNode* node = new ListNode(num);
    if (front == nullptr) {
      front = node;
      rear = node;
    } else {
      rear->next = node;
      rear = node; 
    }
    
    ++queSize;
  }
  
  int pop() {
    int num = peek();
    ListNode* tmp = front;
    front = front->next;
    
    delete tmp;
    --queSize;
    return num;
  }
  
  int peek() {
    if (size() == 0)
      throw out_of_range("队列为空");
    return front->val;
  }
  
  vector<int> toVector() {
    ListNode* node = front;
    vector<int> res(size());
    
    for (int i = 0; i < res.size(); ++i) {
      res[i] = node->val;
      node = node->next;
    }
    
    return res;
  }  
}

基于数组的实现

[!IMPORTANT]

在入队和出队过程中，数组实现的队列，front和rear会不断的向一方移动，但数组的大小是有限的。因此当front和rear到达数组尾部时将无法再继续移动，因此需要利用环形数组。

class ArrayQueue {
private:
 int* num;
 int front;
 int queSize;
 int queCapacity;

public:
  ArrayQueue(int capacity) {
    nums = new int[capacity];
    queCapacity = capacity;
    front = queSize = 0;
  }
  
  ~ArrayQueue() {
    delete nums;
  }
  
  int capacity() {
    return queCapacity;
  }
  
  int size() {
    return queSize;
  }
  
  bool isEmpty() {
    return size() == 0;
  }
  
  void push(int num) {
    if (queSize == queCapacity) {
      return;
    }
    
    int rear = (front + queSize) % queCapacity;
    nums[rear] = num;
    ++queSize;
  }
  
  int pop() {
    int num = peek();
    front = (front + 1) % queCapacity;
    --queSize;
    return num;
  }
  
  int peek() {
    if (isEmpty()) {
      throw out_of_range("empty");
    }
    
    return nums[front]l;
  }
}

队列的应用

1. 消息队列
2. 代办事项