精华内容
下载资源
问答
  • C++数据结构——队列

    万次阅读 多人点赞 2018-06-26 22:20:30
    http://www.cnblogs.com/QG-whz/p/5171123.htmlhttp://www.169it.com/article/2718050585107790752.html1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:(1)队列中的数据元素遵循“先进先出”...

                                                      C++数据结构——队列

     

    参考博客:

     

    1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:

    (1)队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构;

    (2)在队尾添加元素,在队头删除元素。

    2、队列的相关概念:

    (1)队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头;

    (2)入队:队列的插入操作;

    (3)出队:队列的删除操作。

    3、队列的操作:

    (1)入队: 通常命名为push()

    (2)出队: 通常命名为pop()

    (3)求队列中元素个数

    (4)判断队列是否为空

    (5)获取队首元素

    4、队列的分类:

    (1)基于数组的循环队列(循环队列)

    (2)基于链表的队列(链队列)

    5、实例分析

           C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。C++队列Queue是一种容器适配器,它给予程序员一种先进先出(FIFO)的数据结构。

           那么我们如何判断队列是空队列还是已满呢?

          a、栈空: 队首标志=队尾标志时,表示栈空。

          b、栈满 : 队尾+1 = 队首时,表示栈满。

           使用标准库的队列时, 应包含相关头文件,在栈中应包含头文件: #include< queue> 。定义:queue< int > q;

    q.empty()               如果队列为空返回true,否则返回false
    q.size()                返回队列中元素的个数
    q.pop()                 删除队列首元素但不返回其值
    q.front()               返回队首元素的值,但不删除该元素
    q.push()                在队尾压入新元素
    q.back()                返回队列尾元素的值,但不删除该元素
    

    (1)基于数组的循环队列(循环队列)

           以数组作为底层数据结构时,一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作。具体的示例图参考:http://www.cnblogs.com/QG-whz/p/5171123.html

           循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。参考博客:【c++版数据结构】之循环队列的实现,判断循环队列是“空”还是“ 满”,有两种处理方法:

    • A. 设置状态标志位以区别空还是满
    • B. 少用一个元素,约定“队头front在队尾rear的下一个位置(指的是环的下一个位置)”作为“满”的标志

            C语言中,不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度;如果用户无法预估所用队列的最大长度,则宜采用链队列。

           定义front为队列头元素的位置,rear为队列尾元素的位置,MAXSIZE为循环队列的最大长度。注意以下几点,循环队列迎刃而解:

    • A.  求元素的个数:(rear - front + MAXSIZE) % MAXSIZE
    • B.  front/rear指向逻辑的下一个空间  front =(front+1)%MAXSIZE,rear = (rear+1)%MAXSIZE
    • C.  判空:front == rear
    • D.  判满:(rear+1+MAXSZIE) == front

     

    例子1、简单的队列操作

    #include <queue>
    #include <iostream>
    using namespace std;
    
    int main(){
    	queue<int> q;
    	for (int i = 0; i < 10; i++){
    		q.push(i);
    	}
    	if (!q.empty()){
    		cout << "队列q非空!" << endl;
    		cout << "q中有" << q.size() << "个元素" << endl;
    	}
    	cout << "队头元素为:" << q.front() << endl;
    	cout << "队尾元素为:" << q.back() << endl;
    	for (int j = 0; j < 10; j++){
    		int tmp = q.front();
    		cout << tmp << " ";
    		q.pop();
    	}
    	cout << endl;
    	if (!q.empty()){
    		cout << "队列非空!" << endl;
    	}
    	system("pause");
    	return 0;
    }
    运行结果:
     
     
    例子2、循环队列的C++实现
    #include <iostream>
    #include <queue>
    #include <string>
    using namespace std;
    
    template <typename T>
    class LoopQueue
    {
    public:
    	LoopQueue(int c = 10);
    	~LoopQueue();
    	bool isEmpty();        //队列的判空
    	int size();            //队列的大小
    	bool push(T t);        //入队列
    	bool pop();            //出队列
    	T front();            //队首元素
    
    private:
    	int capacity;
    	int begin;
    	int end;
    	T*  queue;
    };
    
    
    template<typename T>
    LoopQueue<T>::LoopQueue(int c = 10)
    	:capacity(c), begin(0), end(0), queue(nullptr)
    {
    	queue = new T[capacity];
    };
    
    template<typename T>
    LoopQueue<T>::~LoopQueue()
    {
    	delete[]queue;
    }
    
    template <typename T>
    bool LoopQueue<T>::isEmpty()                   //判断循环队列是否为空
    {
    	if (begin == end)
    		return true;
    	return false;
    };
    
    template<typename T>
    int LoopQueue<T>::size()
    {
    	return (end - begin + capacity) % capacity; //计算循环队列的长度
    };
    
    template<typename T>
    bool LoopQueue<T>::push(T t)
    {
    	if (end + 1 % capacity == begin)            //判断队列是否已满
    	{
    		return false;
    	}
    	queue[end] = t;
    	end = (end + 1) % capacity;
    	return true;
    };
    
    template <typename T>
    bool LoopQueue<T>::pop()                        //判断队列是否为空
    {
    	if (end == begin) 
    	{
    		return false;
    	}
    	begin = (begin + 1) % capacity;
    	return true;
    };
    
    template <typename T>
    T LoopQueue<T>::front()
    {
    	if (end == begin)
    	{
    		return false;
    	}
    	return queue[begin];
    };
    
    int main()
    {
    	LoopQueue<string> queue(6);
    	queue.push("one");
    	queue.push("two");
    	queue.push("three");
    	queue.push("four");
    	queue.push("five");
    	cout << "队列长度" << queue.size() << endl;
    	while (!queue.isEmpty())
    	{
    		cout << queue.front() << endl;
    		queue.pop();
    	}
    	getchar();
    	//system("pause");
    	return 0;
    }

    运行结果:

     

    (2)基于链表的队列(链队列)

           链队列是基于链表实现的队列,它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首,哪头做队尾显然我们应该以链表头部为队首,链表尾部为队尾。存储一个指向队尾的指针,方便从链表尾插入元素;使用带头节点的链表,方便从链表头删除元素

    代码参考:链式队列的C++实现

    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    struct QNode    //定义队列结点的数据结构
    {
    	QNode *next; //指针域,指向下一个结点
    	double data;    //数据域,存储队列信息
    };
    
    struct LinkQueue    //定义队列的数据结构
    {
    	QNode *front;      //队首指针,指向QNode类型的指针
    	QNode *rear;       //队尾指针
    };
    
    void InitQueue(LinkQueue &Q)     //构造一个空的队列
    {
    	QNode *q;
    	q = new QNode;    //申请一个结点的空间
    	q->next = NULL;   //当作头结点
    	//队首与队尾指针都指向这个结点,指针域为NULL
    	Q.front = q;
    	Q.rear = q;
    }
    
    int IsEmpty(LinkQueue &Q)    //判断队列是否为空
    {
    	if (Q.rear == Q.front)
    		return 0;
    	else
    		return 1;
    }
    
    void EnQueue(LinkQueue &Q, double e)     //从队列尾部插入元素
    {
    	QNode *p;    //新创建一个结点
    	p = new QNode;
    	p->next = NULL;
    	p->data = e;  //输入数据信息
    	//将新结点插入队列尾部
    	Q.rear->next = p;
    	Q.rear = p;       //设置新的尾结点
    }
    
    void DeQueue(LinkQueue &Q, double &e)   //从队列首部删除一个结点
    {
    	QNode *p;
    	p = Q.front->next;
    	e = p->data;    //保存要出队列的数据
    	Q.front->next = p->next;       //将下一个结点当作头结点后面链接的第一个结点
    	if (Q.rear == p)    //如果要删除的元素即为尾结点,则将头指针赋予尾指针,一同指向头结点,表示队列为空
    		Q.rear = Q.front;
    	delete p;
    }
    
    void DestoryQueue(LinkQueue &Q)       //销毁一个队列
    {
    	while (Q.front)
    	{
    		Q.rear = Q.front;    //从头节点开始,一个一个删除队列结点,释放空间
    		delete Q.front;
    		Q.front = Q.rear;
    	}
    }
    int main()
    {
    	LinkQueue *Q;  //定义一个队列Q
    	Q = new LinkQueue;
    	InitQueue(*Q);
    	cout << "开始往队列里输入数据,以-1作为结束符" << endl;
    	cout << "请输入一个数:" << endl;
    	double a, x;
    	cin >> a;
    	while (a != -1)
    	{
    		EnQueue(*Q, a);
    		cout << "请输入一个数:" << endl;
    		cin >> a;
    	}
    	//输出队列元素,队首->队尾
    	QNode *p;
    	p = Q->front->next;
    	if (p == NULL)     //如果为空表,直接退出
    	{
    		cout << "队列为空!" << endl;
    		return 0;
    	}
    	cout << "队列数据依次为:" << endl;
    	while (p != NULL)
    	{
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    	//删除队列元素
    	while (!IsEmpty(*Q))
    	{
    		DeQueue(*Q, x);
    		cout << x << " ";
    	}
    	//释放内存空间
    	delete Q->front;
    	delete Q;
    	system("pause");
    	return 0;
    }

    运行结果:

    还可以参考代码:C++ 链队列和循环队列基本操作

     

    总结:

           1、循环队列中判断队空的方法是判断front==rear,队满的方法是判断front=(rear+1)%MAXSIZE。(为什么不用一个length表示队长,当length==maxSize时表示队满,原因就是,在频繁的队列操作中,多出一个变量会大量的增加执行时间,所以不如浪费一个数组空间来得划算。)

           2、用单链表表示的链式队列特别适合于数据元素变动较大的情形,而且不存在溢出的情况

    展开全文
  • 数据结构——链队列——2016_12_27

    万次阅读 多人点赞 2016-12-27 22:39:58
    队列源代码(C语言版) /*********实现了初始化,插入,删除,销毁,退出等功能*********/ #include #include //定义节点 typedef struct QNode{ int data; struct QNode * next; }...

    链队列源代码(C语言版)



    /*********实现了初始化,插入,删除,销毁,退出等功能*********/


    #include<stdio.h>
    #include<stdlib.h>
    //定义节点
    typedef struct QNode{
       int data;
       struct QNode * next;
    }QNode,*QueuePtr;
    //定义队头和队尾
    typedef struct {
       QueuePtr front;
       QueuePtr rear;
    }LinkQueue;
    
    //初始化队列
    void InitQueue(LinkQueue *Q){
       if(Q->front=Q->rear=malloc(sizeof(QNode)))
       Q->front->next=NULL;
       else 
    	   exit(0);
    }
    //销毁队列
    void DestroyQueue(LinkQueue * Q){
    	while(Q->front){
    	  Q->rear=Q->front->next;
    	  free(Q->front);
    	  Q->front=Q->rear;
    	}
       printf("销毁完成!\n");
    }
    //插入节点
    void InsertQueue(LinkQueue * Q,int e){
        QueuePtr q;
    	q=malloc(sizeof(QNode));
    	if(!q)
    		exit(0);
    	q->data=e; q->next=NULL;
    	Q->rear->next=q;
    	Q->rear=q;
    }
    //删除节点
    void DeleteQueue(LinkQueue * Q){
        QueuePtr p;
    	p=Q->front->next;
    	Q->front->next=p->next;
    	if(Q->rear==p)
    		Q->rear=Q->front;
    	free(p);
    }
    //打印队列
    void PrintQueue(LinkQueue Q){
        QueuePtr p;
    	if(Q.front==Q.rear){
    		printf("队列空\n");  
    	}
        printf("_____________________________________________________________________________\n");
    	p=Q.front->next;
    	while(p->next!=NULL){
    	printf("%d ",p->data);
        p=p->next;
        }
    	printf("%d\n",p->data);
        printf("———————————————————————————————————————\n");
    }
    //主函数
    int main(){
    	int i,x,v;
         LinkQueue Q;
         InitQueue(&Q);
    	 for(i=1;i<=12;i++){
    	     InsertQueue(&Q,i);
    	 }
         printf("十二个节点的链队列已初始化完成!\n");
    	 PrintQueue(Q);
    	 printf("请输入操作序号1.插入  2.删除  3.销毁  4.退出\n");
         scanf("%d",&x);
    	 while(x!=0){
    		 switch(x){
    		 case 1:printf("请输入要插入的数值:");
    			    scanf("%d",&v);
                    InsertQueue(&Q,v);
    				PrintQueue(Q);
    				break;
    		 case 2:printf("正在删除:\n");
    			    DeleteQueue(&Q);
    				PrintQueue(Q);
    				break;
    		 case 3:printf("正在销毁...\n");
    			    DestroyQueue(&Q);
    		        
    		 case 4:exit(0);
    		 default:printf("输入参数有误,请重新输入!\n"); 
    		}
             printf("请输入操作序号1.插入  2.删除  3.销毁  4.退出\n");
         scanf("%d",&x);
    	 }
    	return 0;
    }


    程序截图:





        联系邮箱:xhsgg12302@outlook.com

                                                                                             2016_12_27

    展开全文
  • 数据结构之队列

    千次阅读 多人点赞 2021-08-24 21:22:38
    什么是队列 二.项目创建 三.队列代码实现 1.队列结构体的创建 2.初始化头尾指针 3.队尾入数据 4.队头出数据 5.求队列长度 6.返回队头数据 7.返回队尾数据 8.判断队列是否为空 9.队列销毁 四.总结 五....

    前言: 

    前面,我们学习了栈,单链表,双向链表,顺序表的内容。大家可以看看我上面写过的文章!

    双链表单链表
    动态顺序表静态顺序表

    目录

    一.什么是队列

    二.项目创建

    三.队列代码实现

    1.队列结构体的创建

    2.初始化头尾指针

    3.队尾入数据

    4.队头出数据

    5.求队列长度

    6.返回队头数据

    7.返回队尾数据

    8.判断队列是否为空

    9.队列销毁

    四.总结

    五.原码链接


    一.什么是队列

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)
    入队列:进行插入操作的一端称为队尾
    出队列:进行删除操作的一端称为队头

     

     队尾入数据,队头出数据


    问题:选择什么结构实现队列?

     1.若我们使用数组实现队列:插入数据很方便,时间复杂度为O(1),但是删除数据,需要将后面的数据往前覆盖。需要遍历数组效率低,时间复杂度为O(N)

    2.若我们使用单链表实现队列:入数据相当于尾插,出数据相当于头删。若我们只定义一个头指针,尾插数据则要遍历找到尾节点,效率低。但是若我们定义两个指针,一个指向头节点,一个指向尾节点。这样的话,入数据和出数据效率都是O(1)。

    综上:我们选择单链表实现队列!


    二.项目创建

    工程文件存放的内容
    Queue.h函数声明,宏定义
    Queue.c实现顺序表函数接口的定义
    test.c测试函数接口是否能实现功能

    三.队列代码实现

    1.队列结构体的创建

    队列:先进先出
    只允许一端插入,另一端删除
    队尾:入数据   队头:出数据

    为了方便后序更改变量,我们用typedef重命名变量。创建结构体队列节点,再创建一个结构体Queue用来存放指向队头的节点和队尾的节点。

    typedef int QDataType;
    //节点    
    typedef struct QueueType
    {
    	QDataType data;
    	struct QueueType* next;
    }QNode;
    
    typedef struct Queue
    {
    	QNode* head;	//指向队头节点
    	QNode* tail;	//指向队尾节点
    }Queue;

    我们定义Queue结构体变量pq 

    struct Queue pq;

    2.初始化头尾指针

    初始化指向队头和队尾的指针为空 。传值时,因为形参是实参的临时拷贝,所以我们要传址。

    //初始化头尾指针
    void QueueInit(struct Queue* pq)
    {
    	pq->head = NULL;
    	pq->tail = NULL;
    }

    3.队尾入数据

        动态开辟节点,要判断是否开辟成功!    入数据相当于尾插

    注:Queue结构体的头指针(pq->head)指向的就是头节点

     情况1:当队列无数据时,直接将头指针和尾指针指向新开辟的节点

    情况2:当队列中有数据时,第一个节点链接新节点。尾指针指向新开的节点

    情况1: 

    情况2:


    //队尾入数据 ---用尾指针尾插
    void QueuePush(Queue* pq, QDataType x)
    {
    
    	//创建节点
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	if (newnode == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	else
    	{
    		newnode->data = x;
    		newnode->next = NULL;
    	}
    	//队列无数据时
    	if (pq->head == NULL)
    	{
    		pq->head = pq->tail = newnode;
    	}
    	else
    	{
    		pq->tail->next = newnode;	//尾节点链接新节点
    		pq->tail = newnode;//队尾指针指向新节点
    	}
    }

    4.队头出数据

    队头出数据相当于头删

    出数据要保证队列中要有数据

    情况1:只有一个节点(即pq->head->next == NULL)时,直接释放第一个节点。并且把头指针和尾指针置空!

    情况2:有多个节点,保存第二个节点,释放第一个节点,然后头指针指向第二个节点。

    //队头出数据---用头指针头删
    void QueuePop(Queue* pq)
    {
    	assert(pq);
    	//要保证队列中有数据
    	assert(pq->head);
    	//当只有一个节点时->free掉第一个节点
    	if (pq->head->next == NULL)
    	{
    		free(pq->head);
    		pq->head = pq->tail = NULL;
    	}
    	//多个节点---保存第二个节点,释放第一个节点,头指针指向第二个节点
    	else
    	{
    		QNode* next = pq->head->next;//pq->head指向的就是第一个节点 pq->head->next 第二个节点
    		free(pq->head);
    		pq->head = next;
    	}
    }

    5.求队列长度

    1.因为队列长度肯定是大于等于0的,所有函数返回类型可以为size_t

      size_t 即为:unsigned int。  

    2.使用计数器,遍历队列求队列长度

    //求队列长度
    int QueueSize(Queue* pq)
    {
    	//遍历求长度
    	assert(pq);
    	int size = 0;
    	QNode* cur = pq->head;	//第一个节点
    	while (cur)
    	{
    		size++;
    		cur = cur->next;
    	}
    	return size;
    }

    6.返回队头数据

    头指针指向的就是头节点 

    //返回队头数据
    QDataType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(pq->head);//防止队列为空
    	return pq->head->data;
    }

    7.返回队尾数据

    尾指针指向的就是尾节点 

    //返回队尾数据
    QDataType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(pq->head);//防止队列为空
    	return pq->tail->data;
    }

    8.判断队列是否为空

    最初定义头指针为空,如果仍为空指针说明队列为空!

    //判断队列是否为空
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    	return  pq->head == NULL;
    }

    9.队列销毁

    节点是动态开辟的,所以我们要销毁空间,防止内存泄漏!遍历队列进行销毁

    步骤:释放节点时,要先保留下一个节点,不然就找不到下一个节点!

    注意:头指针和尾指针要置空

    //销毁
    void QueueDestory(Queue* pq)
    {
    	assert(pq);
    	//遍历销毁
    	QNode* cur = pq->head;
    	while (cur)
    	{
    		QNode* next = cur->next;//保留下一个节点
    		free(cur);
    		cur = next;
    	}
    	pq->head = pq->tail = NULL;
    }

    四.总结

    1.使用单链表实现队列,定义前后指针,一个指向队头,一个指向队尾!这样的话出数据和入数据的效率都是O(1)。  队头出数据,队尾入数据!

      那之前我们实现单链表时为什么不使用双指针呢?-->因为这样我们只能解决尾插,不能解决尾删,还得要找到上一个节点。

    2.打印数据时,不能直接打印!不然的话就不满足队列:先进先出的特点。要先取队头数据,再打印,然后出队头数据。以此循环。


    五.原码链接

    队列源码

    展开全文
  • 数据结构之队列.rar

    2020-04-07 19:17:00
    数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列
  • Java笔试面试-数据结构队列

    万次阅读 多人点赞 2019-09-18 09:04:13
      与栈相对的一种数据结构, 集合(Collection)的一个子类。队列允许在一端进行插入操作,而在另一端进行删除操作的线性表,栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,比如实现消息队列。...

    队列(Queue)

      与栈相对的一种数据结构, 集合(Collection)的一个子类。队列允许在一端进行插入操作,而在另一端进行删除操作的线性表,栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,比如实现消息队列。Queue 类关系图,如下:
    在这里插入图片描述

    1.Queue 分类

    • 双端队列:双端队列(Deque)是 Queue 的子类也是 Queue 的补充类,头部和尾部都支持元素插入和获取。
    • 阻塞队列:阻塞队列指的是在元素操作时(添加或删除),如果没有成功,会阻塞等待执行。例如,当添加元素时,如果队列元素已满,队列会阻塞等待直到有空位时再插入。
    • 非阻塞队列:非阻塞队列和阻塞队列相反,会直接返回操作的结果,而非阻塞等待。双端队列也属于非阻塞队列。

    2.Queue 方法

    • add(E):添加元素到队列尾部,成功返回 true
    • offer(E):添加元素到队列尾部,成功返回 true
    • remove():删除元素,成功返回 true,失败返回 false
    • poll():获取并移除此队列的第一个元素,若队列为空,则返回 null
    • peek():获取但不移除此队列的第一个元素,若队列为空,则返回 null
    • element():获取但不移除此队列的第一个元素,若队列为空,则抛异常

    3.Queue 使用实例

    Queue<String> linkedList = new LinkedList<>();
    linkedList.add("Dog");
    linkedList.add("Camel");
    linkedList.add("Cat");
    while (!linkedList.isEmpty()) {
        System.out.println(linkedList.poll());
    }
    

    程序执行结果:

    Dog
    Camel
    Cat
    

    阻塞队列

    1.BlockingQueue
      BlockingQueue 在 java.util.concurrent 包下,其他阻塞类都实现自 BlockingQueue 接口,BlockingQueue 提供了线程安全的队列访问方式,当向队列中插入数据时,如果队列已满,线程则会阻塞等待队列中元素被取出后再插入;当从队列中取数据时,如果队列为空,则线程会阻塞等待队列中有新元素再获取。

    BlockingQueue 核心方法

    插入方法:

    • add(E):添加元素到队列尾部,成功返回 true
    • offer(E):添加元素到队列尾部,成功返回 true
    • put(E):将元素插入到队列的尾部,如果该队列已满,则一直阻塞

    删除方法:

    • remove(Object):移除指定元素,成功返回 true,失败返回 false
    • poll(): 获取并移除队列的第一个元素,如果队列为空,则返回 null
    • take():获取并移除队列第一个元素,如果没有元素则一直阻塞

    检查方法:

    • peek():获取但不移除队列的第一个元素,若队列为空,则返回 null

    2.LinkedBlockingQueue
      LinkedBlockingQueue 是一个由链表实现的有界阻塞队列,容量默认值为 Integer.MAX_VALUE,也可以自定义容量,建议指定容量大小,默认大小在添加速度大于删除速度情况下有造成内存溢出的风险,LinkedBlockingQueue 是先进先出的方式存储元素。

    3.ArrayBlockingQueue
      ArrayBlockingQueue 是一个有边界的阻塞队列,它的内部实现是一个数组。它的容量是有限的,我们必须在其初始化的时候指定它的容量大小,容量大小一旦指定就不可改变。

      ArrayBlockingQueue 也是先进先出的方式存储数据,ArrayBlockingQueue 内部的阻塞队列是通过重入锁 ReenterLock 和 Condition 条件队列实现的,因此 ArrayBlockingQueue 中的元素存在公平访问与非公平访问的区别,对于公平访问队列,被阻塞的线程可以按照阻塞的先后顺序访问队列,即先阻塞的线程先访问队列。而非公平队列,当队列可用时,阻塞的线程将进入争夺访问资源的竞争中,也就是说谁先抢到谁就执行,没有固定的先后顺序。

    示例代码如下:

    // 默认非公平阻塞队列
    ArrayBlockingQueue queue = new ArrayBlockingQueue(6);
    // 公平阻塞队列
    ArrayBlockingQueue queue2 = new ArrayBlockingQueue(6,true);
    
    // ArrayBlockingQueue 源码展示
    public ArrayBlockingQueue(int capacity) {
        this(capacity, false);
    }
    public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }
    

    4.DelayQueue
      DelayQueue 是一个支持延时获取元素的无界阻塞队列,队列中的元素必须实现 Delayed 接口,在创建元素时可以指定延迟时间,只有到达了延迟的时间之后,才能获取到该元素。实现了 Delayed 接口必须重写两个方法 ,getDelay(TimeUnit)compareTo(Delayed),如下代码所示:

    class DelayElement implements Delayed {
            @Override
            // 获取剩余时间
            public long getDelay(TimeUnit unit) {
                // do something
            }
            @Override
            // 队列里元素的排序依据
            public int compareTo(Delayed o) {
                // do something
            }
        }
    

    DelayQueue 使用的完整示例,请参考以下代码:

    public class DelayTest {
        public static void main(String[] args) throws InterruptedException {
            DelayQueue delayQueue = new DelayQueue();
            delayQueue.put(new DelayElement(1000));
            delayQueue.put(new DelayElement(3000));
            delayQueue.put(new DelayElement(5000));
            System.out.println("开始时间:" +  DateFormat.getDateTimeInstance().format(new Date()));
            while (!delayQueue.isEmpty()){
                System.out.println(delayQueue.take());
            }
            System.out.println("结束时间:" +  DateFormat.getDateTimeInstance().format(new Date()));
        }
    static class DelayElement implements Delayed {
        // 延迟截止时间(单面:毫秒)
        long delayTime = System.currentTimeMillis();
        public DelayElement(long delayTime) {
            this.delayTime = (this.delayTime + delayTime);
        }
        @Override
        // 获取剩余时间
        public long getDelay(TimeUnit unit) {
            return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
        @Override
        // 队列里元素的排序依据
        public int compareTo(Delayed o) {
            if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
                return 1;
            } else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
                return -1;
            } else {
                return 0;
            }
        }
        @Override
        public String toString() {
            return DateFormat.getDateTimeInstance().format(new Date(delayTime));
        }
    }
    

    }
    程序执行结果:

    开始时间:2019-6-13 20:40:38
    
    2019-6-13 20:40:39
    
    2019-6-13 20:40:41
    
    2019-6-13 20:40:43
    
    结束时间:2019-6-13 20:40:43
    

    非阻塞队列

      ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部;当我们获取一个元素时,它会返回队列头部的元素。它的入队和出队操作均利用 CAS(Compare And Set)更新,这样允许多个线程并发执行,并且不会因为加锁而阻塞线程,使得并发性能更好。

    ConcurrentLinkedQueue 使用示例:

    ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
    concurrentLinkedQueue.add("Dog");
    concurrentLinkedQueue.add("Cat");
    while (!concurrentLinkedQueue.isEmpty()) {
        System.out.println(concurrentLinkedQueue.poll());
    }
    

    执行结果:

    Dog
    
    Cat
    

    优先级队列

      PriorityQueue 一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。

    PriorityQueue 代码使用示例:

    Queue<Integer> priorityQueue = new PriorityQueue(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            // 非自然排序,数字倒序
            return o2 - o1;
        }
    });
    priorityQueue.add(3);
    priorityQueue.add(1);
    priorityQueue.add(2);
    while (!priorityQueue.isEmpty()) {
        Integer i = priorityQueue.poll();
        System.out.println(i);
    }
    

    程序执行的结果是:

    3
    
    2
    
    1
    

    PriorityQueue 注意的点:

    • PriorityQueue 是非线程安全的,在多线程情况下可使用 PriorityBlockingQueue 类替代;
    • PriorityQueue 不允许插入 null 元素。

    面试笔试题

    1.ArrayBlockingQueue 和 LinkedBlockingQueue 的区别是什么?

    答:ArrayBlockingQueue 和 LinkedBlockingQueue 都实现自阻塞队列 BlockingQueue,它们的区别主要体现在以下几个方面:

    • ArrayBlockingQueue 使用时必须指定容量值,LinkedBlockingQueue 可以不用指定;
    • ArrayBlockingQueue 的最大容量值是使用时指定的,并且指定之后就不允许修改;而 LinkedBlockingQueue 最大的容量为 Integer.MAX_VALUE
    • ArrayBlockingQueue 数据存储容器是采用数组存储的;而 LinkedBlockingQueue 采用的是 Node 节点存储的。

    2.LinkedList 中 add() 和 offer() 有什么关系?

    答:add() 和 offer() 都是添加元素到队列尾部。offer 方法是基于 add 方法实现的,Offer 的源码如下:

    public boolean offer(E e) {
        return add(e);
    }
    

    3.Queue 和 Deque 有什么区别?

    答:Queue 属于一般队列,Deque 属于双端队列。一般队列是先进先出,也就是只有先进的才能先出;而双端队列则是两端都能插入和删除元素。

    4.LinkedList 属于一般队列还是双端队列?

    答:LinkedList 实现了 Deque 属于双端队列,因此拥有 addFirst(E)addLast(E)getFirst()getLast() 等方法。

    5.以下说法错误的是?

    A:DelayQueue 内部是基于 PriorityQueue 实现的
    B:PriorityBlockingQueue 不是先进先出的数据存储方式
    C:LinkedBlockingQueue 默认容量是无限大的
    D:ArrayBlockingQueue 内部的存储单元是数组,初始化时必须指定队列容量

    答:A

    题目解析:LinkedBlockingQueue 默认容量是 Integer.MAX_VALUE,并不是无限大的。

    6.关于 ArrayBlockingQueue 说法不正确的是?

    A:ArrayBlockingQueue 是线程安全的
    B:ArrayBlockingQueue 元素允许为 null
    C:ArrayBlockingQueue 主要应用场景是“生产者-消费者”模型
    D:ArrayBlockingQueue 必须显示地设置容量

    答:B

    题目解析:ArrayBlockingQueue 不允许元素为 null,如果添加一个 null 元素,会抛 NullPointerException 异常。

    7.以下程序执行的结果是什么?

    PriorityQueue priorityQueue = new PriorityQueue();
    priorityQueue.add(null);
    System.out.println(priorityQueue.size());
    

    答:程序执行报错,PriorityQueue 不能插入 null。

    8.Java 中常见的阻塞队列有哪些?
    答:Java 中常见的阻塞队列如下:

    • ArrayBlockingQueue,由数组结构组成的有界阻塞队列;
    • PriorityBlockingQueue,支持优先级排序的无界阻塞队列;
    • SynchronousQueue,是一个不存储元素的阻塞队列,会直接将任务交给消费者,必须等队列中的添加元素被消费后才能继续添加新的元素;
    • LinkedBlockingQueue,由链表结构组成的阻塞队列;
    • DelayQueue,支持延时获取元素的无界阻塞队列。

    9.有界队列和无界队列有哪些区别?

    答:有界队列和无界队列的区别如下。

    • 有界队列:有固定大小的队列叫做有界队列,比如:new ArrayBlockingQueue(6),6 就是队列的大小。
    • 无界队列:指的是没有设置固定大小的队列,这些队列的特点是可以直接入列,直到溢出。它们并不是真的无界,它们最大值通常为 Integer.MAX_VALUE,只是平常很少能用到这么大的容量(超过 Integer.MAX_VALUE),因此从使用者的体验上,就相当于 “无界”。

    10.如何手动实现一个延迟消息队列?

    答:说到延迟消息队列,我们应该可以第一时间想到要使用 DelayQueue 延迟队列来解决这个问题。实现思路,消息队列分为生产者和消费者,生产者用于增加消息,消费者用于获取并消费消息,我们只需要生产者把消息放入到 DelayQueue 队列并设置延迟时间,消费者循环使用 take() 阻塞获取消息即可。完整的实现代码如下:

    public class CustomDelayQueue {
        // 消息编号
        static AtomicInteger MESSAGENO = new AtomicInteger(1);
    public static void main(String[] args) throws InterruptedException {
        DelayQueue<DelayedElement> delayQueue = new DelayQueue<>();
        // 生产者1
        producer(delayQueue, "生产者1");
        // 生产者2
        producer(delayQueue, "生产者2");
        // 消费者
        consumer(delayQueue);
    }
    
    //生产者
    private static void producer(DelayQueue<DelayedElement> delayQueue, String name) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    // 产生 1~5 秒的随机数
                    long time = 1000L * (new Random().nextInt(5) + 1);
                    try {
                        Thread.sleep(time);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    // 组合消息体
                    String message = String.format("%s,消息编号:%s 发送时间:%s 延迟:%s 秒",
                            name, MESSAGENO.getAndIncrement(), DateFormat.getDateTimeInstance().format(new Date()), time / 1000);
                    // 生产消息
                    delayQueue.put(new DelayedElement(message, time));
                }
            }
        }).start();
    }
    
    //消费者
    private static void consumer(DelayQueue<DelayedElement> delayQueue) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    DelayedElement element = null;
                    try {
                        // 消费消息
                        element = delayQueue.take();
                        System.out.println(element);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }
    
    // 延迟队列对象
    static class DelayedElement implements Delayed {
        // 过期时间(单位:毫秒)
        long time = System.currentTimeMillis();
        // 消息体
        String message;
        // 参数:delayTime 延迟时间(单位毫秒)
        public DelayedElement(String message, long delayTime) {
            this.time += delayTime;
            this.message = message;
        }
        @Override
        // 获取过期时间
        public long getDelay(TimeUnit unit) {
            return unit.convert(time - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
        @Override
        // 队列元素排序
        public int compareTo(Delayed o) {
            if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS))
                return 1;
            else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS))
                return -1;
            else
                return 0;
        }
        @Override
        public String toString() {
            // 打印消息
            return message + " |执行时间:" + DateFormat.getDateTimeInstance().format(new Date());
        }
    }
    

    }
    以上程序支持多生产者,执行的结果如下:

    生产者1,消息编号:1 发送时间:2019-6-12 20:38:37 延迟:2 秒 |执行时间:2019-6-12 20:38:39

    生产者2,消息编号:2 发送时间:2019-6-12 20:38:37 延迟:2 秒 |执行时间:2019-6-12 20:38:39

    生产者1,消息编号:3 发送时间:2019-6-12 20:38:41 延迟:4 秒 |执行时间:2019-6-12 20:38:45

    生产者1,消息编号:5 发送时间:2019-6-12 20:38:43 延迟:2 秒 |执行时间:2019-6-12 20:38:45

    ……

    展开全文
  • 数据结构-栈和队列

    万次阅读 多人点赞 2012-06-19 12:53:15
    其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示: 结论:后进先出(Last In First Out),简称为LIFO线性表。 栈的基本运算有六种: 构造空栈:InitStack(S)、 判栈空: StackEmpty...
  • 数据结构-队列

    千次阅读 2021-01-08 20:32:03
    下面,我们再来学习另外一个受限的数据结构:队列 队列( Queue),它是一种受限的线性表先进先出( FIFO First In First Out) 受限之处在于它只允许在表的前端( front)进行删除操作 而在表的后端(rear)进行插入...
  • 数据结构——队列及循环队列

    千次阅读 2014-12-02 22:49:17
    说明:严蔚敏的《数据结构》(C语言版)学习笔记,记录一下,以备后面查看。#include #include #define OK 1; #define ERROR -1; typedef int QElemType; typedef int Status; //定义队列节点 typedef struct ...
  • 队列中没有数据元素时称为空队列队列的操作是按照先进先出(first in first out)或后进后出(last in last out)的原则进行的。因此,队列又被称为FIFO表。它的实现方式主要有顺序队列、链队列两种。   队列...
  • ❤️《画解数据结构》九张动图,画解队列❤️

    千次阅读 多人点赞 2021-08-17 13:49:32
    基础数据结构 ——「 先进先出 」队列
  • 图解Java数据结构之队列

    千次阅读 2019-08-06 16:00:07
    本篇文章,将对队列进行一个深入的解析。 使用场景 队列在日常生活中十分常见,...刚才通过生活中的例子大致了解了一下队列,那么从数据结构的角度来讲,队列到底是什么呢? 队列是一个有序列表,可以用数组或是...
  • 循环队列–C语言实现–数据结构

    万次阅读 多人点赞 2017-06-22 16:36:45
    循环队列–C语言实现–数据结构目录循环队列C语言实现数据结构目录 一 要求 二 循环队列 三 循环队列的算法设计 1 建立循环队列 2 置空队列 3 入队 4 出队 5 打印队 四 程序 1 程序的结构 2 程序源码 五 程序测试 1 ...
  • 数据结构之循环队列

    千次阅读 2019-03-06 15:35:54
    数据结构之循环队列 前言: 关于循环队列需明白以下几点: 1、循环队列队列的顺序存储结构 2、循环队列用判断是否为空利用 Q.front=Q.rear 3、循环队列头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下...
  • java数据结构——队列

    千次阅读 2019-02-21 17:12:33
    上一篇博客我们拒了羽毛球筒的例子来类比栈这种数据结构,这次我们用排队这种模型来类比我们接下来要说的数据结构——队列
  • 数据结构实践——队列数组

    千次阅读 2015-10-06 07:13:36
    本文是针对数据结构基础系列网络课程(3):栈和队列的实践项目。【项目 - 队列数组】  创建10个队列,分别编号为0-9(处理为队列数组,编号即下标)。输入若干个正整数,以数字0作为结束。设输入的值为x,其个位...
  • 数据结构之消息队列

    千次阅读 2016-02-21 22:58:11
    三、队列创建步骤:创建队列,销毁队列,清空队列,判空队列队列长度,新元素入队,首元素出队,遍历队列; 四、队列特点:先进先出(First In First Out - FIFO) 五、普通队列的两个缺点:队列中n个元素出队...
  • 数据结构与算法—队列详解

    千次阅读 2019-08-16 01:18:41
    栈和队列是一对好兄弟,前面我们介绍过数据结构与算法—栈详解,那么栈的机制相对简单,后入先出,就像进入一个狭小的山洞,山洞只有一个出口,只能后进先出(在外面的先出去)。而队列就好比是一个隧道,后面的人跟着...
  • 消息队列发送数据和接收数据

    千次阅读 2017-09-10 17:28:25
    消息队列发送数据和接收数据
  • 数据结构队列的应用】用队列打印杨辉三角

    千次阅读 多人点赞 2016-03-12 11:00:58
    方法很多,队列就是其中的一种。下面给出基于队列实现的杨辉三角。 # include # define M 100 typedef struct { int a[M]; int front,rear; }sq; void init(sq *q) { q->rear=q->front=0; } int enter(sq *
  • 队列中的数据是放在内存中的,可以通过分布式缓存redis优化队列。   demo.py(进程通过队列共享数据): import multiprocessing def download_from_web(q): """下载数据""" ...
  • 数据结构笔记:单线队列

    千次阅读 2020-03-06 09:04:46
    队列有单向队列(我姑且这么称之)和双端队列 单项队列 只能一端只能存入,一端只能取出,先进先出 可以通过线性表(顺序表或链表)实现 单向队列的实现 class Queue(object): def __init__(self): '''初始化...
  • 数据结构—队列

    千次阅读 2015-10-23 21:58:45
    队列是一种先进先出(FIFO)的线性表,它只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入的一端称为队尾(rear),允许删除元素的一端称为队头(front)。
  • 数据结构实践项目——队列

    千次阅读 2015-10-06 08:04:39
    本组项目针对《数据结构基础系列(3):线性表》中的7-12课:7.队列的定义 8. 顺序队的存储及基本操作 9. 环形队列的存储及基本操作 10. 队列的链式存储结构及其基本运算的实现 11. 队列的应用-迷宫问题 12. 双端...
  • 数据结构——队列的详解

    千次阅读 多人点赞 2020-04-21 12:55:45
    队列和栈相反,队列(queue)是一种先进先出(FIFO:first in first out)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。队列和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,...
  • 数据结构——队列

    千次阅读 2013-07-30 21:27:42
    队列:只允许在一段进行插入删除操作,而在另一端进行删除操作的线性表。 队列是一种先进先出(FIFO)的线性表,允许插入的一端为队尾,允许插入的一端为队头。 循环队列 头尾相接的顺序存储结构为循环队列。 为...
  • Python数据结构队列的实现

    千次阅读 2017-11-20 20:02:22
    队列结构:queue 生活例子:排队买票 ...队列:Push、Pop、队列的大小、是否为空队列、清空队列 先进先出 双端队列:两端都能进,都能出 class Queue(object): # 先进先出 # 在Python中用列表模拟
  • 数据结构 - 栈和队列

    千次阅读 2020-06-22 21:23:59
    数据结构 - 栈和队列的定义和特点
  • Nginx数据结构是循环队列,prev前置节点环和next后置节点环。 Nginx链表还是非常有特色的,它是一种轻量级链表,这种链表不包含数据内容,只包含前后节点指针。在使用的时候需要作为带有节点变量的结构体(宿主)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,043,211
精华内容 417,284
关键字:

数据队列