精华内容
下载资源
问答
  • 一、实验目的1.掌握队列的链接存储结构—链队列以及顺序存储结构—顺序队列2.验证链队列的存储结构基本的实现3.验证队列的操作特性。二、实验内容1....2.算法设计链队列验证实验#ifndef LinkQueue_H#...

    一、实验目的

    1.掌握队列的链接存储结构—链队列以及顺序存储结构—顺序队列

    2.验证链队列的存储结构和基本的实现

    3.验证队列的操作特性。

    二、实验内容

    1.建立一个空队列

    2.对已建立的队列进行插入、删除、取队头元素等操作

    三、设计与编码

    1.理论知识

    定义链队列和顺序队列的数据类型如入队出队去队头等操作,利用了队列元素的线性关系和先进先出的特性。

    2.算法设计

    链队列验证实验

    #ifndef LinkQueue_H

    #define LinkQueue_H

     

    template<class DataType>

    struct Node

    {

           DataTypedata;

           Node<DataType>*next;

    };

     

    template<class DataType>

    class LinkQueue

    {

     

    public:

           LinkQueue();

           ~LinkQueue();

           voidEnQueue(DataType x);

           DataTypeDeQueue();

           DataTypeGetQueue();

           intEmpty();

    private:

           Node<DataType>*front,*rear;

    };

    #endif;

     

    #include"LinkQueue.h"

    template<class DataType>

    LinkQueue<DataType>::LinkQueue()

    {

           Node<DataType>*s=NULL;

           s=newNode<DataType>;

           s->next=NULL;

           front=rear=s;

    }

     

    template<class DataType>

    LinkQueue<DataType>::~LinkQueue()

    {

           Node<DataType>*p=NULL;

           while(front!=NULL)

           {

                  p=front->next;

                  deletefront;

                  front=p;

           }

    }

     

    template<class DataType>

    void LinkQueue<DataType>::EnQueue(DataTypex)

    {

           Node<DataType>*s=NULL;

           s=newNode<DataType>;

           s->data=x;

           s->next=NULL;

           rear->next=s;rear=s;

    }

     

    template<class DataType>

    DataTypeLinkQueue<DataType>::DeQueue()

    {

           Node<DataType>*p=NULL;

           intx;

           if(rear==front)throw"下溢";

           p=front->next;

           x=p->data;

           front->next=p->next;

           if(p->next==NULL)rear=front;

           deletep;

           returnx;

    }

    template<class DataType>

    DataTypeLinkQueue<DataType>::GetQueue()

    {

           if(front!=rear)

                  returnfront->next->data;

    }

     

    template<class DataType>

    int LinkQueue<DataType>::Empty()

    {

           if(front==rear)

                  return1;

           else

                  return0;

    }

     

    #include<iostream>

    using namespace std;

    #include"LinkQueue.cpp"

     

    void main()

    {

           LinkQueue<int>.Q;

           if(Q.Empty())

                  cout<<"队列已空"<<endl;

           else

                  cout<<"队列非空"<<endl;

           cout<<"元素100,32,69执行入队操作"<<endl;

           try

           {

                  Q.EnQueue(100);

                  Q.EnQueue(32);

                  Q.EnQueue(69);

           }

           catch(char*wrong)

           {

                  cout<<wrong<<endl;

           }

           cout<<"查看队头元素"<<endl;

           cout<<Q.GetQueue()<<endl;

           cout<<"执行出队操作,并将23入队"<<endl;

           try

           {

                  Q.DeQueue();

                  Q.EnQueue(23);

           }

           catch(char*wrong)

           {

                  cout<<wrong<<endl;

           }

           cout<<"查看队头元素"<<endl;

           cout<<Q.GetQueue()<<endl;

    }

    顺序队列验证实验

    #include <iostream> 

    using namespace std; 

     

    template <class DataType> 

    class Queue{ 

       private: 

           int front; 

           int rear;  

           int MaxSize;  

           DataType *data; 

           int number; 

       public: 

           Queue(int max=10):MaxSize(max)

                  {   

               front=0;    

               rear=0; 

               number=0; 

               data = new DataType[MaxSize]; 

           } 

           ~Queue(){  

               delete [] data;   

           } 

           void EnQueue(DataType x);

           void DeQueue();    

           DataType GetQueue() const;   

            int getLength() const; 

           bool Full() const;   

           bool Empty() const; 

           void Display() const; 

    }; 

     

    template <class DataType> 

    voidQueue<DataType>::EnQueue(DataType x)

    {  

       data[rear]=x; 

       rear=(rear+1)%MaxSize; 

        number++; 

     

    template <class DataType> 

    void Queue<DataType>::DeQueue()

       front=(front+1)%MaxSize; 

       number--; 

     

    template <class DataType> 

    DataType Queue<DataType>::GetQueue()const

    {

       return data[front]; 

     

    template <class DataType> 

    int Queue<DataType>::getLength()const

    {

       return number; 

     

    template <class DataType> 

    bool Queue<DataType>::Full()const

       return number==MaxSize; 

     

    template <class DataType> 

    bool Queue<DataType>::Empty()const

    {

        return number==0; 

     

    template <class DataType> 

    void Queue<DataType>::Display() const

       int p = front; 

       int i=1; 

       while(p!=rear)

           { 

           cout<<"第"<<i<<"元素:"<<data[p]<<endl; 

           i++; 

           p = (p+1)%MaxSize; 

        } 

     

    void main(){ 

       Queue<int> *a = new Queue<int>(5); 

       cout<<"队列是否为空:"<<a->Empty()<<endl; 

           cout<<"输入元素9,65,69,47,56"<<endl;

       a->EnQueue(9); 

       a->EnQueue(65);

       a->EnQueue(69);   

       a->EnQueue(47);   

       a->EnQueue(56);    

           a->Display();

       cout<<"队列是否已满:"<<a->Full()<<endl;   

       cout<<"队列元素个数:"<<a->getLength()<<endl; 

           cout<<"第一个元素出队"<<endl;

       a->DeQueue(); 

       cout<<"队列元素个数:"<<a->getLength()<<endl<<endl; 

       a->Display();  

    }  

    四、运行与调试

    1.遇到问题为如何建立链队列的指针以及出队入队操作,通过查阅书本

    2.测试结果如上。

    展开全文
  • 队列 - 队列的创建基本操作

    千次阅读 2018-03-22 17:45:43
    队列 / 列队 Queue //二叉树 typedef struct Tree{ int val; Tree *left; Tree *right; //Tree(int v):val(v){} }*P_Tree; //队列 typedef P_Tree Elem; //以二叉树作为列队结点元素 struct Node{ Elem Data...

    队列 / 列队 Queue

    //二叉树
    typedef struct Tree{
        int val;
        Tree *left;
        Tree *right;
        //Tree(int v):val(v){}
    }*P_Tree;
    
    //队列
    typedef P_Tree Elem;    //以二叉树作为列队结点元素
    struct Node{
        Elem Data;
        struct Node *Next;  //下一个进来的结点
    };
    struct QNode{
        struct Node *rear;  //列队尾(push)
        struct Node *front; //列队头(pop)
    };
    typedef struct QNode* Queue;
    
    Queue createQueue(){
        Queue queue=(Queue)malloc(sizeof(QNode));
        queue->rear=NULL;
        queue->front=NULL;
        return queue;
    }
    
    int isEmpty(Queue Q){
        //如果队列不为空,则其对头和对尾会指向某个结点
        return (Q->front == NULL);
    }
    
    //对尾(rear)push
    void push(Elem item,Queue queue){
        Node *next;
        next=(Node*)malloc(sizeof(Node));
        next->Data=item;
        next->Next=NULL;
    
        if(isEmpty(queue)){
            queue->front=next;
            queue->rear=next;
        }else{
            queue->rear->Next=next;
            queue->rear=next;
        }
    }
    
    //队头(front)pop
    Elem pop(Queue queue){
        struct Node *node;
        Elem item;
    
        if(isEmpty(queue)){
            cout << "队列空" << endl;
            return NULL;
        }
    
        node=queue->front;
    
        if(queue->front == queue->rear){
            queue->front=NULL;
            queue->rear=NULL;
        }else{
            queue->front=queue->front->Next;
        }
    
        item=node->Data;
        free(node);
        return item;
    }

     

    展开全文
  • 1、实验题目:队列操作的验证及应用 2、实验目的:加深理解循环队列的定义;掌握顺序循环队列的表示与实现。 3、实验内容: 设有N个人站成一排,从左到右的编号分别为1——N,现在从左往右报数“1,2,3,1,2,3。...
  • 基于深度学习算法开发和验证的肝细胞癌预后预测模型:一项大样本队列和外部验证研究.pdf
  • 实验六 栈队列的实现 一实验目的 通过实验掌握队列的逻辑结构特点 掌握队列的初始化入队出队取队首元素等基本操作算法 二实验内容 利用队列模拟银行办理业务时系统叫号客户等待接受服务的过程
  • 和队列的操作

    2019-03-07 10:23:53
    实验三 栈和队列的操作 ...3)验证和队列的基本操作实现。 2. 实验内容: 1)编程实现栈的以下基本操作:建栈,取栈顶元素,入栈,出栈。 2)编程实现队列的以下基本操作:建队,取队头元素,入队,出队。
  • 该用户已经存在 新增的id 入另一种详情表 问题所在: 当用户因特殊情况清除缓存 导致app 发送json串 入库并发高 导致CPU 暴增到88% 并且居高不下 优化思路: 1、异步队列处理 2、redis 过滤(就是只处理当天第一...
  • 队列相关算法

    2019-08-25 14:12:59
    2、实验验证如下算法的正确性、各种功能及指标: 1)创建队列; 2)插入操作:向队尾插入值为x的元素; 3)删除操作:删除队首元素; 4)存取操作:读取队首元素。 3、为便于观察程序的运行结果,设计的输出函数能在...
  • 2.7 队列的应用 三、总结 在日常的学习以及求职面试中,栈和队列是一块非常重要的内容,经常被提及,本篇文章总结了栈和队列基本概念及常用操作,并且分别使用数组链表实现了栈和队列,简单易懂,想不会都难!...

    🎈 作者:Linux猿

    🎈 简介:CSDN博客专家🏆,华为云享专家🏆,数据结构和算法、C/C++、面试、刷题尽管咨询我,关注我,有问题私聊!

    🎈 关注专栏:动图讲解数据结构和算法(优质好文持续更新中……)🚀

    🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


    目录

    一、栈

    1.1 什么是栈

    1.2 实现方式

    1.3 数组实现栈

    1.3.0 类封装

    1.3.1 push 操作

    1.3.2 pop 操作

    1.3.3 empty 操作

    1.3.4 top 操作

    1.3.5 size 操作

    1.3.6 数组栈测试

    1.4 链表实现栈

    1.4.0 类封装

    1.4.1 push 操作

    1.4.2 pop 操作

    1.4.3 empty 操作

    1.4.4 top 操作

    1.4.5 size 操作

    1.4.6 链表栈测试

    1.5 实战分析

    1.6 复杂度分析

    1.6.1 时间复杂度

    1.6.2 空间复杂度

    1.7 栈的应用

    二、队列

    2.1 什么是队列

    2.2 实现方式

    2.3 数组实现队列

    2.3.0 类封装

    2.3.1 push 操作

    2.3.2 pop 操作

    2.3.3 front 操作

    2.3.4 empty 操作

    2.3.5 size 操作

    2.3.6 back 操作

    2.3.7 数组队列测试

    2.4 链表实现队列

    2.4.0 类封装

    2.4.1 push 操作

    2.4.2 pop 操作

    2.4.3 front 操作

    2.4.4 empty 操作

    2.4.5 size 操作

    2.4.6 链表队列测试

    2.5 实战分析

    2.6 复杂度分析

     2.6.1 时间复杂度

    2.6.2 空间复杂度

    2.7 队列的应用

    三、总结


    在日常的学习以及求职面试中,栈和队列是一块非常重要的内容,经常被提及,本篇文章总结了栈和队列基本概念及常用操作,并且分别使用数组和链表实现了栈和队列,简单易懂,想不会都难!赶紧来看下吧!

    一、栈

    1.1 什么是栈

    栈是一种抽象数据结构,也是一种线性数据结构,具有后进先出(LIFO,Last In First Out)的特性,即:后进入栈中的元素在先进入元素的上面,故后进入栈中的元素先出栈,当然也可以说是先进后出,即:先进入的元素后出栈,一样的原理,只是说法不同。如下图所示:

     从上图可以看到,栈只有一个口,即是入口也是出口,后进入栈的元素 C,比先进入栈的 B 和 A 先出栈,这就是所谓的后进先出。如上图所示,栈有栈顶和栈底。

    来看一下动图,如下所示:

    标题

    1.2 实现方式

    栈的实现可以通过数组或链表来实现,如下图所示:

    标题
    标题

     下面分别来看一下数组和链表来实现栈。

    1.3 数组实现栈

    1.3.0 类封装

    下面用类封装了栈的常用操作,如下所示:

    #define NUM 100000 // 栈的大小
    class Stack {
        int data[NUM];  // 数组模拟栈
        int num;    // 栈指针,指向栈顶元素
    public:
        Stack() {   // 初始化
            num = -1;
            memset(data, 0, sizeof(data));
        }
        void push(int val); // 添加元素
        int pop();          // 删除栈顶元素
        int top();          // 返回栈顶元素
        bool empty();       // 判断是否为空
        int size();         // 栈大小
    };

    上面是以 int 为例子,更好的封装是使用 C++ 的模板,这里为了便于理解采用了更简单的方式。

    另一方面,数组还可以改成动态分配的形式,即:先分配一个初始数组,如果栈溢出了,则重新分配,将原先的内容拷贝到新分配的数组中,分配的方式可以参考 STL 的递增策略。

    1.3.1 push 操作

    向栈中添加元素,如下所示:

    void Stack::push(int val) {
        if(num >= NUM) {
            cout<<"Stack Overflow!"<<endl;
            return;
        }
        data[++num] = val;
    }

    如上所示,先判断栈是否已满,未满则添加元素。可以将上面的 if 语句里的内容修改为增加栈容量。

    1.3.2 pop 操作

    删除栈顶元素,因为栈是后进先出的,如下所示:

    int Stack::pop() {
        if(empty()) {
            cout<<"Stack Empty!"<<endl;
            return -1;
        }
        return data[num--];
    }

    如上所示,先判断栈是否为空,不空则删除栈顶元素,只要栈顶指针移动即可。

    1.3.3 empty 操作

    判断栈是否为空,空返回 true,否则返回 false ,如下所示:

    bool Stack::empty() {
        return num == -1;
    }

    这里也许有人会说“为啥不用 int 类型,返回 0 和 1 呢? 用 true 和 false 更好是因为 bool 类型占一个字节,而 int 通常占 4 个字节。

    1.3.4 top 操作

    返回栈顶元素,如下所示:

    int Stack::top() {
        if(empty()) {
            cout<<"Stack Empty!"<<endl;
            return -1;
        }
        return data[num];
    }

    先判断栈是否为空,如果非空则返回栈顶元素。

    注意:这里不是删除,仅仅是返回栈顶元素的值。

    1.3.5 size 操作

    返回栈大小,如下所示:

    int Stack::size() {
        return num + 1;
    }

    栈指针 num 是从 0 开始的,故返回 num+1。

    1.3.6 数组栈测试

    下面是测试上面的数组栈实现,如下所示:

    int main()
    {
        Stack st;
    
        st.push(10);
        st.push(20);
        cout<<"The size of stack is "<<st.size()<<endl;
        cout<<"The top of stack is "<<st.top()<<endl;
        cout<<"The stack empty is "<<st.empty()<<endl;
        cout<<"----------------------------------------"<<endl;
    
        st.pop();
        cout<<"The size of stack is "<<st.size()<<endl;
        cout<<"The top of stack is "<<st.top()<<endl;
        cout<<"----------------------------------------"<<endl;
        return 0;
    }

    输出为:

    The size of stack is 2
    The top of stack is 20
    The stack empty is 0
    ----------------------------------------
    The size of stack is 1
    The top of stack is 10
    ----------------------------------------

    1.4 链表实现栈

    1.4.0 类封装

    使用类封装栈,如下所示:

    struct node { // 链表单个节点
        int val;  // 存储栈元素值
        struct node* next;// 指向下一个元素的指针
        node(int value) { // 赋初值
            val = value;
        }
    };
    
    class Stack {
        struct node *index; // 指向栈顶元素
        int s_size; // 记录栈容量
    public:
        Stack() { // 初始化
            index = nullptr;
            s_size = 0;
        }
        ~Stack() ;
        void push(int val); // 添加元素
        int pop();          // 删除栈顶元素
        int top();          // 返回栈顶元素
        bool empty();       // 判断是否为空
        int size();         // 栈大小
    };

    struce node 是链表中的单个元素, class Stack 包含栈的各种操作,这里使用 s_size 记录栈的容量,便于操作。当然,这里是以 int 为例,可以将其修改为 C++ 的模板形式。

    1.4.1 push 操作

    向栈中添加元素,如下所示:

    void Stack::push(int val) {
        struct node* tmp = new node(val);
        if(tmp == nullptr) {
            cout<<"Failed to allocate space!"<<endl;
            return;
        }
        tmp->next = index;
        index = tmp;
        s_size++;
    }

    如上所示,这里不用判断栈是否已满,需要判断一个是否分配成功。

    1.4.2 pop 操作

    删除栈顶元素,因为栈是后进先出的,如下所示:

    int Stack::pop() {
        if(empty()) {
            cout<<"Stack Empty!"<<endl;
            return -1;
        }
        int tmpVal = index->val; // 暂存栈顶元素
        index = index->next; // 删除栈顶元素
        s_size--;            // 栈元素个数减一
        return tmpVal; // 这个返回下栈顶元素
    }

    如上所示,先判断栈是否为空,不空则删除栈顶元素,只要栈顶指针移动即可。

    1.4.3 empty 操作

    判断栈是否为空,空返回 true,否则返回 false ,如下所示:

    bool Stack::empty() {
        return index == nullptr;
    }

    1.4.4 top 操作

    返回栈顶元素,如下所示:

    int Stack::top() {
        if(empty()) {
            cout<<"Stack Empty!"<<endl;
            return -1;
        }
        return index->val; // 仅仅返回栈顶元素
    }

    因为 index 一直指向栈顶元素,所以直接返回 index->val。

    1.4.5 size 操作

    返回栈大小,如下所示:

    int Stack::size() {
        return s_size;
    }

    这里使用 s_size 记录栈大小,不然每次都要遍历链表。

    1.4.6 链表栈测试

    下面是测试上面的链表栈实现,如下所示:

    int main()
    {
        Stack st;
    
        st.push(10);
        st.push(20);
        cout<<"The size of stack is "<<st.size()<<endl;
        cout<<"The top of stack is "<<st.top()<<endl;
        cout<<"The stack empty is "<<st.empty()<<endl;
        cout<<"----------------------------------------"<<endl;
    
        st.pop();
        cout<<"The size of stack is "<<st.size()<<endl;
        cout<<"The top of stack is "<<st.top()<<endl;
        cout<<"----------------------------------------"<<endl;
        return 0;
    }
    

    输出为:

    linuxy@linuxy:~/Stack$ g++ -o main Stack.cpp 
    linuxy@linuxy:~/Stack$ ./main 
    The size of stack is 2
    The top of stack is 20
    The stack empty is 0
    ----------------------------------------
    The size of stack is 1
    The top of stack is 10
    ----------------------------------------
    linuxy@linuxy:~/Stack$ 

    1.5 实战分析

    模拟元素栈操作,如何实现从下面的入栈顺序到出栈顺序。

    入栈顺序:A B C D

    出栈顺序:C B D A

    如上所示,需要找到一种方法,实现从入站次序到出站次序,这是栈经常考的题目,步骤如下:

    (1)因为第一个出站的是 C,所以 A,B ,C依次入栈;

    (2)这时,C 在栈顶,C 出栈;

    (3)因为第二个出栈的是 B,当前栈顶为 B,所以直接让 B 出栈;

    (4)B 出栈后,当前栈顶为 A,但是,应该是 D 出栈,所以先让 D 进栈;

    (5)当前栈顶为 D,下一个出栈元素为 D,让 D 出栈;

    (6)当前栈顶元素为 A,下一个出栈元素对应 A,所以 A 出栈;

    下面来看下动图:

    1.6 复杂度分析

    1.6.1 时间复杂度

    不管是链表实现的栈,还是数组实现的栈,push 和 pop 操作的时间复杂度都是O(1)的,链表实现的栈中 clear 操作是O(n)的,因为需要释放所有的链表空间,其它操作都是O(1)的。

    1.6.2 空间复杂度

    链表相对于数组更节省空间,因为链表使用到才会分配,数组是提前分配好,而且如果栈满时,数组还需要重新分配。

    1.7 栈的应用

    (1)深度优先搜索

    深度优先搜索的非递归实现通常使用栈作为辅助的数组结构。

    (2)软件中的回退和前进功能

    (3)拓扑排序

    二、队列

    2.1 什么是队列

    队列是一种线性结构的抽象数据类型,可以实现先进先出(FIFO,First In,First Out),即:先进入的元素,先出队列,可以比喻为日常排队买东西。

    如下图所示:

    标题

    从上图可以看到,队列和栈不同,队列有两个口,而且是一个只允许进入元素,一个只允许出元素,后进入栈的元素C,比先进入栈的 B 和 A 先出栈,这就是所谓的后进先出。如上图所示,栈有栈顶和栈底。

    来看一下动图,如下所示:

    标题

    2.2 实现方式

    队列的实现可以通过数组或链表来实现,如下图所示:

    标题
    标题

    2.3 数组实现队列

    2.3.0 类封装

    下面是使用类封装了队列,如下所示:

    #define NUM 100000 // 队列大小
    class Queue {
        int data[NUM];  // 数组模拟队列
        int first;      // 头指针,指向队列顶部
        int last;       // 尾指针,指向队列尾部
    public:
        Queue() {   // 初始化
            first = 0;
            last = 0;
            memset(data, 0, sizeof(data));
        }
        void push(int val); // 添加元素
        int pop();          // 删除队列头元素
        int front();        // 返回队列头元素
        bool empty();       // 判断是否为空
        int size();         // 队列大小
        int back();         // 返回队列尾元素
    };

    data 存储队列数据,first 和 last 分别指向队列头部和尾部。

    2.3.1 push 操作

    向队列中添加元素,如下所示:

    void Queue::push(int val) {
        if(last >= NUM) {
            cout<<"Queue Overflow!"<<endl;
            return;
        }
        data[last++] = val;
    }

    先判断队列是否已满,未满则添加元素,添加元素只需要移动尾指针即可。

    2.3.2 pop 操作

    删除队列头元素,如下所示:

    int Queue::pop() {
        if(empty()) {
            cout<<"Queue Empty!"<<endl;
            return -1;
        }
        return data[first++];
    }

    如上所示,先判断队列是否为空,不空则删除队列头元素,只需要头指针 first 移动即可。

    2.3.3 front 操作

    返回头元素的值,和栈的 top 操作相同的原理,如下所示:

    int Queue::front() {
        if(empty()) {
            cout<<"Queue Empty!"<<endl;
            return -1;
        }
        return data[first];
    }

    先判断队列是否为空,非空则返回头元素。

    2.3.4 empty 操作

    判断队列是否为空,如下所示:

    bool Queue::empty() {
        return first == last;
    }

    直接比较 first 与 last 是否相等即可。

    2.3.5 size 操作

    判断队列元素个数,如下所示:

    int Queue::size() {
        return last - first;
    }

    使用队列尾指针与头指针之前的举例便是元素个数。

    2.3.6 back 操作

    返回队列尾元素,如下所示:

    int Queue::back() {
        if(empty()) {
            cout<<"Queue Empty!"<<endl;
            return -1;
        }
        return data[last-1];
    }

    先判断是否为空,不为空则返回 last - 1 所在的元素,因为 last 指向尾元素的下一个位置。

    2.3.7 数组队列测试

    下面是对上面数组实现的队列的测试,如下所示:

    int main()
    {
        Queue que;
    
        cout<<"The queue empty is "<<que.empty()<<endl;
        cout<<"The size of queue is "<<que.size()<<endl;
        cout<<"----------------------------------------"<<endl;
        que.push(10);
        que.push(20);
        cout<<"The size of queue is "<<que.size()<<endl;
        cout<<"The front of queue is "<<que.front()<<endl;
        cout<<"The queue empty is "<<que.empty()<<endl;
        cout<<"----------------------------------------"<<endl;
    
        que.pop();
        cout<<"The size of queue is "<<que.size()<<endl;
        cout<<"The front of queue is "<<que.front()<<endl;
    
        return 0;
    }

    输出为:

    linuxy@linuxy:~/Stack$ ./main 
    The queue empty is 1
    The size of queue is 0
    ----------------------------------------
    The size of queue is 2
    The front of queue is 10
    The queue empty is 0
    ----------------------------------------
    The size of queue is 1
    The front of queue is 20
    linuxy@linuxy:~/Stack$

    2.4 链表实现队列

    2.4.0 类封装

    struct node {   // 链表节点
        int val;    // 链表值
        struct node* next;
        node(int value) {
            val = value;
        }
    };
    
    class Queue {
        struct node *first; // 指向队列头元素
        struct node *rear;  // 指向队列尾元素
        int s_size;         // 记录队列元素个数
    public:
        Queue() { // 初始化
            first = nullptr;
            rear = nullptr;
            s_size = 0;
        }
        ~Queue();
        void push(int val);  // 添加元素
        int pop();           // 删除队列头元素
        int front();         // 返回队列头元素
        bool empty();        // 判断是否为空
        int size();          // 队列元素个数
        void back();         // 返回队列尾元素
    };

    first 指向队列头元素,rear 指向队列尾元素,s_size 记录队列中的元素个数。

    2.4.1 push 操作

    向队列中添加元素,添加到队列尾部,因为队列是先进先出,如下所示:

    void Queue::push(int val) {
        struct node* tmp = new node(val);
        if(tmp == nullptr) {
            cout<<"Failed to allocate space!"<<endl;
            return;
        }
        if(rear == nullptr) { // 添加第一个元素
            first = tmp;
            rear = tmp;
            tmp->next = nullptr;
        } else {              // 已有元素
            rear->next = tmp;
            tmp->next = nullptr;
            rear = tmp;
        }
    
        s_size++;
    }

    这里需要先分配空间,第一次添加元素需要将 first 和 rear 都指向该元素,否则添加到尾部即可,别忘记增加 s_size。

    2.4.2 pop 操作

    删除队列头元素,如下所示:

    int Queue::pop() {
        if(empty()) {
            cout<<"Stack Empty!"<<endl;
            return -1;
        }
        struct node* tmp = first;
        first = first->next;
        int val = tmp->val;
        delete tmp;
    
        s_size--;
        return val;
    }

    先判断队列是否为空,不为空则移动队列头指针,别忘记释放空间。

    2.4.3 front 操作

    返回队列头元素的值,并不是删除哦!如下所示:

    int Queue::front() {
        if(empty()) {
            cout<<"Stack Empty!"<<endl;
            return -1;
        }
        return first->val;
    }

    队列的 front 和 栈的 top 原理类似。

    2.4.4 empty 操作

    判断队列是否为空,如下所示:

    bool Queue::empty() {
        return first == nullptr;
    }

    2.4.5 size 操作

    判断队列元素个数,如下所示:

    int Queue::size() {
        return s_size;
    }

    这里使用了一个辅助变量 s_size,不然每次求队列元素个数都需要遍历一次链表。

    2.4.6 链表队列测试

    下面是测试上面的链表队列的实现,如下所示:

    int main()
    {
        Queue que;
    
        cout<<"The queue empty is "<<que.empty()<<endl;
        cout<<"The size of queue is "<<que.size()<<endl;
        cout<<"----------------------------------------"<<endl;
    
        que.push(10);
        que.push(20);
        cout<<"The size of queue is "<<que.size()<<endl;
        cout<<"The top of queue is "<<que.front()<<endl;
        cout<<"The queue empty is "<<que.empty()<<endl;
        cout<<"----------------------------------------"<<endl;
    
        que.pop();
        cout<<"The size of queue is "<<que.size()<<endl;
        cout<<"The top of queue is "<<que.front()<<endl;
        cout<<"----------------------------------------"<<endl;
    
        return 0;
    }

    输出结果为:

    linuxy@linuxy:~/Queue$ ./main 
    The queue empty is 1
    The size of queue is 0
    ----------------------------------------
    The size of queue is 2
    The top of queue is 10
    The queue empty is 0
    ----------------------------------------
    The size of queue is 1
    The top of queue is 20
    ----------------------------------------
    linuxy@linuxy:~/Queue$

    2.5 实战分析

    采用层次遍历的方法遍历如下二叉树:

    标题

    层次遍历上图的二叉树,即:从上到下一层一层的遍历二叉树的节点,按照这个思路,遍历步骤为:

    (1)先访问 1 节点,1节点有两个孩子节点,1 节点出队列后,将 2 和 3 两个节点入队;

    (2)访问 2 节点,2 节点出队,2 节点有两个子节点 4 和 5,2 节点出队后,4 和 5 节点入队;

    (3)访问 3 节点,3 节点没有子节点,直接出队;

    (4)依次访问 4  和 5 节点,这两个节点都没有子节点,所以出队即可。

    (5)所有节点按照层次遍历的方式访问完毕!

    来看一下动图:

    标题

    2.6 复杂度分析

     2.6.1 时间复杂度

    不管是链表实现的队列,还是数组实现的队列,push、pop、empty、front 等操作的时间复杂度都是O(1)的。

    2.6.2 空间复杂度

    链表相对于数组更节省空间,因为链表使用到才会分配,数组是提前分配好,而且如果队列满时,数组还需要重新分配。

    2.7 队列的应用

    (1)广度优先搜索

    广度优先搜索的实现通常使用队列作为辅助的数组结构。

    (2)在一些资源请求或任务调度中,往往是先来先处理。

    三、LeetCode 题目

     下面列出了 LeetCode 栈和队列的题目,赶紧来练习下吧!

    (1)20. 有效的括号

    (2)84. 柱状图中最大的矩形

    (3)155. 最小栈

    (4)496. 下一个更大元素 I

    (5)503. 下一个更大元素 II

    (6)946. 验证栈序列

    (7)363. 矩形区域不超过 K 的最大数值和

    (8)621. 任务调度器

    四、总结

    栈和队列都有很强的特性,栈是后进先出,队列是先进先出,应用在不同的应用场景中。

      ⭐推荐阅读

    【数据结构和算法】超详细,超多图解,赫夫曼树详解

    【数据结构和算法】超详细,超多图解,树的各种概念汇总

    【数据结构和算法】衡量算法的标尺,时间和空间复杂度详解

    【数据结构和算法】超多图解,超详细,堆详解

    【数据结构和算法】二叉树详解,动图+实例

    【数据结构和算法】动图演示,超详细,就怕你不会,二分查找详解

    【数据结构和算法】动图+万字,详解栈和队列(实例讲解)

    【数据结构和算法】动图详解,链表(单链表/双链表……)(实例讲解)

    【数据结构和算法】 万字整理,八大排序算法详解

    欢迎关注下方👇👇👇公众号👇👇👇,获取更多优质内容🤞(比心)!

    展开全文
  • 本来想采用最新版本的,一想到生产测试必须版本保持一致,不能随便升级,就只好去下载指定版本的rabbitmq的rpm。 RabbitMQ概念 Broker:消息中间件的服务节点,RabbitMQ的一个服务实例,也可以看做是RabbitMQ的...

    前言

    不知道说什么好,直接开始吧。本来想采用最新版本的,一想到生产和测试必须版本保持一致,不能随便升级,就只好去下载指定版本的rabbitmq的rpm。

    RabbitMQ概念

    Broker :消息中间件的服务节点,RabbitMQ的一个服务实例,也可以看做是RabbitMQ的一台服务器

    Queue 队列:用于存储消息。kafka不一样,它的消息存在在topic逻辑层面,而队列存储的只是topic中实际存储文件中的编译标识。多个消费者可以同时订阅一个队列,平均分摊(Round-robin轮询)处理消息

    Exchange 交换器:生产者将消息发送到交换器,由交换器路由到一个或者多个队列中

    • direct exchangequeue进行bingding时会设置相应的routingkey。生产者发送消息到交换器时会设定相应的routingkey,如果这两个routingkey相同,消息都会投放到绑定的队列上。

    • topic 和direct一样,但是支持routingkey的通配符模式,可以有通配符:* , #。 其中 * 表示匹配一个单词, #则表示匹配没有或者多个单词

    • fanout 直接将发送到该交换器的消息路由到它绑定的一个或者多个队列

    • header 根据添加的header来判断

      • x-match == all,匹配所有header

      • x-match == any, 只需要匹配其中的一个header的值

    Routingkey 路由键: 生产者将消息发给交换器的时候, 一般会指定一个 RoutingKey ,用 来指定这个消息的路由规则,而这个 RoutingKey 需要与交换器类型和绑定键 (BindingKey) 合起来使用才能最终生效。在交换器类型和绑定键 (BindingKey) 固定的情况下,生产者可以在发送消息给交换器时, 通过指定 RoutingKey 来决定消息流向哪里

    Bindingkey 绑定:通过绑定将交换器与队列关联起来,在绑定的时候一般会指定一绑定键 BindingKey ,这样 RabbitMQ 就知何正确将消息路由到队列了。BindingKey只针对特定交换器才有效。

    Producer:消息生产者

    Consumer:消息消费者

    安装条件

    环境

    Centos 7.4 3台虚机8c16g

    用户权限

    需要有sudo权限

    安装文件

    下载的文件统一在/home/lazasha/download目录下, rabbitmq和erlang对应的版本关系可以参考:

    https://www.rabbitmq.com/which-erlang.html

    epel: epel-release-7-12.noarch.rpm

    下载地址:https://mirrors.tuna.tsinghua.edu.cn/epel/7/x86_64/Packages/e/epel-release-7-12.noarch.rpm

    erlang:erlang-22.1.8-1.el7.x86_64.rpm

    下载地址:https://github.com/rabbitmq/erlang-rpm/releases

    rabbitmq: rabbitmq-server-3.8.2-1.el7.noarch.rpm

    下载地址:https://dl.bintray.com/rabbitmq/all/rabbitmq-server/3.8.2/

    key: rabbitmq-release-signing-key.asc (我好像后面没有用到)

    下载地址:https://github.com/rabbitmq/signing-keys/releases

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    步骤

    epel安装

    sudo yum -y install epel-release-7-12.noarch.rpm
    

    erlang安装

    sudo yum -y install erlang-22.1.8-1.el7.x86_64.rpm
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    检查是否安装成功:

    输入:erl
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    rabbitmq安装

    sudo yum -y install rabbitmq-server-3.8.2-1.el7.noarch.rpm 
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    验证是否成功:

    sudo systemctl start rabbitmq-server 
    sudo systemctl status rabbitmq-server
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    停止服务:

    sudo systemctl stop rabbitmq-server
    

    在他两台机器上同样操作. 服务缺省端口是5672.

    集群搭建

    在3台机器上/etc/hosts文件中添加IP和节点名称的对应

    10.156.13.92 lchod1392
    10.156.13.93 lchod1393
    10.156.13.94 lchod1394
    

    把lchod1392上的 cookie文件,赋值到lchod1393、lchod1394节点上,集群环境下各个节点的cookie必须一致。rpm安装的cookie 文件默认路 径为 /var/lib/rabbitmq/.erlang.cookie

    注意:.erlang.cookie可能有权限问题,可以使用下面的操作:

    sudo chmod -R 600 /var/lib/rabbitmq/.erlang.cookie
    

    注意: 拷贝到另外两台机器上后,不管怎么样执行一下下面的命令,改一下.erlang.cookie的owner:

    sudo chown -R rabbitmq:rabbitmq /var/lib/rabbitmq/.erlang.cookie
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    通过Rabbitmqctl来配置集群,集群内部通讯端口是25672

    1.首先启动3个节点上的RabbitMQ服务

    sudo systemctl start rabbitmq-server

    可以使用rabbitmqctl cluster_status 查看各个节点的集群状态

    2.以lchod1392为基准,将lchod1393、lchod1394加入到集群中,把3个节点都设置为硬盘节点了。

    lchod1393

        sudo rabbitmqctl stop_app                    //只关闭rabbitmq服务,不关闭erlang服务
        sudo rabbitmqctl reset                       //这个命令我在加集群时没有执行
        sudo rabbitmqctl join_cluster rabbit@lchod1392   //--ram这个参数是内存节点模式,不是就是硬盘节点
        sudo rabbitmqctl start_app
    

    lchod1394

        sudo rabbitmqctl stop_app                    //只关闭rabbitmq服务,不关闭erlang服务
        sudo rabbitmqctl reset                       //这个命令我在加集群时没有执行
        sudo rabbitmqctl join_cluster rabbit@lchod1392   //--ram这个参数是内存节点模式,不是就是硬盘节点
        sudo rabbitmqctl start_app
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    3.检查集群状态

    sudo rabbitmqctl cluster_status
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    注意点: 如果关闭了集群中的所有节点,确保启动时最后一个关闭的节点第一个启动,否则会有问题。

    创建远程访问用户

    sudo rabbitmqctl add_user rabbitmq ******
    sudo rabbitmqctl set_user_tags rabbitmq administrator
    sudo rabbitmqctl set_permissions -p "/" rabbitmq ".*" ".*" ".*"
    //查看新增加的用户
    sudo rabbitmqctl list_users
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    注意:不用在启动后台管理插件了,使用systemctl start rabbitmq-server就已经启动了,端口是15672

    Mirror Queue 镜像队列搭建

    针对每一个镜像队列都包含一个master节点 和 多个slave节点,需求确保队列的master节点均匀分散的落在集群的各个broker中。如果master不工作,那么假如镜像队列最早的salve升级为master.

    镜像队列的配置主要是通过添加相应的 Policy 来完成 :

    rabbitmqctl set_policy [-p vhost) [--priority
    priority) [--apply- to apply- to) {name) {pattern) {definition)
    

    definition 要包含 个部分 ha-mode、 ha-params、 ha-sync-mode

    • ha-mode 指明镜像队列的模式,有效值为 all/exactly/nodes默认为 all
          all 表示在集群中所有的节点上进行镜像
          exactly 表示在指定个数的节点上进行镜像,节点个数由 ha-params 指定;
          nodes 表示在指定节点上进行镜像,节点名称通ha-params 指定,节点的名称通常类似于 rabbit@hostname ,可以通过rabbitmqctl cluster status 命令查看到

    • ha-params 不同的 hamode 配置中需要用到的参数。

    • ha-sync-mode 队列中消息的同步方式,有效值为 automatic 、manual

     

    命令样例

    • 对队列名称以 queue_" 开头的所有队列进行镜像,并在集群的两个节点上完 成镜像

      rabbitmqctl set_policy --priority 0 --apply-to queues mirror_queue " ^queue_"
      ' {"ha-mode ":"exactly","ha-params ":2, "ha-sync-mode ": "automatic" }'
      
    • 对队列名称以 queue_" 开头的所有队列进行镜像,并在集群的所有节点上完 成镜像

      rabbitmqctl set_policy --priority 0 --apply-to queues mirror_queue " ^queue_"
      ' {"ha-mode ":"all","ha-sync-mode ":"automatic" }'
      

      rabbitmqctl set_policy ha-all “^” ‘{“ha-mode”:“all”}’ 可以把队列设置为镜像队列

    命令执行

       sudo rabbitmqctl set_policy --priority 0 --apply-to queues mirror_queue " ^queue_"
       ' {"ha-mode ":"all","ha-sync-mode ":"automatic" }'
    

    验证

    使用新建的rabbitmq用户从本机登录远程的机器

    lchod1392: 创建一个队列,以queue开头

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    lchod1393: 已经有了这个队列

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    lchod1394: 有了这个队列

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    队列知识

    mandatory、 immediate 参数 channel.basicPublish 方法中的两个参数

    • mandatory参数 mandatory 参数设为 true 时,交换器无法根据自身的类型和路由键找到一个符合条件 的队列,那么 RabbitMQ 会调用 Basic.Return 命令将消息返回给生产者 。当 mandatory 数设置为 false 时,出现上述情形,则消息直接被丢弃。那么生产者如何获取到没有被正确路由到合适队列的消息呢?这时候可以通过调用 channel.addReturnListener 来添加 ReturnListener 监昕器实现。

    • immediate参数 immediate 参数设为 true 时,如果交换器在将消息路由到队列时发现队列上并不存在 任何消费者,那么这条消息将不会存入队列中。当与路由键匹配所有队列都没有消费者时,该消息会通过 Basic.Return 返回至生产者。

    • 概括来说 mandatory 参数告诉服务器至少将该消息路由到一个队中, 将消息返 回给生产者。 imrnediate 参数告诉服务器 如果该消息关联的队列上有消费者, 立刻投递; 如果所有匹配的队列上都没有消费者,则直接将消息返还给生产者,不用将消息存入队列而等待消费者了。

    • RabbitMQ 3.0 版本开始去掉了对 immediate 参数的支持,对此RabbitMQ官方解释是 immediate 参数会影响镜像队列的性能,增加代码码复杂性,建议采用 TTL、 DLX 的方法

    TTL time to live 过期时间

    • 设置方式:通过队列属性设置,整个队列的消息都有同样的过期时间;也可以对单条消息单独设置,则一个队列中消息有不同的过期时间。如果两种都设置了,以时间小的为准

    • 设置队列消息的TTL代码

      Map<String,Object> argss = new HashMap<String, Object>();
      argss.put("x-message-ttl " , 5000);
      channel.queueDeclare(queueName , durable , exclusive , autoDelete , argss) ; 
      

      这种方式, 一旦消息过期,就会从队列中抹去

      针对每条消息设置 TTL 的方法是在 channel.basicPublish 方法中加入 expiration 的属性参数,单位为毫秒:

      AMQP.BasicProperties.Builder builder = new AMQP.BasicProperties.Builder();
      builder deliveryMode(2); 持久化消息
      builder expiration( 50000 );/ 设置 TTL=50000ms
      AMQP.BasicProperties properties = builder. build() ;
      channel.basicPublish(exchangeName , routingKey, mandatory, properties,
      "test ttl".getBytes());
      

      这种方式, 即使消息过期,也不会马上从队列中抹去,因为每条消息是否过期是在即将投递到消费者之前判定的

    • 如果不设置 TTL.则表示此消息不会过期 ;如果将 TTL 设置为 0,则表示除非此时可以直 接将消息投递到消费者,否则该消息会被立即丢弃

    • 设置队列的TTL

      通过 channel.queueDeclare 方法中的 expires 参数可以控制队列被自动删除前处于未使用状态的时间。未使用的意思是队列上没有任何的消费者,队列也没有被重新声明,并 且在过期时间段内也未调用过 Basic.Get 命令。

      Map<String , Object> args =口ew HashMap<String, Object>{) ;
      args . put( "x-expires" , 100000); 
      channel . queueDeclare("queuesleb " , false , false , false , args) ; 

    死信队列 DLX(Dead Letter Message) 当 消息在一个队列中变成死信 (dea message) 之后,它能被重新被发送到另一个交换器中,这个 交换器就是 DLX ,绑定 DLX 的队列就称之为死信队列。

    • 消息被拒绝 (Basic.Reject/Basic .Na ck) ,井且设置 requeue 参数为 false

    • 消息过期

    • 队列达到最大长度

    • 可以创建消费者监听这个队列的消息进行处理

    • 通过在 channel.queueDeclare 方法中设置 x-dead-letter-exchange 参数来为这 个队列添加 DLX

       

        channel.exchangeDeclare("dlx_exchange " , "direct "); // 创建 DLX: dlx_exchange
        Map<String, Object> args = new HashMap<String, Object>();
        args.put("x-dead-letter-exchange" , " dlx-exchange ");
        //为队列 myqueue 添加 DLX
        channel.queueDeclare("myqueue" , false , false , false , args); 
    
        //也可以为这个 DLX 指定路由键,如果没有特殊指定,则使用原队列的路由键, 如果指定了,则消费者需要使用
        //的路由键才能消费这个队列的消息:
        args.put("x-dead-letter-routing-key" , "dlx-routing-key"); 
    

    延迟队列

    • 场景:一个订单在30分钟内支付有效,否则自动取消

    • 利用上面的TTL和DLX来达到延迟队列的功能

    优先级队列

    通过设置队列的 x-max-priority 参数来实现:

        Map<String, Object> args = new HashMap<String, Object>() ;
        args.put( "x-max-priority" , 10) ;
        channel.queueDeclare( "queue.priority" , true , fa1se , false , args) ; 
    

    在生产者速度大于消费者速度且broker中有积压的消息的时候,才有效果

    持久化

    • 交换器的持久化、队列的持久化和消息的持久化 ,才能真正的持久化

    • 交换器的持久化:设置durable = true

    • 队列的持久化: durable = true

    • 消息的持久化:通过将消息的投递模式 (BasicPropertes 中的 deliveryMode 属性)设置为2( DeliveryMode.PERSISTENT) 即可实现消息的持久化 )

    发送方确认机制 publisher confirm

    publisher-confirms: true #确认消息是否到达broker服务器,也就是只确认是否正确到达exchange中即可,只要正确的到达exchange中,broker即可确认该消息返回给客户端

    ackpublisher-returns: true #确认消息是否正确到达queue,如果没有则触发,如果有则不触发

    ConfirmCallback接口用于实现消息发送到RabbitMQ交换器后接收ack回调。

        rabbitTemplate.setConfirmCallback((correlationData, ack, cause) -> {
                    if (ack) {
                        CorrelationDataEx c = (CorrelationDataEx)correlationData;
                        System.out.println("发送消息: " + c.getMsg());
                        System.out.println("HelloSender 消息发送成功 :" + correlationData.toString() );
                        /**
                         * 通过设置correlationData.id为业务主键,消息发送成功后去继续做候选业务。
                         */
                    } else {
                        System.out.println("HelloSender消息发送失败" + cause);
                    }
                });
    

    ReturnCallback接口用于实现消息发送到RabbitMQ交换器,但无相应队列与交换器绑定时的回调

         rabbitTemplate.setReturnCallback((message, replyCode, replyText, exchange, routingKey) -> {
                     //Users users1 = (Users)message.getBody().toString();
                     //String correlationId = message.getMessageProperties().getCorrelationId();
    
                     System.out.println("Message : " + new String(message.getBody()));
                     //System.out.println("Message : " + new String(message.getBody()));
                     System.out.println("replyCode : " + replyCode);
                     System.out.println("replyText : " + replyText);  //错误原因
                     System.out.println("exchange : " + exchange);
                     System.out.println("routingKey : " + routingKey);//queue名称
    
                 });
    

     

         /**
                  * CorrelationDataEx继承CorrelationData, 把需要发送消息的关键字段加入
                  * 这样confirmcallback可以返回带有关键字段的correlationData,我们可以通过这个来确定发送的是那条业务记录
                  */
                 CorrelationDataEx c = new CorrelationDataEx();
                 c.setId(users.getId().toString());
                 c.setMsg(users.toString());
    
                 /**
                  * 加上这个,可以从returncallback参数中读取发送的json消息,否则是二进制bytes
                  * 比如:如果returncallback触发,则表明消息没有投递到队列,则继续业务操作,比如将消息记录标志位未投递成功,记录投递次数
                  */
                 rabbitTemplate.setMessageConverter(new Jackson2JsonMessageConverter());
    
                 rabbitTemplate.convertAndSend(EXCHANGE, QUEUE_TWO_ROUTING, users, c);
    

    消息消费

    1.配置

            listener:
                  simple:
                    prefetch: 1               #设置一次处理一个消息
                    acknowledge-mode: manual  #设置消费端手动 ack
                    concurrency: 3            #设置同时有3个消费者消费,需要3个消费者实例
    

    2.代码

            @RabbitHandler
                @RabbitListener(queues = QUEUE_ONE_ROUTING) //containerFactory = "rabbitListenerContainerFactory", concurrency = "2")
                public void process(Users users, Channel channel, Message message) throws IOException {
                    System.out.println("HelloReceiver收到  : " + users.toString() + "收到时间" + new Date());
    
                    try {
                        //告诉服务器收到这条消息 已经被我消费了 可以在队列删掉 这样以后就不会再发了
                        // 否则消息服务器以为这条消息没处理掉 后续还会在发
                        channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
                        System.out.println("receiver success");
                    } catch (IOException e) {
                        e.printStackTrace();
                        //丢弃这条消息,则不会重新发送了
                        //channel.basicNack(message.getMessageProperties().getDeliveryTag(), false, false);
                        System.out.println("receiver fail");
                    }
                }
    

    验证

    创建消息生产者和消费者

    生产者

    集群配置:

        spring:
          application:
            name: rabbitmq-producer-demo
          rabbitmq:
            # 单点配置
            #host: localhost
            #port: 5672
            # 集群的配置
            addresses: 10.156.13.92:5672,10.156.13.93:5672,10.156.13.94:5672
            username: rabbitmq  #guest是缺省,只能localhost网络访问,要访问远程网络,需要创建用户
            password: 123456
            # 像mysql拥有数据库的概念并且可以指定用户对库和表等操作的权限。那RabbitMQ呢?RabbitMQ也有类似的权限管理。
            # 在RabbitMQ中可以虚拟消息服务器VirtualHost,每个VirtualHost相当于一个相对独立的RabbitMQ服务器,
            # 每个VirtualHost之间是相互隔离的。exchange、queue、message不能互通。 相当于mysql的db。
            # Virtual Name一般以/开头
            virtual-host: /
            # 确认消息是否正确到达queue,如果没有则触发,如果有则不触发
            publisher-returns: on
            # 确认消息是否到达broker服务器,也就是只确认是否正确到达exchange中即可,
            # 只要正确的到达exchange中,broker即可确认该消息返回给客户端ack
            # 如果是simple就不会回调
            publisher-confirm-type: correlated
            template:
              #设置为 on 后 消费者在消息没有被路由到合适队列情况下会被return监听,而不会自动删除
              mandatory: on
    

    队列设置: 设置了queue_sleb_accept队列

        @Configuration
        public class RabbitConfig {
            /**
             * 投保消息交换机的名字
             */
            public static final String EXCHANGE_SLEB_ACCEPT = "exchange_sleb_accept";
    
            /**
             * 投保消息队列
             */
            public static final String QUEUE_SLEB_ACCEPT = "queue_sleb_accept";
            /**
             * 投保消息路由键
             */
            public static final String ROUTING_KEY_ACCEPT = "routing_key_accept";
            /**
             *  投保消息死信交换机
             */
            public static final String DLX_EXCHANGE_SLEB_ACCEPT = "exchange_dlx_sleb_accept";
            /**
             * 投保消息死信队列
             */
            public static final String DLX_QUEUE_SLEB_ACCEPT = "queue_dlx_sleb_accept";
            /**
             *  常用交换器类型如下:
             *       Direct(DirectExchange):direct 类型的行为是"先匹配, 再投送".
             *       即在绑定时设定一个 routing_key, 消息的routing_key完全匹配时, 才会被交换器投送到绑定的队列中去。
             *       Topic(TopicExchange):按规则转发消息(最灵活)。
             *       Headers(HeadersExchange):设置header attribute参数类型的交换机。
             *       Fanout(FanoutExchange):转发消息到所有绑定队列。
             *
             * 下面都是采用direct, 必须严格匹配exchange和queue
             * 投保消息交换机
             */
            @Bean("slebAcceptExchange")
            DirectExchange slebAcceptExchange() {
                return ExchangeBuilder.directExchange(EXCHANGE_SLEB_ACCEPT).durable(true).build();
    
            }
            /**
             * 第二个参数 durable: 是否持久化,如果true,则此种队列叫持久化队列(Durable queues)。此队列会被存储在磁盘上,
             *                 当消息代理(broker)重启的时候,它依旧存在。没有被持久化的队列称作暂存队列(Transient queues)。
             * 第三个参数 execulusive: 表示此对应只能被当前创建的连接使用,而且当连接关闭后队列即被删除。此参考优先级高于durable
             * 第四个参数 autoDelete: 当没有生成者/消费者使用此队列时,此队列会被自动删除。(即当最后一个消费者退订后即被删除)
             *
             * 这儿是(queue)队列持久化(durable=true),exchange也需要持久化
             * ********************死信队列**********************************************************
             *            x-dead-letter-exchange    这里声明当前队列绑定的死信交换机
             *            x-dead-letter-routing-key  这里声明当前队列的死信路由key
             *            采用死信队列,才会用到下面的参数
             *            Map<String, Object> args = new HashMap<>(2);
             *            args.put("x-dead-letter-exchange", DLX_EXCHANGE_SLEB_ACCEPT);
             *            args.put("x-dead-letter-routing-key", ROUTING_KEY_ACCEPT);
             *            return QueueBuilder.durable(QUEUE_SLEB_ACCEPT).withArguments(args).build();
             * ********************死信队列**********************************************************
             * 投保消息队列
             */
            @Bean("slebAcceptQueue")
            public Queue slebAcceptQueue() {
                return QueueBuilder.durable(QUEUE_SLEB_ACCEPT).build();
            }
    
            /**
             * 交换机、队列、绑定
             */
            @Bean("bindingSlebAcceptExchange")
            Binding bindingSlebAcceptExchange(@Qualifier("slebAcceptQueue") Queue queue,
                                              @Qualifier("slebAcceptExchange") DirectExchange directExchange) {
                return BindingBuilder.bind(queue).to(directExchange).with(ROUTING_KEY_ACCEPT);
            }
            /**
             * 投保死信交换机
             */
            @Bean("slebDlxAcceptExchange")
            DirectExchange slebDlxAcceptExchange() {
                return ExchangeBuilder.directExchange(DLX_EXCHANGE_SLEB_ACCEPT).durable(true).build();
            }
            /**
             * 投保死信队列
             */
            @Bean("slebDlxAcceptQueue")
            public Queue slebDlxAcceptQueue() {
                return QueueBuilder.durable(DLX_QUEUE_SLEB_ACCEPT).build();
            }
            /**
             * 死信交换机、队列、绑定
             */
            @Bean("bindingDlxSlebAcceptExchange")
            Binding bindingDlxSlebAcceptExchange(@Qualifier("slebDlxAcceptQueue") Queue     queue, @Qualifier("slebDlxAcceptExchange") DirectExchange directExchange) {
                return BindingBuilder.bind(queue).to(directExchange).with(ROUTING_KEY_ACCEPT);
            }
    

    生产消息

        @Service
        public class AcceptProducerServiceImpl implements AcceptProducerService {
            private final Logger logger = LoggerFactory.getLogger(AcceptProducerServiceImpl.class);
    
    
            private final RabbitTemplate rabbitTemplate;
    
            public AcceptProducerServiceImpl(RabbitTemplate rabbitTemplate) {
                this.rabbitTemplate = rabbitTemplate;
            }
    
            @Override
            public void sendMessage(PolicyModal policyModal) {
                logger.info("开始发送时间: " + DateUtils.localDateTimeToString(LocalDateTime.now())
                        + ",保单号: " + policyModal.getPolicyNo()
                        + ",发送内容: " + policyModal.toString());
                /*
                 * policyDataEx继承CorrelationData, 把需要发送消息的关键字段加入
                 * 这样confirmcallback可以返回带有关键字段的correlationData,我们可以通过这个来确定发送的是那条业务记录
                 * policyno为唯一的值
                 */
                PolicyDataEx policyDataEx = new PolicyDataEx();
                policyDataEx.setId(policyModal.getPolicyNo());
                policyDataEx.setMessage(policyModal.toString());
    
                /*
                 * 加上这个,可以从returncallback参数中读取发送的json消息,否则是二进制bytes
                 * 比如:如果returncallback触发,则表明消息没有投递到队列,则继续业务操作,比如将消息记录标志位未投递成功,记录投递次数
                 */
                //rabbitTemplate.setMessageConverter(new Jackson2JsonMessageConverter());
                //PolicyModal类的全限名称(包名+类名)会带入到mq, 所以消费者服务一边必须有同样全限名称的类,否则接收会失败。
    
                rabbitTemplate.convertAndSend(RabbitConfig.EXCHANGE_SLEB_ACCEPT, RabbitConfig.ROUTING_KEY_ACCEPT, policyModal, policyDataEx);
    
            }
    

    运行验证

    http://localhost:9020/sendsing
    

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    查看3台服务器控制台:看到已经创建了镜像队列,并且有一个消息在队列里面:

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    消费者

    配置

        spring:
          application:
            name: rabbitmq-consumer-demo
          rabbitmq:
            # 单点配置
            #host: localhost
            #port: 5672
            # 集群的配置
            addresses: 10.156.13.92:5672,10.156.13.93:5672,10.156.13.94:5672
            username: rabbitmq
            password: 123456
            # 像mysql拥有数据库的概念并且可以指定用户对库和表等操作的权限。那RabbitMQ呢?RabbitMQ也有类似的权限管理。
            # 在RabbitMQ中可以虚拟消息服务器VirtualHost,每个VirtualHost相当于一个相对独立的RabbitMQ服务器,
            # 每个VirtualHost之间是相互隔离的。exchange、queue、message不能互通。 相当于mysql的db。
            # Virtual Name一般以/开头
            virtual-host: /
            listener:
              simple:
                prefetch: 1               #设置一次处理一个消息
                acknowledge-mode: manual  #设置消费端手动 ack
                concurrency: 3            #设置同时有3个消费者消费
                #消息接收确认,可选模式:NONE(不确认)、AUTO(自动确认)、MANUAL(手动确认)
    

    配置队列名称,主要名称和生产者里面的名称一样

        public class RabbitMQConfigInfo {
            /**
             * 投保消息队列
             */
            public static final String QUEUE_SLEB_ACCEPT = "queue_sleb_accept";
            /**
             * 投保消息交换机的名字
             */
            public static final String EXCHANGE_SLEB_ACCEPT = "exchange_sleb_accept";
    
            /**
             * 投保消息路由键
             */
            public static final String ROUTING_KEY_ACCEPT = "routing_key_accept";
        }
    

    消费

        @Service
        public class RabbitConsumerServiceImpl implements RabbitConsumerService {
    
            private final Logger logger = LoggerFactory.getLogger(RabbitConsumerServiceImpl.class);
    
            @RabbitHandler
            @RabbitListener(bindings = @QueueBinding(
                    value = @Queue(name = QUEUE_SLEB_ACCEPT, durable = "true"),
                    exchange = @Exchange(name = EXCHANGE_SLEB_ACCEPT,
                            ignoreDeclarationExceptions = "true"),
                    key = {ROUTING_KEY_ACCEPT}
            ))
            @Override
            public void process(Channel channel, Message message) throws IOException {
                String jsonStr = new String(message.getBody());
                logger.info("接收信息时间: " + DateUtils.localDateTimeToString(LocalDateTime.now())
                        + "n,消息:" + jsonStr);
                //PolicyModal类的全限名称(包名+类名)会带入到mq, 所以消费者服务一边必须有同样全限名称的类,否则接收会失败。
                PolicyModal policyModal = JsonUtils.JSON2Object(jsonStr, PolicyModal.class);
                assert policyModal != null;
                try {
                    //将message中的body获取出来, 转换为PolicyModal,再获取policyno
                    //更根据policyno新数据库里面的标志,
                    // todo
    
                    //告诉服务器收到这条消息 已经被我消费了 可以在队列删掉 这样以后就不会再发了
                    // 否则消息服务器以为这条消息没处理掉 后续还会在发
                    //throw new IOException("myself");
                    channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
                    /*logger.info("接收处理成功:n"
                            + "接收信息时间: " + DateUtils.localDateTimeToString(LocalDateTime.now())
                            + ",保单号: " + policyModal.getPolicyNo()
                            + "n,消息:" + new String(message.getBody()));
        */
                } catch (IOException e) {
                    e.printStackTrace();
                    //丢弃这条消息,则不会重新发送了
                    //一般不丢弃,超时后mq自动会转到死信队列(如果设置了超时时间和死信交换机和队列后)
                    //channel.basicNack(message.getMessageProperties().getDeliveryTag(), false, false);
                    logger.info("接收处理失败:n"
                            + "接收信息时间: " + DateUtils.localDateTimeToString(LocalDateTime.now())
                            + ",保单号: " + policyModal.getPolicyNo()
                            + "n,消息:" + new String(message.getBody()));
                }
            }
    
        }
    

    启动验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    在看各个服务器控制台:消息已经被消费,队列里面消息为0

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    结束

    技术文章难写,这个花了前后一个礼拜的时间,希望对大家有帮助。有要验证代码的,可以发邮件:lazasha@163.com联系我,我给你发。懒,没空上github,回来再说。

    END

    Java面试题专栏

    【30期】说一下HashMap的实现原理?

    【29期】Java集合框架 10 连问,你有被问过吗?

    【28期】ZooKeeper面试那些事儿

    【27期】Dubbo面试八连问,这些你都能答上来吗?

    【26期】如何判断一个对象是否存活?(或者GC对象的判定方法)?

    【25期】这三道常见的面试题,你有被问过吗?

    【24期】请你谈谈单例模式的优缺点,注意事项,使用场景

    【23期】请你谈谈关于IO同步、异步、阻塞、非阻塞的区别

    【22期】为什么需要消息队列?使用消息队列有什么好处?

    【21期】你能说说Java中Comparable和Comparator的区别吗

     

    带你从头进行RabbitMQ安装、集群搭建、镜像队列配置和代码验证

    展开全文
  • 掌握基于消息队列和共享内存的进程间通信原理 实验项目 基于消息队列和共享内存的进程间通信 实验目的 1.加深对进程概念的理解,明确进程与程序的区别;进一步认识并发执行的实质。 2.掌握进程管理、进程通信。 3....
  • 本Demo使用Delphi7编写,是为了验证Window 线程内消息队列的最大容量。
  • 所以消息队列可以解决应用解耦、异步消息、流量削锋等问题,是实现高性能、高可用、可伸缩最终一致性架构中不可以或缺的一环。 现在比较常见的消息队列产品主要有ActiveMQ、RabbitMQ、ZeroMQ、Kafka、RocketMQ等...
  • 建立队列的顺序存储结构(循环队列),进行入队出队的操作 首先我们先说一下队列的基本函数操作(c++) 头文件 #include<queue> 建立一个队列 数据类型 变量名 queue<int> q; 1、检验队列是否为空 ...
  • 基于队列评分的说话人验证决策
  • RabbitMQ消息队列中数据的消费顺序问题 场景:多个消费者绑定到同一个队列中 生产者: 有序发送一百条消息到队列中去,发送方法 rabbitTemplate.convertAndSend(“交换机”,“路由”,“消息内容”); 消费者: 然后...
  • 4.持久化/临时 两种队列 5.支持异步 — poll() 6.symmetrical — 单个TCP连接可用于双工通讯 7.多数据库支持 — SQLite、MongoDB…… 8.brokerless – 类似ZeroMQ的实现原理 9.扩展模块:RPC, bandwidth throttling ...
  • python实现链队列

    2020-06-10 08:20:51
    python链队列 在写链队列之前,我们需要知道队列元素进出的原则为“先进先出”。 class Node(): #结点类 def __init__(self,elem): self.elem = elem # 数据域,用来存放数据元素 self.next = None # 指针域,...
  • 《数据结构》实验三: 栈和队列实验 一..实验目的  巩固栈和队列数据结构,学会运用栈和队列。 1.回顾栈和队列的逻辑结构受限操作特点,栈和队列的物理存储结构常见操作。 2.学习运用栈和队列的...
  • 消息队列和Kafka的基本介绍 一、什么是消息队列 二、消息队列的应用场景 异步处理 应用耦合 限流削峰 消息驱动系统 三、消息队列的两种方式 点对点模式 发布/订阅模式 四、常见的消息队列的产品 五、...
  • 队列实现循环队列

    千次阅读 2018-04-20 21:53:40
    二、实验内容仿照资料中顺序循环队列的例子,设计一个只使用队头指针计数器的顺序循环队列抽象数据类型。其中操作包括:初始化、入队列、出队列、判断队列是否非空。编写主函数,验证所设计的顺序循环队列的正确性...
  • 基于stm32的串口环形队列,可以直接移植其他芯片,可测试验证,注释完整,项目中实际使用的代码
  • queueclient:非官方客户端,用于查看speedrun.com验证队列
  • 数据结构实验报告二 栈和队列

    千次阅读 2020-12-31 13:06:28
    数据结构实验报告:实验二 栈和队列
  • 算法题这里不会讲解基础概念,如果连栈和队列都不清楚的同学们,可能需要自己先去了解下。如果以前学过但是忘了的,是可以用本篇文章来回忆相关细节的。这篇文章会放代码,代码能力一般的同学建议在电脑上完成阅读。...
  • 注:本篇内容参考了《Java常用算法手册》、《大话数据结构》《Java编程(第四版)》三本书籍,并参考了在线工具网站中对于队列相关Java类的一些说明。 文中涉及的java以Java 1.8为准。 本人水平有限,文中如有...
  • 当字符串全部压入栈和队列后,逐个弹出字符,对链栈队列弹出的字符逐个进行比较是否相等,由于栈是先进后出,队列是先进先出,从而相当于对字符串首尾行进比较,从而能判断出字符串是否为回文。 代码即详细注释...
  • 队列介绍 队列是一种常见的数据结构,也是我们学习,工作中必须掌握的基础,众所周知,在计算机的世界里,基础的数据结构只有两种,一种是线性连续的存储结构–数组,还有一种是随机的存储结构—链表,很多知名或者...
  • 为了避免RED缺陷, 提出一种改进的...该算法采用二次圆函数来计算丢包概率, 减少了RED的设置参数, 实现了在网络大延时小延时时的队列稳定, 且在小延时能获得比PID队列更平滑的效果。NS2仿真验证了RED-r算法的有效性。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 155,206
精华内容 62,082
关键字:

发现队列和验证队列