在线咨询
有事点这里
有事点这里
看不懂这篇文章?联系我们
("麦洛克菲"长期致力于内核与移动安全以及编程技术的推广与普及,我们更专业!)
如果想从事IT相关有竞争性的工作,欢迎报考麦洛克菲零基础班
作者:admin 时间:2016-10-31

第三章 队列

3.1队列定义:先进先出

队列是一种只允许前端(front,队首)进行删除操作,而在后端(rear,队尾)进行插入操作的数据结构。正是因为规定了从队首删除队尾插入的性质,因此最先插入的元素将是最先被删除的元素;反之最后插入的元素将是最后被删除的元素,因此队列又称为“先进先出”(FIFOfirst in first out)的数据结构。

 

队列是一种使用很广泛的数据结构,比如操作系统的进程调度就是用的队列,图的广度优先遍历也使用的是队列。

 

队列也是一种很好理解的数据结构。比如人们去银行办事,就是排成一队,新到的人从队尾插入,而银行工作人员都是从队首开始受理业务,受理完,队首的人就离开队列(从队列中删除)。

3.2队列结构:尾部插入,前端删除

如下图所示,队列底层数据结构可以使用链表或者数组。在使用链表的时候,如下图左边部分所示,用frontrear两个指针分别指向队列的前端和后端。在使用数组的时候,分别用2个整数frontrear做数组的下标,指向数组的前端和尾端。

 

需要注意的是,如果用数组作为队列的底层结构,那么在不断的插入元素和删除元素的时候,数组的内存空间将会不断的向上滑动(如下图中间部分所示),这在实际应用过程中肯定是不好的,因此假如数组的长度为MAX,通过用rear=(rear+1)%MAXfront=(front+1)%MAX来移动数组的前端和尾端,可以限制它们在数组的当前空间,这样就构成了一个循环队列(如下图右边部分所示)。

3.3队列基本操作

队列包含创建,入队,出队,队空判断,对满判断等操作。

1.         创建

int CreateQue();

用于创建一个队列,一般需要初始化队列的前端和后端指针。

2.         入队

int EnQueue(int e);

将特定的元素e从队列的尾部插入。

3.         出队

int DeQueue(int *e);

获取队列头部的数据并从队列删除。

4.         判断队列满

int IsQueueFull();

判断队列是否已满,如果队列满了就不能再从尾部插入数据了,只对基于数组的队列有效。

5.         判断队列空

int IsQueueEmpty();

判断队列是否为空,如果队列为空,就不能从队首删除数据了,在构造基于链表的队列的时候,队列为空,插入第一个元素的时候,也需要特别的处理。

3.4基于链表的链队

链表结点的存储结构如下:

typedef struct _node

{

       int value;

       struct _node *next;

}node,*pnode;

其中值的部分存放的是一个整数data,这部分数据可以自己再定义,增减。

node  *front=NULL;   //队头指针,由于是全局变量,请注意多线程安全

node  *rear=NULL;    //队尾指针,由于是全局变量,请注意多线程安全

在实现队列的基本操作的时候,最好是先画出队列的图形,如上图所示,然后按照图形来写各种操作的代码,思路就会比较清晰(注意,在多线程环境下,下面的代码没有提供加锁机制,需要另外处理)。

//创建队列

int CreateQueue()

{

       front = rear = NULL;//frontrear置为NULL

       return 1;

}

//判断队列是否为空

int IsQueueEmpty()

{

       if(front==NULL&&rear==NULL)//frontrear等于NULL是队列为空的标志

       {

              return 1;

       }

       return 0;

}

 

//入队

int EnQueue(int e)

{

       node *p = (node *)malloc(sizeof(node));

       if(p==NULL)

       {

              return -1;

       }

 

       memset(p,0,sizeof(node));

       p->value = e;

       p->next = NULL;

 

       if(IsQueueEmpty())//队列为空,直接将rearfront指向该结点

       {

              rear=front=p;

              return 1;

       }

       //队列不为空,插入尾部

       rear->next = p;

       rear = p;

 

       return 1;

}

//出队

int DeQueue(int *e)//必须传指针,否则出队的值无法获取

{

 

       if(IsQueueEmpty())

       {

              return -1;

       }

 

       if(e==NULL)

       {

              return -1;

       }

 

       //只有一个结点的时候

       if(rear==front && rear!=NULL)

       {

              *e = rear->value;

              free(rear);

              front=rear=NULL;

              return 1;

       }

       //多个结点的时候

       *e = front->value;

       node *q =front;

       front = front->next;

       free(q);

       return 1;

 

}

 

//遍历队列

void TraverseQueue()

{

       while(!IsQueueEmpty())

       {

              int value;

              DeQueue(&value);

              printf("%d ",value);

 

       }

       printf("\n");

}

 

//队列测试代码

int _tmain(int argc, _TCHAR* argv[])

{

       int value;

 

       CreateQueue();

       EnQueue(3);

       EnQueue(1);

       EnQueue(0);

       EnQueue(5);

 

       DeQueue(&value);

       printf("value:%d\n", value);

 

       EnQueue(18);

       EnQueue(27);

 

       DeQueue(&value);

       printf("value:%d\n", value);

       DeQueue(&value);

       printf("value:%d\n", value);

 

       TraverseQueue();

 

       return 0;

}

3.5基于数组的循环队列

如下图所示,基于数组的循环队列,有3种形态:

1,队列为空,这个时候front等于rear,如下图左边部分所示。

2,正常形态,这个时候,front指向队首元素,rear指向队尾元素的下一个位置,如下图中间部分所示。

3,队列满,这个时候,队尾指针指向队首指针的前一个位置(空位)。如下图右边部分所示。

因此,循环队列在队列满的时候,会浪费一个空间,这主要是为了区分队列空和队列满的2个状态的。否则,如果最后一个空间也存放元素,那么rear在加1后,就和front相等了,这和队列为空的判断条件是冲突的。

 

在实现基于数组的队列的基本操作的时候,结合上面3个队列的基本形态来写代码,会显得思路清晰。下面是具体的代码与数据结构(注意,在多线程环境下,下面的代码没有提供加锁机制,需要另外处理):

 

#define MAXSIZE 100//数组的元素个数

int Queue[MAXSIZE]={0};//队列的底层数据结构,数组,支持100个元素

int rear = 0;//队列后端,插入的位置

int front = 0;//队列前端,删除的位置

 

创建队列,将前端和后端置0

int CreateQueue()

{

       rear = front = 0;

       return 1;

}

 

判断队列是否为空

int IsQueueEmpty()

{

       return rear==front?1:0;//front等于rear,队列即为空

}

 

判断队列是否满

int IsQueueFull()

{

       return (rear+1)%MAXSIZE == front?1:0;//注意判断标准

}

 

入队:

int EnQueue(int e)

{

 

       if(IsQueueFull())

       {

              return -1;

       }

 

       Queue[rear]=e;

       rear = (rear+1)%MAXSIZE;

      

       return 1;

      

}

出队

int DeQueue(int *e)

{

       if(IsQueueEmpty())

       {

              return -1;

       }

       if (e==NULL)

       {

              return -1;

       }

 

       *e = Queue[front];

       front = (front + 1)%MAXSIZE;

      

       return 1;

}

队列遍历:

void TraverseQue()

{

       while(!IsQueueEmpty())

       {

              int val;

              DeQueue(&val);

              printf("%d ",val);

       }

       printf("\n");

}

接口测试:

int _tmain(int argc, _TCHAR* argv[])

{

       for(int i=0;i<200;i++)

       {

              EnQueue(i);

       }

       int val = 0;

 

       DeQueue(&val);

       printf("val:%d\n",val);

 

       DeQueue(&val);

       printf("val:%d\n",val);

 

       TraverseQue();

      

       return 0;

}