线性结构--队列常用操作

Dear 丶 2022-02-02 15:57 215阅读 0赞

##### 循环队列的顺序存储实现和队列的链式存储实现 #####

--------------------

队列：先进先出，只能从队列的尾部进入，从头部出去

**常用操作**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]

--------------------

**循环队列**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 1]

--------------------

##### 一、循环队列的顺序存储实现 #####

###### 1、声明定义和初始化 ######

#define MAXSIZE//储存最大元素的个数 
    typedef struct QNode *Queue;
    struct QNode{ 
    	ElemenType Data[MAXSIZE];
    	int front;
    	int rear;
    };

--------------------

###### 2、循环队列的创建 ######

Queue CreatQueue()
    { 
    	Queue Q=(Queue)malloc(sizeof(struct QNode));
    	Q->Data=(ElemenType *)malloc((MAXSIZE)sizeof(ElemenType));
    	Q->front=Q->rear=0;
    	return Q;
     }

--------------------

###### 4、判断队列是否为满和是否为空 ######

bool IsFull(Queue Q)
    { 
    	return ((Q->rear+1)%MAXSIZE==Q->front);
    }
    
    bool IsEmpty(Queue Q)
    { 
    	return(Q->front==Q->rear);
    }

--------------------

###### 5、入队操作 ######

bool AddQ(Queue Q,ElemenType X)
    { 
    	if(IsFull(Q))
    	{ 
    		printf("Queue full");
    		return false;
    	}
    	else
    	{ 
    		Q->rear=(Q->rear+1)%MAXSIZE;
    		Q->Data[Q->rear]=X;
    		return true;
    	}
    }

--------------------

###### 6、出队操作 ######

ElemenType DeleteQ(Queue Q)
    { 
    	if(IsEmpty)
    		printf("Queue Empty");
    	else
    	{ 
    		Q->front=(Q->front+1)%MAXSIZE;
    		return Q->Data[Q->front];
    	}
    }

--------------------

##### 二、队列的链式存储实现 #####

###### 1、声明定义和初始化 ######

typedef struct Node *PtrNode;
    struct Node{ //链表的结构 
    	ElemenType Data;
    	PtrNode Next;
    }; 
    
    struct QNode{ //队列的结构 
    	PtrNode rear;
    	PtrNode front;
    };
    typedef struct QNode *Queue;

--------------------

###### 2、创建一个链表 ######

PtrNode MakeQueue()
    { 
    	PtrNode Q=(PtrNode)malloc(sizeof(struct Node));
    	Q->Next==NUll;
    	return Q;
    }

--------------------

###### 3、判断队列是否为空 ######

bool IsEmpty(Queue Q)
    { 
    	return(Q->front==NULL);
    }

--------------------

###### 4、入队 ######

bool AddQ(Queue Q,ElemenType X)
    { 
    	PtrNode tmp=(PtrNode)malloc(sizeof(struct Node));
    	tmp->Next=NULL;
    	tmp->Data=X;
    	Q->rear=tmp;
    	return true;
    }

--------------------

###### 5、出队 ######

ElemenType DeleteQ(Queue Q)
    { 
    	PtrNode tmp;
    	ElemenType back;
    	
    	if(IsEmpty)
    		printf("queue empty");
    	else
    	{ 
    		back=Q->front->Data;
    		
    		if(Q->front->Next==Q->rear)//判断队列是否只有一个元素 
    			Q->front=Q->rear=NULL;//如果只有一个元素，就让对列的头和尾都为空 
    			
    		else
    		{ 
    			tmp=Q->front->Next;
    			Q->front->Next=tmp->Next;
    			free(tmp);
    		}
    
    		return back;
    	}
    }

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]: /images/20220202/10c9e4816ffb4fc7980d46c2c2904081.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 1]: /images/20220202/457620d70208484db81b1169ae5a5ac1.png