数据结构与算法整理5——队列（C语言）

1、队列的基本概念与特点

2、队列的两种存储结构的基本操作，队空，队满，环形队列，假溢出

1、队列的基本概念与特点

1.1队列的特点：先进先出（FIFO）可看做排队买冰淇淋，只能对队头和队尾进行操作

1.2存储方式：顺序存储和链式存储（注意front和rear的位置）

（队列的顺序存储）

（队列的链式存储）

1.3 队列的假溢出问题

队列中因为多次出队入队而导致的存储空间不足的问题——解决办法：循环队列

front+1==[front+1]%maxsize;

2、队列的两种存储结构的基本操作，队空，队满，环形队列，假溢出

队列的操作	循环队列	链式队列
定义数据类型	Typedef struct{ Int queue[maxsize]; Int rear,front,count; }seqrencequeue;	定义节点类型 Typedef struct qnode{ Int data； Struct qnode next; }linkedqueuenode; 定义队列的结构体 Typedef struct{ Linkedqueuenode front; Linkedqueuenode *front; }Lqueue;
判空与判满	方法一：使用count记录元素个数队列已满count>0&&rear==front; 或count==maxsize; 队列已空count==0; 方法二：加设标志位出队时置０入队时置１队列已满：tag==1 && rear==front 队列已空：tag==0 && rear==front 方法三：用掉一个存储单元（默认）队列已满： front=＝(rear+1)%MaxQueueSize 队列已空：rear==front	If(Q.front==null) Printf(“”queue is empty); 链式队列不会满
入队(在队尾入队)	Seqrencequeue Q; Q->queue[Q->rear]=x; Q->rear=(Q->rear+1)% maxsize;	P=(linkedqueuenode *)malloc(sizeof(linkedqueuenode)) Q->rear=p; p->next=null;
出队（在队头出队）	*d=Q->queue[Q->front]； Q->front=[Q->front+1]%maxsize;	P=Q->front; Q->front=Q->front->next; Free(p;)
取队头元素	*d=Q->queue[Q->front];	*d=Q.front->data;

队列的应用举例（CPU对资源的管理，图的广度周游等，树的层次周游）

3、几个例题

（2）写算法：从把一个队列中的元素存储到栈。将一个栈中的元素放于队列中的算法（写算法要求会写程序，核心语句一定要会）（可以直接调用push pop操作）

把队列中的元素存到栈中：

（1）新建队列与栈并赋值： Q=createEmptyQueue_seq();//队列 S= createEmptyStack_seq();//栈

（2）取队头： n=frontQueue_seq(Q);

（3）将队头入栈顶：push_seq( S, n );

（4）出队： popQueue_seq(Q);

把栈中的元素存到队列中：

（1）取出栈顶： n=top_seq( S);

（2）将栈顶入队尾：pushQueue_seq(Q,n);

（3）出栈: popStack_seq(S);

4、队列的操作（C语言）

（1）队列的链式存储操作：

/*队列链接表示：函数定义*/

#include<stdio.h>
#include<stdlib.h>

typedef int DataType;
struct  Node;
typedef  struct Node *PNode;

struct  Node { 		/* 结点结构 */
    DataType    info;
    PNode       link;
};

struct  LinkQueue {	/* 链接队列类型定义 */	
    PNode  f;  		/* 头指针 */
    PNode  r;  		/* 尾指针 */
};

typedef struct LinkQueue *PLinkQueue;

/*创建一个空队列*/
PLinkQueue  createEmptyQueue_link() { 	
    PLinkQueue plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue));
    if (plqu != NULL)
        plqu->f = plqu->r = NULL;
    else
        printf("Out of space!! \n");
  		
    return (plqu);
}

/*判断链接表示队列是否为空队列*/ 
int  isEmptyQueue_link( PLinkQueue plqu ) {
    return (plqu->f == NULL);
}


/*进队列*/
void  enQueue_link( PLinkQueue plqu, DataType x) { 
    PNode p = (PNode )malloc( sizeof( struct Node ) );
    if ( p == NULL  )
        printf("Out of space!");
    else { 
        p->info = x;
        p->link = NULL;
        if (plqu->f == NULL)
            plqu->f = p;
        else
            plqu->r->link = p;

        plqu->r = p;
    }
}

/*出队列*/
void  deQueue_link( PLinkQueue plqu ) { 
    PNode   p;
    if( plqu->f == NULL )
        printf( "Empty queue.\n " );
    else { 
        p = plqu->f;
        plqu->f = plqu->f->link;
        free(p);
    }
}

/* 在非空队列中求队头元素 */
DataType  frontQueue_link( PLinkQueue plqu ) { 
    return (plqu->f->info);
}


main()
{
	PLinkQueue  A;
	int i;
	A=createEmptyQueue_link();
	for(i=0;i<3;i++)
	{enQueue_link(A, i+1);
	}
	
	while(!isEmptyQueue_link(A))
	{printf("%d", frontQueue_link(A));
		deQueue_link(A);
	
	}
}

（2）队列的顺序存储操作：

/* 队列的顺序表示：函数定义 循环存储*/
#include <stdio.h>
#include <stdlib.h>

/* 队列的顺序表示：类型和函数声明 */

typedef int DataType;
#define MAXNUM 20  /* 队列中最大元素个数 */

struct  SeqQueue {	/* 顺序队列类型定义 */
    int f, r;
    DataType q[MAXNUM];
};

typedef struct SeqQueue *PSeqQueue;	/* 顺序队列类型的指针类型 */


/*创建一个空队列*/
PSeqQueue  createEmptyQueue_seq( void ) {  
    PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu==NULL)
        printf("Out of space!! \n");
    else
        paqu->f = paqu->r = 0;   //令头指针f和尾指针r都为0 
    return paqu;                 //返回队列 
}

/*判队列是否为空队列*/
int  isEmptyQueue_seq( PSeqQueue paqu ) {
    return paqu->f == paqu->r;          //如果  paqu->f == paqu->r则队列是空与下面的 paqu->r = (paqu->r + 1) % MAXNUM 表示队列已满相区别 
}

/* 在队列中插入一元素x */
void  enQueue_seq( PSeqQueue paqu, DataType x ) {
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.\n" );
    else {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}

/* 删除队列头部元素 */
void  deQueue_seq( PSeqQueue paqu ) {
    if( paqu->f == paqu->r )
        printf( "Empty Queue.\n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}

/* 对非空队列,求队列头部元素 */
DataType  frontQueue_seq( PSeqQueue paqu ) {
    return paqu->q[paqu->f];
}

main()
{
	PSeqQueue  A;int i;
	A=createEmptyQueue_seq();
	for(i=0;i<3;i++)
	{enQueue_seq(A, i+1);
	}
	
	
	while(!isEmptyQueue_seq(A))
	{printf("%d", frontQueue_seq(A));
		deQueue_seq(A);
	
	}
}

（3）队列的顺序循环存储

//顺序循环存储队列
#include "stdio.h"
#include "stdlib.h"

//定义一个顺序循环存储的数据类型
#define max 10
typedef struct Seqquen {
	char quen[max];
    int f,r;
}*SeqQuen; 

//创建一个队列
SeqQuen  creatquen(){
	SeqQuen q=(SeqQuen)malloc(sizeof(struct Seqquen));
    if(q==NULL)
    	printf("out of space!");
    else
    	q->f=q->r=0;
        return q;
}

//判断队列是否为空
int ifempty(SeqQuen q) {
	if(q->f==q->r){
		printf("队列为空");
		return 0; 
	}
	else {
		printf("队列不为空");
		return 1; 
	}
}


//入队列
void appendquen(SeqQuen q,char n) {
	if((q->r+ 1 ) % max == q->f){
		printf("队列已满无法入队");
	}
	else{
		q->quen[q->r]=n;
		q->r=(q->r+1)%max;
	}
}

//出队列
void deletequen(SeqQuen q){
	char n;
	if(q->f==q->r){
		printf("队列为空无法出队");
    }
	else{
		n=q->quen[q->f];
		q->f=(q->f+1)%max;
		printf("刚刚出队的元素是%c\n",n);
	}
} 

//取出队头
char getfront(SeqQuen q){
	if(q->f==q->r){
		printf("队列为空无法出队");
    }
    else{
    	return q->quen[q->f];
	}
}

//main函数测试
main(){
	SeqQuen q;
	q=creatquen();
	appendquen(q,'a');
	appendquen(q,'b');
	deletequen(q);
	printf("目前队顶的元素是%c",getfront(q));
}

原文链接：https://blog.csdn.net/weixin_40695088/article/details/104311125