【数据结构】限定性线性表——队列（3000字超级详细 图文结合）C语言

目录

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初始化为一个空的链队列 */
  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)
{  /* 将数据元素x插入到队列Q中 */
      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)
{  /* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
  LinkQueueNode * p;
  if(Q->front==Q->rear)
       return(FALSE);
  p=Q->front->next;
  Q->front->next=p->next;  /* 队头元素p出队 */
  if(Q->rear==p)  /* 如果队中只有一个元素p，则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初始化为一个空的循环队列 */
	Q->front=Q->rear=0;
    } 

(2)入队 *** 作

int EnterQueue(SeqQueue *Q, QueueElementType x)
{  /*将元素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)
{ /*删除队列的队头元素，用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++)   /* 产生第n行元素并入队，同时打印第n-1行的元素*/
    {
      EnterQueue (&Q,1);   /* 第n行的第一个元素入队*/
      for(i=1;i<=n-2;i++)  /* 利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/
       {
         DeleteQueue (&Q,&temp);
         Printf(“%d”,temp);     /* 打印第n-1行的元素*/
         GetHead(Q,&x);
         temp=temp+x;      /*利用队中第n-1行元素产生第n行元素*/
         EnterQueue (&Q,temp);  
        }
      DeleteQueue (&Q, &x);  
      printf(“%d”, x);    /* 打印第n-1行的最后一个元素 */
      EnterQueue (&Q, 1)   /* 第n行的最后一个元素入队 */
    }
  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);  /* 通过DOS命令读入一个字符*/
			 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='';   /*置空ch1，程序继续*/
         }
}