Chinaunix首页 | 论坛 | 博客
  • 博客访问: 196891
  • 博文数量: 26
  • 博客积分: 567
  • 博客等级: 中士
  • 技术积分: 420
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-05 18:48
文章分类

全部博文(26)

文章存档

2011年(26)

分类: C/C++

2011-10-16 21:48:44

队列即先进先出(FIFO)的线性表。怎么来比喻队列呢?相当于有一排座位,只能依次从右边入座,从左边离开。入座的时候,第一个人坐最左边,第二个人坐左边的第二个位置,依次类推;出场的时候,最左边的人先走。

 

1. 循环(顺序)队列

       普通顺序队列有一个问题,假如中场的时候,最左边走了几个人,那么此时最左边的人,坐的却不是最左边的座位,因为最左边的人走后,头指针就移动到了此时最左边的人身上(而人无需移动),所以那些空位置就再也用不上了,造成了“假上溢”。所以普通顺序队列没意思,循环队列才可行。

       注意:自始至终,这些座位都是编好号的,从左到右依次为0,1,2,…类似于数组,座位的总个数即MAXSIZE,但是只能坐MAXSIZE-1个人,队头和队尾之间要留一个空位,即sq->rear+1=MAXSIZE时就意味着坐满了。

       循环队列的关键算法是,判断队尾是否还有空座,如果没有了,就再看看最左边是否有人离开而腾出来的空座位,如果左边头上有人,证明头尾都坐满了人,如果左边有空位,说明已经有人离开了,后来的人就直接坐到左边去。即:

if( sq->rear+1>= MAXSIZE )

       sq->rear=0; //坐不下了,转到队头去,看看队头有没有人。

else

       sq->rear++; //坐得下,直接坐到后面

将上面两句改成如下形式:

sq->rear =(sq->rear+1)%MAXSIZE;

       二者等价。实际上,sq->rear+1不会大于MAXSIZE,最多等于MAXSIZE,所以说上面那个if正确的写法应该是if( sq->rear+1==MAXSIZE ),如果sq->rear+1= MAXSIZE,则sq->rear就等于0,否则sq->rear=余数= sq->rear+1,所以说if else和求模运算是等价的。

 

循环队列的数据结构如下

typedef struct

{

       DataType data[QueueSize];

       int front;//头指针

       int rear;//尾指针    

}CirQueue;  

 

其他操作如下:

// 置队列空

void Initial(CirQueue *Q)

{

       Q->front=Q->rear=QueueSize-1;//注意这个绝对不能写作-1等,写成0也可以

}

 

// 判队列空

int IsEmpty(CirQueue *Q)

{

       return Q->front==Q->rear;

}

 

//判队列满

int IsFull(CirQueue *Q)

{

       return (Q->rear+1)%QueueSize==Q->front;//这句很多地方都要用到

}

 

//入队

void EnQueue(CirQueue *Q,DataType x)

{

       /*关键算法:新元素存入队尾,队尾再后移一位*/

       Q->data[Q->rear]=x;                 //新元素插入队尾

       Q->rear=(Q->rear+1)%QueueSize;      //循环意义下将尾指针加1

}

 

//出队

void DeQueue(CirQueue *Q)

{

       /*关键算法:最左边的人走后,就将队头front往右移一位(即循环意义下+1*/

       Q->front=(Q->front+1)%QueueSize;   //循环意义下的头指针加1

}

 

2. 链队列

数据结构如下:

typedef struct node{

       DataType data;

       struct node *next;

}LinkQueue;

typedef struct{

       LinkQueue *front;  //头指针

       LinkQueue *rear;

}QueueNode;

同样(见上一篇文章""),关于QueueNode我们也可以用数组LinkQueue *QueueNode[2]来实现。

 

基本操作

// 置队列空

void Initial(QueueNode *Q)

{

    Q->front=Q->rear=NULL;

}

//判队列空

int IsEmpty(QueueNode *Q)

{

    return Q->front==NULL&&Q->rear==NULL;

}

//进队列

void Push(QueueNode *Q,DataType x)

{//将元素x插入链队列尾部

       LinkQueue *p=(LinkQueue *)malloc(sizeof(LinkQueue));//申请新结点

       p->data=x;

       p->next=NULL;

    if(IsEmpty(Q))

              Q->front=Q->rear=p;  //x插入空队列

       else

       {

              Q->rear->next=p; //(Q->rear)是队尾的指针,即:使队尾结构体的next指针指向p

              Q->rear=p;     //队尾指针指向新的尾

       }

}

//出队列

DataType Pop(QueueNode *Q)

{

       LinkQueue *p;

       p=Q->front;                   //保存队头结点

       Q->front=p->next;             //使队头指向p后面的一位

    if(Q->rear==p)//原队中只有一个结点的情况,删去后队列变空,所以尾指针也应置空

              Q->rear=NULL;

       free(p);   //释放被删队头结点

}

 

注意上面列出的只是算法的关键部分,并不完整,删减了一些无碍算法逻辑的内容。

 

阅读(7568) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~