目录

1 队列的定义

2 基本操作

         队列的表示和实现

链队列的基本操作 

(1) 初始化操作

(2) 入队操作

(3) 出队操作

循环队列

循环队列的基本操作

(1)初始化操作

(2)入队操作

(3)出队操作

3 队列的应用举例

1．打印杨辉三角

2．键盘输入循环缓冲区问题

1 队列的定义

队列 ： 是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。

 在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。

队列的抽象数据类型定义：

ADT  Queue

数据元素：可以是任意类型的数据，但必须属于同一个数据对象。  

关系：队列中数据元素之间是线性关系。

2 基本操作

队列的表示和实现

队列的两种存储表示，顺序表示和链式表示。

1.链队列 ：用链表表示的队列简称为链队列。

非空的链队列

 

 链队列可以定义如下：

typedef struct Node
{
  QueueElementType  data;     
  struct Node        *next;     
}LinkQueueNode;
 
typedef struct 
{
  LinkQueueNode   * front;
  LinkQueueNode   * rear;
   }LinkQueue;

链队列的基本操作 

(1) 初始化操作

int InitQueue(LinkQueue * Q)
{ 
  Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
  if(Q->front!=NULL)
		{
			Q->rear=Q->front;
			Q->front->next=NULL;
 			return(TRUE);
		}
	else  	return(FALSE);    
      } 

(2) 入队操作

int EnterQueue(LinkQueue *Q, QueueElementType x)
{  
      LinkQueueNode  * NewNode;
      NewNode=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
      if(NewNode!=NULL)
        {
               NewNode->data=x;
               NewNode->next=NULL;
               Q->rear->next=NewNode;
	  Q->rear=NewNode;
               return(TRUE);
         }
     else  return(FALSE);    
}

(3) 出队操作

int DeleteQueue(LinkQueue * Q, QueueElementType *x)
{  
  LinkQueueNode * p;
  if(Q->front==Q->rear)
       return(FALSE);
  p=Q->front->next;
  Q->front->next=p->next;  
  if(Q->rear==p)  
Q->rear=Q->front;  
 *x=p->data;
 free(p);   
 return(TRUE);	
     } 

---

循环队列

循环队列是队列的一种顺序表示和实现方法。

 循环队列的类型定义：

#define MAXSIZE 50  
typedef struct
{
	QueueElementType  element[MAXSIZE];  
	int  front;  
	int  rear ;  
    }SeqQueue; 

循环队列的基本操作

(1)初始化操作

void InitQueue（SeqQueue * Q）
{  
	Q->front=Q->rear=0;
    } 

(2)入队操作

int EnterQueue(SeqQueue *Q, QueueElementType x)
{  
    if((Q->rear+1)%MAXSIZE==Q->front)  
	return(FALSE);
      Q->element[Q->rear]=x;
      Q->rear=(Q->rear+1)%MAXSIZE;  
      return(TRUE);  
    } 

(3)出队操作

int DeleteQueue(SeqQueue *Q, QueueElementType * x)
{ 
   if（Q->front==Q->rear）  
	return(FALSE);
  *x=Q->element[Q->front];
  Q->front=(Q->front+1)%MAXSIZE;  
  return(TRUE);  
    } 

3 队列的应用举例

1．打印杨辉三角

 【算法思想】由图可看出杨辉三角形的特点：即每一行的第一个元素和最后一个元素均为1，其它位置上的数字是其上一行中与之相邻的两个整数之和。所以第i行上的元素要由第i-1行中的元素来生成。我们可以利用循环队列实现打印杨辉三角形的过程：在循环队列中依次存放第i-1行上的元素，然后逐个出队并打印，同时生成第i行元素并入队。

代码：

void YangHuiTriangle( )
{ SeqQueue  Q;
    InitQueue (&Q);
    EnterQueue (&Q,1);  
    for(n=2;n<=N;n++)   
    {
      EnterQueue (&Q,1);   
      for(i=1;i<=n-2;i++)  
       {
         DeleteQueue (&Q,&temp);
         Printf(“%d”,temp);     
         GetHead(Q,&x);
         temp=temp+x;      
         EnterQueue (&Q,temp);  
        }
      DeleteQueue (&Q, &x);  
      printf(“%d”, x);    
      EnterQueue (&Q, 1)   
    }
  While(!IsEmpty(Q))     
    {
    DeleteQueue (&Q, &x);  
    printf(“%d”, x);    
    }
    } 

2．键盘输入循环缓冲区问题

问题描述：有两个进程同时存在于一个程序中。其中第一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户键入的字符并保存到输入缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。当用户键入一个逗号（，）时，表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键入字符，直到用户输入一个分号（；）键，才结束第一个进程，同时也结束整个程序。

void KeyBoardBuffer()
{
         InitQueue (&Q);      
         for(;;)
        {
	  for(;;)   
	  {
		 printf("A");
		 if(kbhit())
		  {
			 ch1=bdos(7,0,0);  
			 f= EnterQueue (&Q,ch1);
			if(f==FALSE)
			  {
				 printf("循环队列已满n");
				 break;      
			  }
		 }
		 if(ch1==';'||ch1==',')
			 break;   
	 }
	while (!IsEmpty(Q))   
	  {
		  DeleteQueue (&Q,&ch2);
		  putchar(ch2);     
	 }
	if(ch1==';')
                              break;     
	else
                              ch1='';   
         }
}