C++ queue (STL容器适配器)-蒲公英云

C++ queue (STL容器适配器)

适配器

queue

queue的使用

queue的模拟实现

适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，适配器是将一个类的接口转换成客户希望的另外一个接口。

举个栗子, 咱们香港的插头和我们内地是不一的, 如下图, 这种插头在咱们内地是不方便使用的, 要是香港同胞到对岸深圳转一转, 被繁华的深圳所吸引, 不禁多留了两天, 那这时候手机要充电怎么充电啊, 不过没关系, 我们有适配器, 其实真正给手机充电的还是手机充电器, 适配器只是方便了人们的使用而已 .
港版充电器适配器适配器的使用

常见的容器适配器有stack , queue, priority_queue, 它们就相当于上图的适配器, 真正给手机充电的是还是充电头, 同样的道理, 它们底层是靠别的容器实现的
例如:
stack可以用vector, deque, list实现.
queue可以用 deque, list实现
priority_queue, 可以用 deque, vector实现

queue

队列是一种容器适配器，专门用于在(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下，如果没有实例化指定容器，则使用标准容器deque。
需要头文件#include
为什么选择deque作为queue的底层默认容器
主要原因
deque优点: 两端插入删除最快的
deque缺点: 迭代器复杂效率低
queue利用了优点规避了缺点, 在两端插删, 且并未使用迭代器, 所以deque最优

queue图示 :

C++STL容器适配器之stack
C++ STL容器适配器之priority_queue

queue的使用

函数名称	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
back()	返回队尾元素的引用
front()	返回队头元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

queue的模拟实现

myqueue.h

#pragma once
#include<deque>
using namespace std;
template<class T, class Con = deque<T>>
class myqueue {
    Con qu;
public:
    myqueue() {
    }
    void push(const T& val) {
        qu.push_back(val);
    }
    void pop() {
        qu.pop_front();
    }
    T& front() {
        return qu.front();
    }
    T& back() {
        return qu.back();
    }
    int size() {
        return qu.size();
    }
    bool empty() {
        return qu.empty();
    }
};

测试入口main.cpp

#include<iostream>
#include<deque>
#include<queue>
#include<list>
#include"myqueue.h"
using namespace std;
void Test_queue() {
    cout << "STL中的queue\n";
    queue<int, deque<int>> qu;
    for (int i = 1; i <= 5; ++i) {
        qu.push(i);
    }
    cout << "size = " << qu.size() << endl;
    cout << qu.back() << endl;
    while (!qu.empty()) {
        cout << qu.front() << endl;
        qu.pop();
    }
    cout << "size = " << qu.size() << endl;
}
void Test_myqueue() {
    cout << "自己实现的的queue\n";
    myqueue<int> qu;
    //myqueue<int, list<int>> qu;
    for (int i = 1; i <= 5; ++i) {
        qu.push(i);
    }
    cout << "size = " << qu.size() << endl;
    cout << qu.back() << endl;
    while (!qu.empty()) {
        cout << qu.front() << endl;
        qu.pop();
    }
    cout << "size = " << qu.size() << endl;
}
int main() {
    Test_queue();
    Test_myqueue();
    system("pause");
    return 0;
}