笔记·C++数据结构：队列

顺序队列

队尾：入队操作

队首：出队操作

队空：front=rear

队满：Full = (rear-front)

循环队列

空出来一个位置，为了更好地判断队空/队满

空队列：front=near

满队列：(rear + 1)%Full == front%Full

C++ STL库中的队列

包含头文件queue

1 2	#include <queue> using namespace std;//必须

不要像我一样憨憨地拼错

queue q;

创建一个空的int类型队列q；

q.empty();

判断队列是否为空，为空返回true，否则返回false；

q.size();

返回队列q中元素的个数，即队列长度；

q.front();

获取队首元素的值；

q.back();

获取队尾元素的值；

q.push(x);

在队尾插入元素x；

q.pop();

队首元素出队。（没有返回值）

Example

#include <iostream>
#include <queue>
using namespace std;

int main(){
    queue<int> Queue1;

    for(int i = 1;i <= 10; i++)Queue1.push(i);

    cout<<"队首元素"<<
    Queue1.front()<<
    endl<<"队尾元素"<<
    Queue1.back()<<
    endl;
    
    int total = 0;
    for(int i = 10;i >= 1; i-- ){
        total+=Queue1.front();
        Queue1.pop();
    }
    cout<<"总和："<<total<<endl;

    return 0;
}

C++ STL库中的双端队列

包含头文件deque

1 2	#include <deque> using namespace std;//必须

deque dq;

创建一个空的int型双端队列dq；

dq.empty();

判断队列是否为空，返回同quere.empty()；

dq.size();

返回dq队列中元素的个数;

dq.max_size();

返回双端队列能容纳的最大元素个数；

dq.front();

返回队首元素的值；

dq.back();

返回队尾元素的值；

dq.push_front(a);

在队首插入元素a；

dq.push_back(b);

在队尾插入元素b；

dq.pop_front();

删除队首元素，没有返回值；

dq.pop_back()

删除队尾元素，没有返回值。

Example

#include <iostream>
#include <deque>
using namespace std;
int main(){
    deque<int> doublefun;//双倍快乐
    int total = 0;
    for(int i = 0;i <= 5;i++){
        doublefun.push_front(i);
    }
    for(int i = 10; i >= 5; i--){
        doublefun.push_back(i);
    }
    cout<<"双端队列能容纳的最大元素："<<doublefun.max_size()<<endl;
    for(int i = 0;i <= 10;i++){
        total += doublefun.front();
        cout<<"出队："<<doublefun.front()<<endl;
        doublefun.pop_front();
    }
    
    cout<<"总和："<<total<<endl;

    return 0;
}