再探队列

我为什么要说再？？？？？打算明天在总结的想想不能再鸽了啊。因为菜鸡越鸽越菜！为了防止我成为弱弱弱弱的菜鸡所以很有必要好好好好学习。

什么是队列

队列是一个简单的等待数列。尾部加入元素，头部删除元素，和栈不同的是它是可以两端都是用的一种结构：一端用来加入元素，一端用来删除元素。因此最后一个元素只能等排在他之前的元素全部删除之后才可以操作。操作和栈都差不多

clean()----清空队列
isEmpty()----判断队列是否为空
enqueue(a)-----在尾部加入元素a
dequeue()------取出队列的第一个元素
FristEI()-------返回队列第一个元素但不删除

那么接下来就先写一个超级简单模板库队列【毕竟我是辣鸡嘛】

#include<bits/stdc++.h>
using namespace std;
int main(){
queue<int> q1;
queue<int,list<int>>q2;
q1.push(1);
q1.push(2);
q1.push(3);
q1.push(4);
q2.push(5);
q2.push(6);
q2.push(7);
q2.push(8);

q1.push(q2.back());
while(!q1.empty()){
  cout<<q1.front()<<" ";
  q1.pop();
}
while (!q2.empty())
{
  cout<<q2.front()<<" ";
  q2.pop();
}

system("pause");
  return 0;
}

这是标准模板库中的队列，自己写模板什么的…毕竟我是辣鸡嘛

顺序队列

不理想的设计【雾】：
1 . 若使用顺序表的尾端插入实现enqueue操作，根据队列性质，出队操作应该在表的首端进行。为了维护顺序表的完整性（表元素在表前端连续存放），出队操作取出当时的首元素后，就需要把表中其余元素全部前移，这样就会是一个 O(n) 时间的操作。
2 . 反过来：从尾端出队是 O(1) 操作，但从首端入队就是 O(n) 时间操作，这种设计也不理想。
3 . 另一种是在队首元素出队后表中的元素不前移，但记住新队头位置。如果队列中没有空闲了，只需要在入队时，再集中触发一次数据的搬移操作。

顺序队列也被称为队列的数组是实现，我写的我感觉完全看不出来错误，但是编译器他就是一直报错，啊，我是辣鸡！！！说以为了保证严谨性就完完全全拿了网上一片大大的文章

源代码地址

请摁我！

一：队列的数组实现【来了来了模板他来了】

我们用 first 和 last 存储队列首元素和尾元素的下标。
*当队列为空时，习惯上设置 first 和 last 的值为-1。当数据入队时, 必须先++相应的下标，然后再存入数据。

*判断队列是否为空：这时只需要看 first 就可以，如果 first == -1 ，队列即为空。

*判断队列是否已满：队列满队，有两种情况：
1.当队列首次按顺序存满数据时，它的 first 等于0，指向storge数组第一个元素位置storge[0]，而它的last 等于size-1，指向storge数组最后一个元素storge[size-1]，此时队列已满。
2.另外一种情况就是，但我们首次队列满时，将一些元素出队，由于队列是FIFO结构，从头部开始出队，这样在队列元素未全部出队的情况下，first 指向后移。当我们再次将一些数据入队时，last 从storge[size-1] 再次回到 storge[0]，然后按照队列顺序入队，当last = first -1 时，队列再次满队。

*入队操作：
1.首先入队操作首先判断队列是否已满，队列已满则不入队。
2.其次，我们要注意到特殊情况，当队列由空队开始存入第一个数据时，以及last 等于 size-1 时，我们下一个数据入队会被存储在storge[0]的位置，此时需要令 last = 0，不要忘了如果 first 等于-1，同时要令 first = 0;
3.其他情况++last，然后入队即可。

*出队操作：
1.首先判断队列是否空，若为空，则不能出队。
2.重点：当 first等于last 时，说明队列中只有一个元素，此时出队后队列为空，切记将 first ，last值赋为-1，表示队列空。
3.特殊情况：当 first 等于size-1 时，它处于storge数组尾部，事实上由于它是队列此状态下的首元素，队列的第二个元素是storge数组storge[0]，所以此时进行出队操作后，须将 first 的值设置为0。
4.其他情况直接出队，++first即可。

队列数组实现代码如下：

#ifndef _ARRAY_QUEUE_H
#define _ARRAY_QUEUE_H

#include <iostream>
using namespace std;

template<typename T, int size = 0>
class Queue{
public:
    Queue();

    bool is_empty()const;
    bool is_full()const;
     
    void enqueue(const T&);
    T dequeue();
     
    void traverse()const;

private:
    T storge[size];
    int first;
    int last;
};

template<typename T, int size>
Queue<T, size>::Queue()
{
    first = last = -1;
}

template<typename T, int size>
bool Queue<T, size>::is_empty()const
{
    return first == -1;
}

template<typename T, int size>
bool Queue<T, size>::is_full()const
{
    return first == 0 && last == size - 1 || last == first - 1;
}

template<typename T, int size>
void Queue<T, size>::enqueue(const T& elem)
{
    if(!is_full()){
        if(last == -1 || last == size -1){
            storge[0] = elem;
            last = 0;
            if(first == -1)
                first = 0;
        }
        else storge[++last] = elem;
    }
    else{
        cout << "Queue full." << endl;
        exit(EXIT_FAILURE);
    }
}

template<typename T, int size>
T Queue<T, size>::dequeue()
{
    if(is_empty()){
        cout << "Queue empty." << endl;
        exit(EXIT_FAILURE);
    }

    T tmp;
     
    tmp = storge[first];
    if(first == last)
        last = first = -1;
    else if(first == size - 1)
        first = 0;
    else ++first;
     
    return tmp;

}

template<typename T, int size>
void Queue<T, size>::traverse()const
{
    for(auto i=first; i<=last; ++i)
        cout << storge[i] << " ";
    cout << endl;
}

#endif

下面是测试程序实测完全OK

#include "array_queue.h"
 
int main()
{
    Queue<int, 3> queue;
    
    queue.enqueue(10);
    queue.enqueue(10);
+/-    queue.enqueue(10);
    cout << queue.is_full() <<endl;
    
    queue.traverse();
    
    queue.dequeue();
    queue.dequeue();
    queue.dequeue();
    
    queue.is_empty();
    queue.traverse();
}

而c版的实现是这样的哒

#include<bits/stdc++.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef int Status;
//===============循环队列=====================
#define MAXQSIZE 6    //最大队列长度
typedef int QElemType;
typedef struct {
    QElemType *base; //初始化的动态分配存储分配空间
    int front;	//头指针，若队列不空，指向队头元素
    int rear;	//尾指针，若队列不空，指向队尾元素的下一个位置
}SqQueue;
//================队列初始化==========
Status InitQueue(SqQueue *Q) {
    //构造一个空队列Q
    Q->base = new QElemType[MAXQSIZE];
    if (!Q->base) exit(OVERFLOW);//存储分配失败
    Q->front = Q->rear = 0;
    return OK;
}
//================入队================================
Status EnQueue(SqQueue *Q,QElemType e) {
    //插入元素e为Q的新的队尾元素
    if ((Q->rear + 1) % MAXQSIZE == Q->front)return ERROR;//队列满
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXQSIZE;//重新设置队尾指针
    return OK;
}
//===============出队=================================
Status DeQueue(SqQueue *Q, QElemType *e) {
    //若队列不空，则删除Q的对头元素，用e返回其值
    if (Q->front == Q->rear)return ERROR;//队空
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAXQSIZE;
    return OK;
}
int main() {
    SqQueue Q;
    QElemType e;
    int i = 5, j = 5;
    InitQueue(&Q);
    for (i; i > 0; i--) {
        EnQueue(&Q, i);
        printf("入队元素为%d\n", i);
    }
    for (j; j > 0; j--) {
        DeQueue(&Q, &e);
        printf("出队元素为%d\n", e);
    }
    system("pause");
    return 0;
}

链式队列

最简单的单链表只支持首端 O(1) 的操作，在另一端操作需要 O(n) 时间。不适合作为队列的实现基础。
考虑带表尾指针的单链表，它支持 O(1) 时间的尾端插入操作；再加上表首端的高效访问和删除，基于单链表实现队列就很容易。

辣鸡本鸡

依然是大大的 代码


#ifndef _LIST_QUEUE_H
#define _LIST_QUEUE_H
 
#include <list>
#include <iostream>
using namespace::std;
 
template<class T>
class Queue{
public:
    Queue() = default;
 
    bool is_empty()const;
    T& front();
    
    T dequeue();
    void enqueue(const T&);
    
    size_t size()const;
    void clear();
private:
    list<T> lst;
};
 
template<class T>
bool Queue<T>::is_empty()const
{
    return lst.is_empty();
}
 
template<typename T>
T& Queue<T>::front()
{
    return lst.front();
}
 
template<typename T>
T Queue<T>::dequeue()
{
    if(!lst.size()){
        cout << "Queue empty." << endl;
        exit(EXIT_FAILURE);
    }
 
    T tmp = lst.front();
    lst.pop_front();
    
    return tmp;
}
 
template<typename T>
void Queue<T>::enqueue(const T& elem)
{
    lst.push_back(elem);
}
 
template<typename T>
void Queue<T>::clear()
{
    lst.clear();
}
 
template<typename T>
size_t Queue<T>::size()const
{
    return lst.size();
}
 
#endif

这里说明一下。链表的实现采用了标准模板库中的list

那再来说两种队列吧

阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

注：可以用阻塞队列实现一个“生产者-消费者模型”。基于阻塞队列，可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。

并发队列

在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题。
要实现一个线程安全的队列就需要并发队列。
最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。

优先队列

啥玩意是优先队列啊，小朋友，你是否有很多问题，在很多情况下，简单的队列结构是远远不够的，我们需要更复杂的方法来应付这些复杂的场景。加入是一个残疾人去银行排队，职员应该首先给他服务而不是排在他前面的那些人。公路收费亭也应该优先于警车和消防车优先通过。说以休闲队列的关键在于，如何更加快速高效的进行出队列和如对列的操作。元素会随机到达队列，说以并不能保证排在前面的元素先出列排在后面的元素后出列。在不同的引用场景下我们可以采用不同的优先规则。这里主要说明标准模板库中的优先对列。

priority_queue容器默认vector容器x实现
deque容器也是可以的
list是不行哒

STL优先队列的使用

定义
1
priority_queue<Type,Container=vector<Type>,cmp=greater<Type>>que;
其中，第一个参数为数据类型，第二个参数为容器（默认为vector），第三个参数为比较函数（默认大值优先）。

比较函数的写法

使用C++自带的库函数
自定义优先级1
自定义优先级2
自定义优先级3

方法一：使用C++自带的库函数

首先在头文件中引用include库函数

#include

functional 中提供了如下的基于模板的比较函数对象。

equal_to: 等于
not_equal_to: 不等于
greater: 大于
greater_equal: 大于等于
less: 小于
less_equal: 小于等于

创建方法：priority_queue,less>que;

方法二：自定义优先级1，队列元素为数值型

struct cmp1{
    bool operator()(int &a,int &b){
        return a<b;//最大值优先
    }
};
struct cmp{
    bool operator()(int &a,int &b){
        return a>b;//最小值优先
    }
};

创建方法：priority_queue,cmp1>que;

方法三：自定义优先级2，队列元素为结构体

struct node1{
    int x,y;
    bool operator < (const node1 &a) const {//只能重载<
        retrun x<a.x;//最大值优先
    }
};
struct node2{
    int x,y;
    bool operator < (const node2 &a) const {
        retrun x>a.x;//最小值优先
    }
};

创建方法：priority_queueque;

方法四：自定义优先级3，队列元素为结构体

struct node{
    int x,y;
}；
bool operator < (const node &a,const node &b){
    return a.x<b.x;按成员x最大值优先
}
/*bool operator < (const node &a,const node &b){//由于都是重载<,所以两种比较形式只能同时存在一种
    return a.y>b.y;按成员y最小值优先
}*/

创建方法：priority_queueque;

当然实际中俺就使过第一种嘻嘻嘻

那那那这里就来具体实现一下标准模板库中的优先对列

#include<iostream>
#include<queue>
#include<functional>
using namespace std;
int main(){
    priority_queue<int>q1;
    priority_queue<int,vector<int>,greater<int>>q2;
    q1.push(1);q1.push(2);q1.push(3);
    q2.push(3);q2.push(2);q2.push(1);
    int a[]={1,2,6,4,7,8,9,3,5};
    priority_queue<int,vector<int>,less<int>>q3(a,a+9);
    while (!q1.empty())
    {
        cout<<q1.top()<<" ";
        q1.pop();

    }
    while (!q2.empty())
    {
        cout<<q2.top()<<" ";
        q2.pop();
    }
    while (!q3.empty())
    {
        cout<<q3.top();
        q3.pop();
    }
    system("pause");    
    return 0;
}

你以为完了吗还有呐

双端队列

先说方法STL提供的方法贼多

构造：

deque c 创建一个空的deque
deque c1(c2) 复制一个deque。
deque c(n) 创建一个deque，含有n个数据，数据均已缺省构造产生。
deque c(n, elem) 创建一个含有n个elem拷贝的deque
deque c(beg,end) 创建一个以[beg;end)区间的deque
c.~deque() 销毁所有数据，释放内存

方法：

c.assign(beg,end) 将[beg; end)区间中的数据赋值给c。
c.assign(n,elem) 将n个elem的拷贝赋值给c。
c. at(idx) 传回索引idx所指的数据，如果idx越界，抛出out_of_range。
c.back() 传回最后一个数据，不检查这个数据是否存在。
c.begin() 传回迭代器中的第一个数据。
c.clear() 移除容器中所有数据。
c.empty() 判断容器是否为空。
c.end() 指向迭代器中的最后一个数据地址。
c.erase(pos) 删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) 删除[beg,end)区间的数据，传回下一个数据的位置。
c.front() 传回第一个数据。
get_allocator 使用构造函数返回一个拷贝。
c.insert(pos,elem) 在pos位置插入一个elem拷贝，传回新数据位置
c.insert(pos,n,elem) 在pos位置插入>n个elem数据。无返回值
c.insert(pos,beg,end) 在pos位置插入在[beg,end)区间的数据。无返回值
c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.pop_front() 删除头部数据。
c.push_back(elem) 在尾部加入一个数据。
c.push_front(elem) 在头部插入一个数据。
c.rbegin() 传回一个逆向队列的第一个数据。
c.rend() 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) 重新指定队列的长度。
c.size() 返回容器中实际数据的个数。
我决对不是在水博客你们相信我啊！！！！！！

标准模板库中的双端队列[double-ended queue]是允许在两端访问的线性表，因此双端队列可以用双向链表实现。在STL中的容器list已经添加了双向链表，在STL在双端队列中添加了很多额外的功能，可以随机访问双端队列的``任意位置`。如同数组一样。不说了直接开始水一段代码！【雾】胜利的法则已经确定！！

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
int main(){
    deque<int>q1;
    q1.push_front(1);
    q1.push_front(2);
    q1.push_back(3);
    q1.push_back(4);//现在序列应该是2134;
    deque<int>q2(q1.begin()+1,q1.begin()-1);//13
    q1[1]=5;//现在是2534,我说过了完全可以当数组使
    q1.erase(q1.begin());//534
    q1.insert(q1.end()-1,2,6);//53664
    sort(q1.begin(),q1.end());//34566
    deque<int>q3;
    q3.resize(q1.size()+q2.size());//q3={0,0,0,0,0,0,0}
    merge(q1.begin(),q1.end(),q2.begin(),q2.end(),q3.begin());//1334566
        system("pause");
    return 0;
}

虽然有点突然但大概就那么多吧。好了大概就那么多吧，emmmmm我想想还有什么要说的吗emmmmmm估计没了，在写下去水博客就实锤了！！！！还有我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客我没有水博客

你们相信我啊！！！！