数据结构之线性结构-队列

末蓝、 2022-10-13 12:51 242阅读 0赞

# 队列 #

先进先出

==队列(Queue)==是只允许在一端进行插入在另一端进行删除操作的**线性表。**

队首是允许删除的一端。

队尾是允许插入的一端。

空队是不含任何元素的队列。

## 基本操作 ##

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入， 使之成为新的队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x): 读队头元素，若队列Q非空，则将队头元素赋值给x。

QueueEmpty(Q)：判队列空，若队列Q为空返回true, 否则返回false。

## 循环队列 ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define ElemType int//数据元素的类型
    #define MaxSize 5
    
    //循环队列
    //定义队列
    //牺牲一个存储单元用于区分队空和队满
    typedef struct {
        
    	ElemType data[MaxSize];
    	int front, rear;
    }SequenceQueue;
    //还可以增加一个size，保存队长
    
    int InitQueue(SequenceQueue& Q) {
        
    	Q.front = Q.rear = 0;
    	return 1;
    }
    
    //判满
    int QueueFull(SequenceQueue Q) {
        
    	if ((Q.rear + 1) % MaxSize == Q.front)//判满
    		//若队尾指针的下一个位置是队头，则队满
    		return 1;//若满，返回1
    	else
    		return 0;
    }
    
    //判空
    int QueueEmpty(SequenceQueue Q) {
        
    	if (Q.front == Q.rear)//判空
    		return 1;//若空，返回1
    	else
    		return 0;
    }
    
    //求队长
    int QueueLength(SequenceQueue Q) {
        
    	return (Q.rear - Q.front + MaxSize) % MaxSize;
    }
    
    //入队
    int EnQueue(SequenceQueue& Q, ElemType x) {
        
    	if ((Q.rear + 1) % MaxSize == Q.front)//判满
    		return 0;
    	Q.data[Q.rear] = x;
    	//Q.rear += 1;
    	(Q.rear += 1)%MaxSize;
    	return 1;
    }
    
    //出队
    int DeQueue(SequenceQueue& Q, ElemType& x) {
        
    	if (Q.front == Q.rear)//判空
    		return 0;
    	x = Q.data[Q.front];
    	//Q.front = (Q.front + 1);
    	Q.front = (Q.front + 1) % MaxSize;
    	return 1;
    }
    
    //或取队头元素
    int GetHead(SequenceQueue& Q, ElemType& x) {
        
    	if (Q.front == Q.rear)//判空
    		return 0;
    	x = Q.data[Q.front];
    	return 1;
    }
    
    int main() {
        
    	SequenceQueue Q;
    	ElemType x = 0;
    	InitQueue(Q);
    	int i;
    	for (i = 0; i < 10; i += 2) {
        
    		if(EnQueue(Q, i))
    			printf_s("%d入队\n", i);
    	}
    
    	if (QueueFull(Q)) {
        
    		printf_s("队满\n");
    	}
    	else {
        
    		printf_s("队不满\n");
    	}
        length = QueueLength(Q);
    	printf_s("队长为%d\n", length);
    
    	for (i = 0; i < 10; i += 2) {
        
    		if(DeQueue(Q, x))
    			printf_s("%d出队\n", x);
    	}
    
    	if (QueueEmpty(Q)) {
        
    		printf_s("队空\n");
    	}
    	else {
        
    		printf_s("队不空\n");
    	}
    	system("pause");
    	return 0;
    }

区分循环队列是队空还是队满有三种方法：

1.  牺牲一个存储单元来区分，约定”队头指针在队尾指针的下一个位置作为队满条件“  
    队满：(Q.rear + 1) % MaxSize == Q.front；队空：Q.front == Q.rear；队长：Q.rear - Q.front + MaxSize) % MaxSize
2.  队列增加一个size元素记录队长，size==0表示队空，size==MaxSize表示队满。
3.  队列增设tag表示状态，进队tag置1，出队tag置0。初始tag=0。tag==0时，若因出队导致Q.front == Q.rear则为队空；tag==1时，若因入队导致Q.front == Q.rear则为队满。

#include<stdio.h>
    #include<stdlib.h>
    
    #define ElemType int//数据元素的类型
    #define MaxSize 5
    
    //循环队列
    //定义队列
    //增加tag
    typedef struct {
        
    	ElemType data[MaxSize];
    	int front, rear;
    	int tag;
    }SequenceQueue;
    //还可以增加一个size，保存队长
    
    int InitQueue(SequenceQueue& Q) {
        
    	Q.front = Q.rear = 0;
    	Q.tag = 0;
    	return 1;
    }
    
    //求队长
    int QueueLength(SequenceQueue Q) {
        
    	return (Q.rear - Q.front + MaxSize) % MaxSize;
    }
    
    //入队
    int EnQueue(SequenceQueue& Q, ElemType x) {
        
    	if (Q.rear == Q.front && Q.tag == 1)//判满
    		return 0;
    	Q.data[Q.rear] = x; \
    		(Q.rear += 1) % MaxSize;
    	Q.tag = 1;
    	return 1;
    }
    
    //出队
    int DeQueue(SequenceQueue& Q, ElemType& x) {
        
    	if (Q.front == Q.rear && Q.tag == 0)//判空
    		return 0;
    	x = Q.data[Q.front];
    	Q.front = (Q.front + 1) % MaxSize;
    	Q.tag = 0;
    	return 1;
    }
    
    
    
    int main() {
        
    	SequenceQueue Q;
    	ElemType x = 0;
    	InitQueue(Q);
    	EnQueue(Q, 1);
    	DeQueue(Q, x);
    	printf_s("%d", x);
    	system("pause");
    	return 0;
    }

## 链队 ##

//定义链式队列
    //队列节点
    typedef struct LinkNode{
        
    	ElemType data;
    	struct LinkNode* next;
    }LinkNode;
    //队列
    typedef struct {
        
    	LinkNode* front, * rear;
        //int length;//可以考虑增加一个参数，保存队的长度
    }LinkQueue;
    
    //初始化
    int InitLinkQueue(LinkQueue& Q) {
        
    	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    	Q.front->next = NULL;
    	return 1;
    }
    
    //判空
    bool isEmpty(LinkQueue Q) {
        
    	if (Q.front->next == NULL)
    		return true;
    	else
    		return false;
    }
    
    //入队
    int EnLinkQueue(LinkQueue& Q, ElemType x) {
        
    	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    	s->data = x;
    	s->next = NULL;
    	Q.rear->next = s;//新节点插入到rear之后
    	Q.rear = s;//修改rear
    	return 1;
    
    	//如果不带头节点
    	/*
    	if(Q.front==NULL){
    		Q.front=s;
    		Q.rear=s;
    	}else{
    		Q.rear->next = s;//新节点插入到rear之后
    		Q.rear = s;//修改rear
    	}
    	*/
    }
    
    //出队
    int DeLinkQueue(LinkQueue& Q, ElemType& x) {
        
    	if (Q.front == Q.rear)
    		return 0;//队空
    	LinkNode* p = Q.front->next;
    	x = p->data;
    	Q.front->next = p->next;
    	if (Q.rear == p)//如果这是最后一个节点，修改对尾指针
    		Q.rear = Q.front;
    	free(p);//释放空间
    	return true;
    }
    
    int main() {
        
    	LinkQueue Q;
    	InitLinkQueue(Q);
    	ElemType x;
    	int i;
    	for (i = 0; i < 10; i += 2) {
        
    		if(EnLinkQueue(Q, i))
    			printf_s("%d入队\n", i);
    	}
    
    	for (i = 0; i < 10; i += 2) {
        
    		if(DeLinkQueue(Q, x))
    			printf_s("%d出队\n", x);
    	}
    
    	if (isEmpty(Q)) {
        
    		printf_s("队空\n");
    	}
    	else {
        
    		printf_s("队不空\n");
    	}
    	free(Q.front);
    
    	system("pause");
    	return 0;
    }