队列

id: queue

定义

队列是一种特殊的线性表，具有先进先出和后进先出的性质。只允许一端进行插入操作，另一端进行删除操作的线性数据结构

  • 队头
  • 队尾

性质

先进先出,First In First Out, FIFO

操作

  • headhead,永远指向队列的开头的第一个元素的位置
  • tailtail,永远指向队列的结尾的最后一个元素的后面一个位置

也就是[head,tail)[head,tail)表示元素的范围

创建队列

const int maxn = 1e5+5; //队列的最大容量
int que[maxn]; //队列的存储空间
int head= 0, tail = 0;  //队头和队尾

基本操作

  1. 插入元素
void push (int n){
    que[tail++] = n; //为什么是tail++,不是++tail?
}
  1. 删除元素
void pop() {
    head++;
}
  1. 获得队列中第一个元素
int front() {
    return que[head];
}
  1. 获得队列中最后一个元素
int back() {
    return que[tail-1];
}
  1. 判断队列是否为空
bool empty() {
    return head == tail;
}
  1. 获得队列中元素的个数
int size() {
    return tail-head;
}

模板

template<typename T = int,int siz = maxn>
struct myqueue{
    T a[siz+5];
    //tail 指向最后一个元素后面一个位置
    //head 指向第一个元素
    int head = 0,tail=0; 

    void clear() { head =tail = 0;}

    void push(T b) { a[tail++] = b;}

    void pop(){head++;}
    void pop_back(){tail--;}

    T front() { return a[head];}
    T back() { return a[tail-1];}

    bool empty() { return head == tail;}

    int size() { return tail-head;}
};

练习